20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

24 чел.

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

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

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

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


 

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

50764. Сравнительный анализ растровой и векторной графики 274 KB
  Записать размер каждого полученного файла. Оценить перспективы внедрения графического файла в web-документ. Создать web-страницу с каждым из файлов посмотреть скорость открытия файла. Описать возможности создания Web-страниц непосредственно из самого редактора.
50766. Работа по созданию векторных изображений 427.5 KB
  На страницу с логотипом размещаем 6 кнопокс 1 по 4 ссылки на конкретные страницы 5Вперед 6Назад Задание 4 Организуем гиперсвязь главной страницы с 4 второстепенными.
50767. Программное обеспечение для работы с векторными изображениями 460 KB
  Достигнув края экрана надпись появляется снова с противоположной стороны SLIDE Схоже с SCROLL но текст перемещается только один раз и останавливается DIRECTION=DOWN LEFT RIGHT UP Определяет направление скроллинга DOWN Движение вниз LEFT Движение справа налево. По умолчанию RIGHT Движение слева направо UP Движение вверх 3D объекты.
50769. Создание динамических Web-страниц 31.5 KB
  Цель: Научиться создавать динамические web-страницы. Разобрать на примерах их достоинства и недостатки. Создадим шаблон страницы следующего вида.
50770. Использование динамических переменных 27.5 KB
  Цель: Научиться использовать переменные разных типов. Задание 1. Создадим первую типовую программу на PHP
50771. Программирование циклов в РНР 31.5 KB
  Цель: Научиться использовать различные циклы. Задание 1. Проверить работоспособность кода программ из 3 примеров.
50772. Работа с массивами РНР 25.5 KB
  Цель: Научиться использовать массивы при написании программ. Разобрать особенности каждого вида массивов. Задание 1. Создать массив A 1-10 из десяти целых чисел.