• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Способи задання графів

Графічний опис графів є незручним для їх аналізу на ЕОМ. Тому розглянемо табличні способи задання графів.

Надалі будемо розглядати тільки скінченні графи, у яких множини вершин V = {v₁, …, v_n} і ребер E = {e₁, …, e_m} є скінченними.

Визначення. Матриця суміжності вершин графу G(V) (позначається M(G) = {M_ij}) - це квадратна матриця розміру n´n, в якій M_ij - кількість ребер, які з’єднують V_i з V_j в графі G. Якщо граф G неорієнтований, то

M_ij = M_ji,

тобто матриця М є симетричною.

На рис.2 зображений деякий неорієнтований граф; відповідна матриця суміжності вершин приведена в табл.1.

Рис.2	Таблиця 1

Граф також може бути описаний за допомогою матриці інцидентності (позначається N(G) = {N_ij}), яка має n рядків (вершини) і m стовпців (ребра). Для неорієнтованого графу N_ij = 1, якщо вершина v_i інцидентна ребру e_j; в протилежному випадку - N_ij = 0.

Для орієнтованого графу N_ij = 1, якщо v_i - початкова вершина ребра e_j; N_ij = ‑1, якщо v_i - кінцева вершина ребра e_j; N_ij = 0, якщо вершина v_i не інцидентна ребру e_j.

У табл. 2 наведена матриця інцидентності для неорієнтованого графу, зображеного на рис. 2.

На рис. 3 зображений орієнтований граф, матриця інцидентності для якого наведена в табл. 3.

Неорієнтований граф без петель G може бути також описаний квадратною матрицею суміжності ребер (позначається I(G) = {I_ij}) розміром m´m, причому I_ij = 1, якщо i ¹ j і у ребер e_i і e_j є спільна вершина. В протилежному випаду - I_ij = 0.

Для графу, зображеного на рис. 2, відповідна матриця суміжності ребер приведена в табл. 4.

Таблиця 2

Рис. 3	Таблиця 3
	І	ІІ	ІІІ	IV	V	VI
	-1	-1
			-1
				-1	-1	-1

Таблиця 4

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

1. Безстатеве розмноження, його визначення та загальна характеристика. Спори — клітини безстатевого розмноження, способи утворення і типи спор.
2. Біологічні способи лікування ран.
3. Валютний курс і способи його визначення
4. Варіанти і способи вимірювань характеристик телефонних каналів
5. Види і способи вибіркового спостереження.
6. Види середніх величин та способи їх обрахування.
7. Види середніх величин та способи їх обрахування.
8. Види середніх і способи їх обчислення
9. Види та способи гартування.
10. Види та способи здійснення посягань на територіальну цілісність.
11. Види цивільно-правових договорів в “Руській Правді”, способи їх укладення.
12. Види, форми і способи спостереження.

Переглядів: 1007