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

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

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

Для направленного графа с 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. На практике используют так называемые базовые матрицы контуров.

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

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

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

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

Подпись: 2,Подпись: 3

На рис. 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;

Выноска 2: Номера ветвей
 

Выноска 3 (граница и черта): Номера главных контуров 

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

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

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

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

 

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

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

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

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

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




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

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

 
 

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

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

номер ветви

\

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

Полезно обратить внимание, что для выбранных ориентированных сечений строки, соответствующие сечениям 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-го закона Кирхгофа в общем виде

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

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



Подпишитесь на рассылку:

Проекты по теме:

Основные порталы, построенные редакторами

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: • АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика
История: СССРИстория РоссииРоссийская Империя
Окружающий мир: Животный мирДомашние животныеНасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организации
МуниципалитетыРайоныОбразованияПрограммы
Отчеты: • по упоминаниямДокументная базаЦенные бумаги
Положения: • Финансовые документы
Постановления: • Рубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датам
Регламенты
Термины: • Научная терминологияФинансоваяЭкономическая
Время: • Даты2015 год2016 год
Документы в финансовой сферев инвестиционнойФинансовые документы - программы

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШколаПрофессиональное образованиеМотивация учащихся
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказ
Регионы РоссииПрограммы регионовЭкономика

Бизнес и финансы

Бизнес: • БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумаги: • УправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги - контрольЦенные бумаги - оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудит
Промышленность: • МеталлургияНефтьСельское хозяйствоЭнергетика
СтроительствоАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства

Блокирование содержания является нарушением Правил пользования сайтом. Администрация сайта оставляет за собой право отклонять в доступе к содержанию в случае выявления блокировок.