20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

33 чел.

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

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

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

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


 

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

7876. Конфликты и их разрешение. Межличностные отношения в группе и коллективе 42.4 KB
  Конфликты и их разрешение. Межличностные отношения в группе и коллективе Конфликты и их разрешение Конфликт - сложное социальное, психологическое явление под которым понимается столкновение противоположных взглядов, действий, интересов различны...
7877. Все мы разные: толерантность 89 KB
  Все мы разные: толерантность Цель:познакомить учащихся с понятием толерантность, с основными чертами толерантной и интолерантной личности Задачи: Обучающая: дать учащимся возможность оценить степень своей толерантности Развиваю...
7878. Сутність та форми використання доказів 22.53 KB
  Сутність та форми використання доказів Всебічна оцінка доказів завершується побудовою висновків у справі та обґрунтуванням рішень, які приймаються щодо використання доказів. Докази використовуються не тільки для формулювання та обгрунтування висновк...
7879. Загальна характеристика елементів процесу доказування 44 KB
  Загальна характеристика елементів процесу доказування Одним із найважливіших завдань сучасної Української держави і суспільства в цілому є забезпечення суворого додержання законності, викорінення будь-яких порушень громадського порядку, ліквідація з...
7880. Збирання доказів при розслідуванні злочинів 104.5 KB
  Збирання доказів при розслідуванні злочинів. Поняття та зміст збирання доказів. Будучи специфічним, процес доказування є особливим різновидом інтелектуальної діяльності суб’єктів розслідування. Найбільш складним її елементом є збирання та фор...
7881. Поняття та зміст оцінки доказів 29.11 KB
  Поняття та зміст оцінки доказів Найважливішим елементом процесу доказування є оцінка доказів. Вона вважається однією із проблем кримінального судочинства і є, як зазначає В.Д. Арсеньєв, душой уголовно-процессуального доказывания. Оцінка дозв...
7882. Перевірка (дослідження) доказів та їх джерел 62.5 KB
  Перевірка (дослідження) доказів та їх джерел Зібрані докази підлягають ретельній, усесторонній та об’єктивній перевірці. Це передбачає вивчення їх джерел, аналіз отриманих доказів і співставлення їх між собою. У силу принципу публічності...
7883. Тактичні проблеми доказування 36.5 KB
  Тактичні проблеми доказування. Тактичні прийоми роботи з доказами. Фактор раптовості, його врахування і використання в доказуванні. Перш ніж розглядати саме тактичні прийоми роботи з доказами, слід зупинитись на співвідношенні процесуального й такти...
7884. Школа и общественное дошкольное воспитание в период восстановления и дальнейшего развития народного хозяйства СССР (1946—1958 гг.) 126.5 KB
  Школа и общественное дошкольное воспитание в период восстановления и дальнейшего развития народного хозяйства СССР (1946 гг.) Еще в ходе Великой Отечественной войны Коммунистическая партия и Советское правительство принимали меры по восста...