Матрица инциденций

Территория рекламы

. МАТРИЦА ИНЦИДЕНЦИЙ

   

Обратимся к направленному графу. При математическом моделировании электронных схем информацию о топологии схемы удобно хранить в виде матрицы инциденций.

Для направленного графа с k вершинами и l ветвями полной матрицей инциденций называется матрица, имеющая k строк и l столбцов, причем элементы aij матрицы определяются следующим образом:

aij = +1, если ветвь j принадлежит узлу i и стрелка направлена от узла i;

aij = -1, если ветвь j принадлежит узлу i и стрелка направлена к узлу i;

aij = 0  в остальных случаях.

Пример: изобразим полную матрицу инциденций.

Легко заметить, что у каждой полной матрицы инциденций сумма всех строк равна 0. Т. о. строки этой матрицы линейно зависимы.

На практике обычно используют индуцированную матрицу А, которая получается из Аn путем удаления одной строки. При этом никакой потери информации нет, т.к. вычеркнутая строка равна сумме остальных строк.

В дальнейшем, если не делается уточнений, то предполагаем, что используется обычно редуцированная матрица.

          

         

Рис. 3. Граф и соответствующая ему матрица инциденций

    Редуцированная матрица содержит k-1 строк и столбцы в количестве l.

3.4. МАТРИЦА КОНТУРОВ

Обратимся к направленным графам и введем понятие "ориентированный контур".

Контур называется ориентированным, если ему приписана одна из двух возможных ориентаций.

При графическом изображении ориентации обозначают стрелками.

Приведем пример графа с ориентированными контурами:

Рис. 4. Пример графа с неориентированными контурами.

       Вначале определим матрицу контуров, соответствующую всем контурам графа; будем называть её полной матрицей контуров Вп.

Для направленного графа с l ветвями и m ориентированными контурами полной матрицей контуров называется матрица, имеющая l строк и m столбцов, каждый элемент bij которой определяется следующим образом:

bij = +1, если j-я ветвь входит в i-й контур и ориентация ветви совпадает с ориентацией контура;

bij = -1, если j-я ветвь входит в i-й контур и ориентация ветви не совпадает с ориентацией контура;

bij = 0 в остальных случаях.

Приведем пример полной матрицы контуров для вышеприведенного графа.

   1    2   3     4     5    6

Строки полной матрицы контуров обычно линейно зависимы при количестве контуров, большем 1. На практике используют так называемые базовые матрицы контуров.

Базовой матрицей контуров называется каждая подматрица матрицы Вп, состоящая из максимального числа независимых строк.

Из различных базовых матриц при практическом моделировании обычно используют матрицу главных контуров.

3.4.2. Матрица главных контуров

Матрица главных контуров формируется на основе дерева графов. Легко заметить, что и для приведенного графа, и для всякого другого графа добавление к дереву каждой из хорд приводит к образованию единственного контура.

На рис. 5 жирные линии образуют дерево.

Рис. 5. Граф и его дерево

Так, добавление хорды 1 образует контур  1,3,6,5; хорды 4 – 4, 2, 3, 6, 5; хорды 7 – 7, 3, 2.

Каждый контур, определяемый хордой, называется главным. Ориентация каждого главного контура считается определенной стрелкой, устанавливающей ориентацию соответствующей хорды.

Число главных контуров равно числу хорд и равно l-(k-1). Будем присваивать номера контурам с 1 до l-(k-1). Дадим определение матрицы главных контуров, которую будем обозначать через В.

Для направленного графа с k узлами и l ветвями матрицей главных контуров называется матрица, имеющая l-k+1 строк и l столбцов, каждый элемент bij которой определен следующим образом:

bij = +1, если j-ая ветвь входит в i-й главный контур и их ориентации совпадают;

bij = -1, если j-ая ветвь входит в i-й главный контур и их ориентации не совпадают (противоположны); 

bij = 0  в остальных случаях.

Пример.

Изобразим для изображенного на рис. 5 графа матрицу главных контуров.

l-(k-1) = 7-(5-1)=3; l=7;

 

Ниже матрицу главных контуров будем называть матрицей контуров.

МАТРИЦА СЕЧЕНИЙ

 

Матрица сечений необходима для записи 1-го закона Кирхгофа в общем виде. Обратимся к направленным графам и введем понятие "ориентированное сечение".

Сечение называют ориентированным, если ему приписана одна из двух возможных ориентаций.

Рис. 6. Сечение графа

Вначале определим так называемую полную матрицу сечений Dп, которая соответствует всем сечениям графа.

Для направленного графа с l ветвями и р ориентированными сечениями полной матрицей сечений называется матрица Dп, содержащая l столбцов и р строк, каждый элемент dij которой определяется следующим образом:   

dij = +1, если j-ая ветвь входит в i-е сечение и их ориентации совпадают;                    

dij = -1, если j-ая ветвь входит в i-е сечение и их ориентации не совпадают;               

dij = 0  в остальных случаях.

Приведем пример графа и соответствующей матрицы сечения.

Рис.7. Пример графа и матрицы сечения.

Изобразим соответствующую полную матрицу соответствия.

         1     2      3     4  -  номер ветви

 \

 номер сечения

Полезно обратить внимание, что для выбранных ориентированных сечений строки, соответствующие сечениям 1, 2, 3, 4, образуют матрицу инциденций. У матрицы Dп строки обычно являются линейно зависимыми. На практике широко используют не полные матрицы сечений, а так называемые базовые матрицы сечений.

Базовой матрицей сечений называется каждая подматрица полной матрицы сечений, состоящая из максимального числа независимых строк.

Из различных базовых матриц сечений при практическом моделировании, как правило, используют так называемые матрицы главных сечений.

Матрица главных сечений

   Матрица главных сечений формируется на основе дерева графов. Можно доказать, что каждая ветвь дерева определяет единственное сечение, такое, что в это сечение кроме указанной ветви дерева входят только хорды. Каждое такое сечение называется главным. Ориентация этого сечения определяется ориентацией соответствующей ветви дерева.

Если в схеме k узлов, то в дерево войдет k-1ветвь, а значит, имеются главные сечения в количестве k-1. Будем присваивать сечениям номера от 1 до k-1.

Для направленного графа с k узлами и l ветвями матрицей главных сечений D называют матрицу, имеющую k-1 строк и l столбцов, каждый элемент dij которой определен следующим образом:

dij = +1, если j-ая ветвь входит в i-е главное сечение и их ориентации

              совпадают;                           

dij = -1, если j-ая ветвь входит в i-е главное сечение и их ориентации

              противоположны;

dij = 0  в остальных случаях.

Пример.

На рис. 8. в прямоугольниках указанны номера сечений.

В этом случае матрица главных сечений будет иметь следующий вид:

Ниже матрицу главных сечений будем называть матрицей сечений.

3.5.3. Использование матриц сечений для записи 1-го закона Кирхгофа в общем виде

р – количество различных сечений.

С учетом изложенного очевидно, что уравнения системы  не всегда линейно независимы.   

2

           6

     5

4             3

1

2

4

3

Одна

часть эл.схемы

Другая часть эл.схемы

Ветви сечения

EMBED PBrush  

2

1

3

4

1

2

3

Рис. 8. Сечения графа

1

2

3

           1.                            2.    

                                     3.        

         4.       

5.

 

         6.                           7.

Номера ветвей

Номера главных контуров

← Предыдущая
Страница 1
Следующая →

Скачать

202415.doc

202415.doc
Размер: 537 Кб

Бесплатно Скачать

Пожаловаться на материал

Обратимся к направленному графу. При математическом моделировании электронных схем информацию о топологии схемы удобно хранить в виде матрицы инциденций.

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Флобер - создатель объективного романа

Противоречие реализма и антиреализма становится основным противоречием его эстетики. У романа – многозначительный подзаголовок «провинциальные нравы». Омэ Решительно меняется у Флобера понимание счастья.

Процесс внутригрупповой идентификации

Этапы развития межгрупповых отношений. Обмен социально-психологическими отношениями. Регуляция. Персональный уровень разрешения конфликта. Социоцентризм.

Язык, речь и речевая деятельность

Курсовая работа. Теория речевой деятельности. Понятие о языке и речи. Виды и функции речи. Структура и виды речевой деятельности. Понятие, виды, структура речевой деятельности.

Денежный рынок и монетарная политика

Спрос на деньги. Предложение денег и равновесие на денежном рынке. Центральный банк и его функции. Цели и инструменты монетарной политики. Передаточный механизм и эффективность монетарной политики

Грипп и другие ОРВИ (тесты, варианты)

Сохранить?

Пропустить...

Введите код

Ok