20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

22 чел.

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

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

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

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


 

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

391. Проблемы экономической безопасности России 128 KB
  Ключевые тенденции проблематики экономической безопасности. Прикладные аспекты экономической безопасности. Глобализация как угроза экономическому суверенитету государства. Методика определения ключевых проблем экономической безопасности.
392. Объекты промышленной интеллектуальной собственности 62.5 KB
  Объект интеллектуальной собственности, цели и задачи, на решение которых направлен объект. Сравненительный анализ разработанного объекта и прототипа. Разработка объекта промышленной собственности.
393. Коммуникативная компетенция учителя иностранного языка 96 KB
  Теоретические аспекты формирования коммуникативной компетенции в рамках педагогического процесса. Лингвистическая компетенция как одна из составляющих иноязычной коммуникативной компетенции. Коммуникативная компетенция как новый тип содержания образования в школе.
394. Теория дизайна 222 KB
  История понятие термина дизайн. Промышленный и транспортный дизайн. Колористика и суперграфика. Визуальная идентификация, товарные знаки, визуальные коммуникации и ландшафтный дизайн. Примеры дизайна квартир.
395. Денежная масса и скорость обращения денег 62 KB
  Деньги являются важнейшим атрибутом рыночной экономики. Налично-денежное обращение - движение наличных денег в сфере обращения и выполнение ими двух функций (средства платежа и средства обращения).
396. М.В. Исаковский на Смоленщине 297.56 KB
  Связь биографии поэта с историей народа и страны. Народность песенного творчества М.В. Исаковского. Отражение в лирике М. В. Исаковского черт русского национального характера.
397. Электрический ток в различных средах 333 KB
  Электрический ток в металлах. Носителями зарядов являются положительные ионы и электроны. Рекомбинация заряженных частиц. Самостоятельный электрический разряд. Электрический ток в полупроводниках.
398. Алгоритм микропроцессорного комплекта К580 62.5 KB
  На вход поступает двух проводная линия, по которой поступает параллельный 8-ми разрядный код. Состав кристаллов: ВМ80, ВВ51, ВИ53, ПЗУ/ОЗУ. Посчитать коэффициент преобразования входной величины в выходную.
399. Создание счетчика с произвольным коэффициентом пересчета 101 KB
  Реализовать двоичный вычитающий счётчик с пропуском начальных состояний и коэффициентом пересчёта 10 на RS-триггерах на элементах 1533 серии.