Матричне представлення графів

У випадку великої кількості вершин і дуг рисунок графа перестає бути наглядним. Тому для його задання використовують матриці. Найбільш вживаними в цьому плані є матриці суміжності, інцидентності, шляхів, циклів, перерізів. Більш детально зупинимося на перших трьох видах матриць.

Так для графа з n вершинами матриця суміжності є розмірності , а її елементи задаються формулою

Наприклад, для графа матриця суміжності має вигляд

Матриця інцидентності орієнтованого графа, складається з n стовпчиків і k рядків, де n – число вершин графа, а k – число дуг цього графа (пронумеруємо їх , ,…, ). Елементи матриці знаходяться за формулою:

Для графа

матриця інцидентності має вигляд

Для зв’язного графа, вершини якого перенумеровані, можна побудувати матрицю шляхів S наступним чином: рядки матриці повинні відповідати шляхам з першої вершини в останню, а стовпчики ребрам графа. Відповідно елемент матриці приймає значення 1 або 0 в залежності від того належить ребро графа даному шляху чи ні.

Так для графа

всеможливими шляхами є , , а матриця шляхів має вигляд

Мережі

Розглянемо орієнтовані зв’язні графи, які не мають петель. Їх називатимемо мережами. Оптимізаційні задачі на мережі можна описати наступними типами моделей.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Орієнтовані графи	\|	Мінімізація мережі

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.