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: якщо між  і  немає ребра.


 

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

83179. Анализ природных ресурсов Кемеровской области 94.13 KB
  Кузнецкий бассейн расположен в Западно-Сибирском экономическом районе на территории Кемеровской области. Крайний юг области обширная территория средне-высоких гор Горной Шории. С 1943 центр Кемеровской области. Минерально-сырьевые ресурсы На территории области выявлены полезные ископаемые: уголь каменный бурый и горючие сланцы; чёрные металлы руда железная марганцевая; цветные и благородные металлы руда серебро ртуть свинец цинк медь барит бокситы нефелиновые руды...
83180. Несиметричні короткі замикання 71.15 KB
  Найбільш частим виглядом КЗ є несиметричні КЗ – однофазні, двофазні, двофазні на нейтраль. Вони є граничним випадком несиметричного навантаження. При несиметричних коротких замиканнях сталі струми короткого замикання досягають максимальних значень.
83181. Вентиляция, отопление и кондиционирование воздуха в производственных помещениях 68.08 KB
  Классификация систем кондиционирования. Вот некоторые задачи которые послужат для достижения этой цели: Выяснить значение кондиционирования воздуха. Классифицировать системы кондиционирования воздуха.
83182. Последствия советско-афганской войны 18.28 KB
  Военная служба была обязательна. У мальчиков, которые насчитали 18 или 19 лет возраста, не было выбора, кроме как служить в течение 2 - 3 лет. Новички для Афганистана получили бы 8-10 недели обучения прежде чем быть посланным в их отделения. Это обучение, конечно, не покрывало всю необходимую подготовку.
83183. Моя будущая профессия – инженер-строитель 22.28 KB
  Задачи: Рассмотреть разные профили инженера строителя Раскрыть основные проблемы дорожного строительства Когда мы задумываемся о своей будущей профессии в первую нас интересует ее полезность и практичность. Возьмём сферу дорожного строительства и на её примере рассмотрим основные функции строительства в общем так как из всех сфер строительства нашей...
83184. Франчайзинг товарный и производственный 36 KB
  Итак что же скрывает в себе это слово Под франчайзингом понимается ведение бизнеса под арендованным товарным знаком. Одна из первых успешных франчайзинговых систем была применена компанией Generl Motors. На сегодняшний день можно выделить три основных вида франчайзинга.
83186. Economics in our life 14.92 KB
  Much time was spent by people on the study of economics. This is a very ancient science. It existed even before emergence of electricity, cars and means of communications. But economics as the academic discipline is rather new.
83187. The problems of young people 15.64 KB
  All people have problems. Some people have a lot of problems, others have one or two. And no matter how old you are, you will still face difficulties in your life. We can solve some problems but some problems are very hard to solve.There are a lot of teenagers in our country.