20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

29 чел.

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

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

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

Матриця суміжності графа 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: якщо між  і  немає ребра.


 

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

17341. ЕКОНОМІЧНІ КОНЦЕПЦІЇ СОЦІАЛ-ДЕМОКРАТІЇ 199 KB
  ЕКОНОМІЧНІ КОНЦЕПЦІЇ СОЦІАЛДЕМОКРАТІЇ Соціалдемократичний рух в економічному та політичному відношенні є нині досить впливовою силою яка значною мірою визначає напрями сучасного розвитку різних держав світу. Історія його формування тісно звязана з еволюцією
17342. РАДЯНСЬКА ЕКОНОМІЧНА НАУКА 192.5 KB
  РАДЯНСЬКА ЕКОНОМІЧНА НАУКА 1. Основні етапи становлення й розвитку економічної науки в СРСР Сучасна світова економічна думка формувалась обєднуючи різноманітні напрямки економічного знання. Вона синтезувала досягнення цілих поколінь добираючи раціональне та в
17343. Введение в курс Системное проектирование телекоммуникационных систем 87 KB
  Лекция 1. Введение в курс Системное проектирование телекоммуникационных систем 1.1.Общее понятие о системном проекте и системном подходе к проектированию сложных объектов Данная университетская дисциплина Системное проектирование телекоммуникационных систем отн...
17344. ЭЛЕМЕНТЫ ОБЩЕЙ ТЕОРИИ СИСТЕМ 181 KB
  ЭЛЕМЕНТЫ ОБЩЕЙ ТЕОРИИ СИСТЕМ Лекция №2 Основания общей теории систем 1.1. Уровни исследования системы Во второй половине двадцатого столетия в биологии медицинской науке и философии основательно укоренилось словосочетание: Общая теория систем [15] котор...
17345. Сложный объект как система. Основные аспекты системного исследования 136.5 KB
  Тема 2. ЭЛЕМЕНТЫ ОБЩЕЙ ТЕОРИИ СИСТЕМ Лекция 3. 2.4. Сложный объект как система Основные аспекты системного исследования Несколько нарушая принятую методологию изложения материала начнем с определения объекта Ob как потенциально сложного элемента системы. Сложный ...
17346. Научные (Теоретические) основы системного похода 136.5 KB
  Тема 2. Научные Теоретические основы системного похода Продолжение. Лекция 4 3.5 Основные принципы системного подхода Основные принципы системного подхода вытекают из соответствующих главных концепций ОТС представленных схеме на рис.1. ...
17347. Системобразрушающие факторы 109.5 KB
  Тема 2. Научные Теоретические основы системного похода Продолжение 2. Лекция 5 3.10.Системобразрушающие факторы Как указывалось выше распад целостных объектов происходит под влиянием внешних системоразрушающих факторов. Горы могут быть разрушены землетрясение
17348. ПРОЦЕСС УПРАВЛЕНИЯ В СЛОЖНОЙ СИСТЕМЕ 214.5 KB
  Лекция 6. ПРОЦЕСС УПРАВЛЕНИЯ В СЛОЖНОЙ СИСТЕМЕ 1. Концептуальная структура системы с управлением Как было ранее отмечено в классификации систем выделяется класс систем с управлением. Для таких систем характерно наличие свойства открытости и способность к адекватно...
17349. ЭЛЕМЕНТЫ ОПИСАНИЯ СЛОЖНЫХ СИСТЕМ. МОДЕЛЬНОЕ ОБЕСПЕЧЕНИЕ АНАЛИЗА СС. ОБОБЩЕННАЯ (СЕМАНТИЧЕСКАЯ) МОДЕЛЬ ПРИКЛАДНОЙ СИСТЕМЫ 270 KB
  Лекция 7. ЭЛЕМЕНТЫ ОПИСАНИЯ СЛОЖНЫХ СИСТЕМ. МОДЕЛЬНОЕ ОБЕСПЕЧЕНИЕ АНАЛИЗА СС. ОБОБЩЕННАЯ СЕМАНТИЧЕСКАЯ МОДЕЛЬ ПРИКЛАДНОЙ СИСТЕМЫ. I. 1. Показатели параметры в описании элемента системы Элементу объекта системы поставим в соответствие систему показателей парам...