20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

21 чел.

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

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

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

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


 

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

4079. Исследование качества полированной поверхности с помощью микроинтерферометра Линника 788.5 KB
  Цель работы – знакомство с явлением интерференции света и с его использованием в метрологии. Получение практических навыков работы с высокоточным измерительным оптическим прибором и определение качества полированной поверхности исследуемого обр...
4080. Исследование интерференции света и определение длины волны используемого излучения 247.5 KB
  Цель работы - изучение методов наблюдения интерференционной картины и измерения ее параметров, определение длины волны используемого излучения. Приборы и принадлежности Оптическая скамья. Лазер. Бипризма Френеля. Линзы. ...
4081. Обработка результатов физического эксперимента 391.5 KB
  Цель работы – ознакомление с методами оценки результатов измерений и расчета погрешностей. Приборы и принадлежности: исследуемые образцы штангенциркуль микрометр лабораторная установка FPM - 01 пакет компьютерных программ по моделированию...
4082. Изучение центрального абсолютно упругого и неупругого соударения шаров 749 KB
  Цель работы - изучение центрального абсолютно упругого и неупругого соударения шаров. Исследование упругого соударения шаров Физические закономерности, возникающие при ударе двух тел, широко используются в науке и технике, например, при ковке металл...
4083. Изучение равноускоренного движения на машине Атвудаи ее компьютерной модели 1.03 MB
  Дана методика и описаны эксперименты по проверке основных формул кинематики и динамики равноускоренного прямолинейного движения. Эксперименты могут быть проведены как на реальной лабораторной установке (машине Атвуда), так и на ее компьютерной модел...
4084. Изучение вращательного движения с помощью маятника Обербека и его компьютерного имитатора 183.5 KB
  Изложены основные положения кинематики и динамики твердого тела. Приведена методика и описан эксперимент по проверке основного закона динамики вращательного движения. Эксперимент может быть выполнен как на реальной лабораторной установке (маятнике ...
4085. Определение коэффициента трения с помощью установки ФПМ-02 и ее компьютерного имитатора 646 KB
  Цель работы: изучить свободные затухающие колебания наклонного маятника освоить методику определения коэффициента трения. Приборы: установка для определения коэффициента трения ФПМ-02, а также IBM-совместимый персональный компьютер и пакет компьют...
4086. Определение энергетических характеристик электрической цепи постоянного тока 5.08 MB
  Цель работы – исследование зависимости энергетических характеристик электрической цепи от внешнего сопротивления. Приборы и принадлежности: лабораторный комплекс ЛКЭ-2П, включающий источник тока, мультиметр, магазин сопротивлений и комплект сое...
4087. Определение изменения энтропии при плавлении олова 127.5 KB
  Цель работы – изучение процессов плавления и кристаллизации олова и определение изменения энтропии. Теплоемкость твердых тел Теплоемкостью твердого тела называется величина, равная отношению количества теплоты Q, погл...