20503

Матриця суміжності та матриця інцидентності

Доклад

Информатика, кибернетика и программирование

Матриця суміжності графа G зі скінченною кількістю вершин n пронумерованих числами від 1 до n це квадратна матриця A розміру n в якій значення елементу aij рівне числу ребер з iї вершини графа в jу вершину. Матриця суміжності простого графа що не містить петель і кратних ребер є бінарною матрицею і містить нулі на головній діагоналі. Матриця суміжності неорієнтованого графа симетрична а значить володіє дійсними власними значеннями і ортогональним базисом з власних векторів.

Украинкский

2013-07-25

28 KB

31 чел.

Матриця суміжності та матриця інцидентності

Матриця суміжності

Матриця суміжності — один із способів представлення графа у вигляді матриці.

Матриця суміжності графа G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графа в j-у вершину.

Іноді, особливо у разі неорієнтованого графа, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.

Матриця суміжності простого графа (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.

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

Два графи G1 і G2 з матрицями суміжності A1 і A2 є ізоморфними якщо і тільки якщо існує матриця перестановок P, така що PA1P-1 = A2.

З цього випливає, що матриці A1 і A2 подібні, а значить мають рівні набори власних значень, визначників і характеристичні многочлени. Проте зворотне твердження не завжди вірне — два графи з подібними матрицями суміжності можуть бути неізоморфними.

Матриця суміжності і списки суміжності є основними структурами даних, що використовуються для представлення графів в комп'ютерних програмах.

Використання матриці суміжності переважно тільки у разі нерозріджених графів, з великим числом ребер, оскільки вона вимагає зберігання по одному біту даних для кожного елементу. Якщо граф розріджений, то велика частина пам'яті марно буде витрачатися на зберігання нулів, зате у разі нерозріджених графів матриця суміжності достатньо компактно представляє граф в пам'яті.

матриця інцидентності

Ма́триця інциде́нтності — одна з форм представлення графа, в якій вказуються зв'язок між інцидентними елементами графа (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки — вершин. Ненульове значення у клітинці матриці вказує на зв'язок між вершиною і ребром (їх інцедентність).

Кожна комірка матриці може набувати трьох значень:

1: якщо ребро виходить з  і входить у ;

-1: якщо ребро входить у  і виходить з ;

0: якщо між  і  немає ребра.


 

А также другие работы, которые могут Вас заинтересовать

54122. Сценарій позаурочного заходу для 5 класу «Різнобарвна книга життя і творчості Маршака» 88.5 KB
  Крім того запропоновані у сценарії твори Маршака дають змогу відпрацьовувати прийоми художнього читання віршів допомагають розвиткові естетичного чуття учнів. Сценарій позаурочного заходу для 5 класу Різнобарвна книга життя і творчості Маршака Мета: закріпити уявлення про багатогранність таланту Самуїла Яковича Маршака дати знання про основні віхи його біографії розвивати творче сприйняття художньої літератури естетичний смак прищеплювання навички вдумливого прочитання поезії і виразного виконання виховувати духовну культуру...
54123. Самомасаж та сучасні методи корекції, оздоровлення та загартування дітей дошкільного віку 38 KB
  Розвивати гнучкість спритність навички самомасажу а також слухову рухову зорову пам'ять мовленнєве дихання. А щоб з нами цього не трапилося ми будемо виконувати точковий масаж який допоможе стати вам здоровими. Почнемо масаж з носика: аВказівні пальчики поставили в ямочки які знаходяться під носиком і робимо кругові рухи.
54124. Машинобудування. Загальна характеристика. Важке та транспортне машинобудування 34.5 KB
  Мета: сформувати знання про значення місце машинобудування у господарстві держави його галузеву і територіальну структуру; пояснити чинники розміщення підприємств галузі; формувати навички роботи з економічними картами; виховувати економічну культуру та економічне мислення Очікувані результати: учень називає галузевий склад машинобудування; пояснює роль галузі в господарстві держави; характеризує галузі машинобудування та чинники їх розміщення; показує на карті великі центри окремих галузей...
54125. Масленица 402 KB
  Ход праздника Масленица - это проводы зимы встреча весны. 1 чтец К нам сюда скорее просим приходи честной народ Фейерверки зажигайте всех нас масленица ждёт 2 чтец Люди Велено до вас довести такой указ: Заготовленный самой нашей матушкой-зимой 1 чтец Каждый год сего числа как гласит указник Людям города села выходить на праздник Чтецы хором Спешите увидеть спешите смотреть спешите скорее на праздник успеть Колокольный звон Скоморох 1. Что встречает масленица Весну А что провожает Зиму Что является символом масленицы...
54126. Масляна. Сценарій виховного заходу 67 KB
  Святково одягнені в українські національні костюми діти збираються в рекреаційній залі школи. Починається дійство Діти стукають у двері Зими але ніхто не відповідає. Як же нам бути Чи підкоримось Зимі Чи не злякались ви її погроз Знаєте діти мені стало сумно від думки що я ніколи не побачу як пробуджується наша Матінка Земля від довгого зимового сну як зеленітимуть її луки горбочки. А ви діти хочете щоб на землі завжди була зима Діти: Ні не хочемо Ведуча: То що ж нам робити Може будемо штурмом брати цю фортецю і...
54127. Активізація пізнавальної діяльності при викладанні дисципліни «Автомобільні перевезення» з використанням інтерактивних технологій навчання 242.5 KB
  Однією з умов запоруки успіху в підготовці конкурентоспроможних фахівців є застосування інтерактивних форм навчання з метою активізації пізнавальної діяльності студентів. У Донецькому індустріальному технікумі широко застосовуються інтерактивні навчальні технології які забезпечують інтенсифікацію...
54128. МОДЕЛЮВАННЯ СУЧАСНОГО ЕФЕКТИВНОГО УРОКУ УКРАЇНСЬКОЇ ЛІТЕРАТУРИ 190.5 KB
  У застосуванні методів навчання треба бути обережним інакше ефективний урок може перетворитися на ефектний. Павленко Питання моделювання ефективного уроку є надзвичайно актуальним для сучасних педагогів що працюють в умовах особистісно орієнтованого підходу запроваджують інноваційні технології.Опрацювати методи і прийоми що...
54129. Хто працює, той і має. Майстер-клас 351.5 KB
  Українська мова Корінь слова. Спільнокореневі слова. формувати в учнів уявлення про спільнокореневі слова корінь на основі споріднених слів; розвивати вміння виділяти споріднені слова виділяти спільну частину; збагачувати словниковий запас учнів; розвивати вміння спостерігати аналізувати зіставляти; виховувати акуратність уважність у роботі. Які виросли паростки діти називають Що спільного з словом лісце корінь тому вони і називаються спільнокореневі слова.
54130. СЦЕНАРИЙ РАЙОННОГО СЕМИНАРА ФИЗИКОВ 89.5 KB
  Смещение акцентов с содержания обучения на процесс учения выражающийся в активной познавательной деятельности школьников и в овладении ими рациональными способами этой деятельности; Создание для каждого ученика возможности реализовать свою потребность в познании и в творческой деятельности; Ориентация на овладение учащимися общекультурными ценностями коммуникативной информационной культурой культурой деятельности. Деятельностный подход к обучению предполагает что...