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


 

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

19207. Движение в неоднородном магнитном поле 333 KB
  Лекция № 3. Движение в неоднородном магнитном поле. Дрейфовое приближение условия применимости дрейфовая скорость. Дрейфы в неоднородном магнитном поле. Адиабатический инвариант. Движение в скрещенных электрическом и магнитном полях. Общий случай скрещенных поля л...
19208. Аналогия световой и электронной оптики. Электронная оптика параксиальных пучков 735 KB
  Лекция № 4. Аналогия световой и электронной оптики. Электронная оптика параксиальных пучков. Движение заряженных частиц в аксиальносимметричном электрическом поле. Основные типы электростатических линз. IV. Электронная оптика. 4.1. Аналогия световой и электрон
19209. Движение заряженных частиц в аксиально-симметричном магнитном поле. Магнитные линзы 412.5 KB
  Лекция № 5. Движение заряженных частиц в аксиальносимметричном магнитном поле. Магнитные линзы. Фокусировка короткой катушкой. Магнитные квадрупольные линзы жесткая фокусировка. Магнитные электронные микроскопы. Аберрация электронных линз. V. Магнитные линзы. ...
19210. Ограничение тока пространственным зарядом в диоде. Формула Ленгмюра и Богуславского для плоских и цилиндрических электродов 325.5 KB
  Лекция № 6. Ограничение тока пространственным зарядом в диоде. Формула Ленгмюра и Богуславского для плоских и цилиндрических электродов. Учет начальных скоростей частиц. Образование виртуального катода. Предельная плотность тока пучка частиц в пролетном промежутке
19211. Расхождение пучков заряженных частиц под действием собственного объемного заряда 421.5 KB
  Лекция № 7. Расхождение пучков заряженных частиц под действием собственного объемного заряда. Прямолинейные пучки электронных лучей электронные пушки Пирса. VII. Формирование электронных и ионных пучков. 7.1. Расплывание пучков заряженных частиц под действи
19212. Электромагнитные ускорители плазмы. МГД приближение для описания динамики 269 KB
  Лекция 8 VIII. Плазменные ускорители. Электромагнитные ускорители плазмы. МГД приближение для описания динамики. Одножидкостная модель. Магнитное давление. Равновесие плазменной границы. Рельсотрон. 8.1. МГД приближение. Для описания ускорения плазмы магни...
19213. Термоэлектронная эмиссия. Статистический и термодинамические вывод формулы плотности тока термоэлектронной эмиссии 557.5 KB
  Лекция № 9. Термоэлектронная эмиссия. Статистический и термодинамические вывод формулы плотности тока термоэлектронной эмиссии. Влияние внешнего электрического поля Эффект Шоттки. Распределение термоэлектронов по энергиям. Средняя энергия термоэлектронов. Эксп
19214. Влияние поверхностной неоднородности материала катода на термоэмиссию 557 KB
  Лекция № 10. Влияние поверхностной неоднородности материала катода на термоэмиссию. Пленочные катоды. Оксидные катоды. Автоэлектронная эмиссия. Изменение температуры эмиттера при термо и автоэлектронной эмиссии. 9.7. Влияние поверхностной неоднородности материала...
19215. Фотоэлектронная эмиссия. Законы Столетова и Эйнштейна. Теория фотоэмиссии 476 KB
  Лекция № 11. Фотоэлектронная эмиссия. Законы Столетова и Эйнштейна. Теория фотоэмиссии. Кривая Фаулера. Применение фотоэмиссии в технике. Фотокатоды. XI. ФОТОэлектронная эмиссия. 11.1. Законы фотоэффекта. В широком смысле фотоэффект – это возникновение или измене