різні, називається простим циклом.
5. Ступінь вершини - число ребер, яким інцидентна вершина V, позначається D (V).
.2 Способи завдання графа
Нехай G (V, E) - зв'язний неорієнтовані граф, кожному ребру якого приписаний деякий вага відмінний від 0 (рис. 1). Існують різні способи завдання графа: у вигляді матриці ваг, матриці суміжності або інцидентності, списку ребер. Кожен з цих способів має свої переваги і недоліки. br/>
E2 E4 E5
E3
E1 E7
E6
E8
E9
Рис. 1 В«Приклад неорієнтованого графаВ»
Матрицею ваг називається квадратна матриця розмірності nхn (n-кількість вершин), елемент якої стоїть в i рядку і j стовпці визначається за правилом:
В
Матриця суміжності - це булева матриця (іноді її називають двійковій або бітової) порядку n: R = | | r [ij] | |, в якій рядках і стовпчиках поставлені у відповідність вершини графа G, і r [ij] = 1, якщо вершини vi, vjV суміжні, і r [ij] = 0 в іншому випадку. Так для неорієнтованого графа, представленого на рис. 1, матриця суміжності має вигляд таблиці 1. br/>
Таблиця 1. В«Матриця суміжностіВ»
V1V2V3V4V5V6V70110001V11010000V21110101V30000000V40010001V50000001V61010110V7
Матриця інцидентності - це також булева матриця Q = | | q [ij] | | розміру nxm, в якій рядками поставлені у відповідність вершини графа, а стовпцями - ребра. Якщо граф - неорієнтований, то матриця інцидентності такого графа є булевої матрицею, в якій q [ij] = 1, якщо вершина vi інцидентна ребру еj, і q [ij] = 0 в іншому випадку. Так для неорієнтованого графа, представленого на рис. 1, матриця інцидентності має вигляд, як у таблиці 2.
Таблиця 2. В«Матриця інцидентностіВ»
Якщо граф G є розрідженим, тобто число ребер m значно менше величини (число ребер повного графа
),
то ефективним поданням графа є список його ребер , що задається парами вершин. Для цього формують два масиви: (, ...,) і (, ...,). Кожен елемент в масиві є мітка вершини, а ie ребро графа виходить з вершини. Наприклад неорієнтовані граф, представлений на рис. 1 буде представлений наступними двома масивами:
g = (1, 1, 1, 2, 2, 3, 3, 3, 3, 5, 5, 6, 7)
h = (2, 3, 7, 1, 3, 3, 1, 5, 7, 3, 7, 7, 6)
1.3 Сильна зв'язність графів
На практиці часто виникають завдання у знаходженні сильно зв'язкових ...
