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


 

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

85261. ОПРЕДЕЛЕНИЕ СТОИМОСТИ РАБОТ ПО ПОДТВЕРЖДЕНИЮ СООТВЕТСТВИЯ В ЗАКОНОДАТЕЛЬНО РЕГУЛИРУЕМОЙ СФЕРЕ 23.13 KB
  Стоимость работ по подтверждению соответствия конкретного вида продукции, систем качества, систем управления качеством, систем управления окружающей средой, персоналом устанавливается назначенным органом по оценке соответствия согласно с этими Правилами и утверждается их руководством.
85262. УПРАВЛЕНИЕ КАЧЕСТВОМ ПРОДУКЦИИ И УСЛУГ 43.67 KB
  Создание и внедрение системы качества Создание и внедрение системы менеджмента качества в организации предусматривает следующие шаги: признание высшим руководством организации качества как жизненно важного элемента его деятельности; осознание того что разработка системы качества является...
85263. КОНТРОЛЬ РАБОТ (АУДИТ) ПО УПРАВЛЕНИЮ КАЧЕСТВОМ ПРОДУКЦИИ И УСЛУГ 41.29 KB
  Аудит - систематический независимый и задокументированный процесс получения доказательств аудита и объективного их оценивания с целью определения ступени исполнения критерия аудита. Доказательства аудита протоколы изложенные факты или другая информация что является существенной для критериев аудита и может быть проверена.
85264. ПРОГНОЗИРОВАНИЕ УРОВНЯ КАЧЕСТВА ПРОДУКЦИИ 30.55 KB
  Успешная деятельность любой организации возможна лишь в условиях четкого прогнозирования уровня качества продукции и планирования его улучшения. Прогнозирование качества продукции это научно обоснованная информация об уровне качества продукции в будущем.
85265. ПОРЯДОК ПРОВЕДЕНИЯ СЕРТИФИКАЦИИ ПРОДУКЦИ, ПРОЦЕССОВ И УСЛУГ 46.73 KB
  Порядок проведения сертификации продукции в общем случае включает: представление и рассмотрение заявки на сертификацию продукции; анализ предоставленной документации; принятие решения по заявке с указанием схемы модели сертификации; обследование...
85266. ПРОВЕДЕНИЕ СЕРТИФИКАЦИОННЫХ ИСПЫТАНИЙ И КОНТРОЛЬ ЗА ИХ ПРОВЕДЕНИЕМ 64.8 KB
  Сертификационные испытания - элемент системы мероприятий направленных на подтверждение соответствия фактических характеристик продукции требованиям НД с целью получения достоверной информации при взаимоотношениях между изготовителями и потребителями продукции.
85267. СЕРТИФИКАЦИЯ ПЕРСОНАЛА И ИНСПЕКЦИОННЫЙ НАДЗОР 43.51 KB
  Получение сертификата компетентности аудитора является непременным условием для осуществления им работ в области подтверждения соответствия продукции, услуг, систем управления качеством, систем управления безопасностью пищевых продуктов (на основании принципов НАССР), отраслевых систем управления качеством...
85268. Социальное взаимодействие. Социальные движения и изменения 178 KB
  Социальные движения и социальные изменения. Продолжая углублять и развивать социальные связи индивиды вступают в кратковременные соприкосновения в ходе которых они обмениваются какими-либо ценностями материальными предметами информацией и т.
85269. Професійна робота з текстовим та табличним процесорами 1.31 MB
  Засоби автоматизації процесу створення документа. Під час створення текстового документа у Word він автоматично розбивається на сторінки відповідно до тих значень властивостей які встановлені в цьому документі. Сторінка як обєкт текстового документа має такі властивості: розмір сторінки розміри полів...