Ноу Інти, лекція, графи і дерева

зважені графи

Зважений (інша назва: розмічений) граф (або орграф) - це граф (орграф), деякими елементами якого (вершин. Ребрах або дуг) зіставлені числа. Найбільш часто зустрічаються графи з позначеними ребрами. Числа-позначки носять різні назви: вага. довжина. вартість.

Зауваження. Звичайний (невиважених) граф можна інтерпретувати як зважений, все ребра якого мають однакову вагу 1.

Довжина шляху в зваженому (зв'язковому) графі - це сума довжин (ваг) тих ребер, з яких складається шлях. Відстань між вершинами - це, як і раніше, довжина найкоротшого шляху. Наприклад, відстань від вершини a до вершини d в підвішеному графі. зображеному на рис. 11.7. дорівнює 6.

Мал. 11.7. зважений граф

N - периферія вершини v - це безліч вершин. відстань до кожної з яких (від вершини v) не менше, аніж N.

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

Існує досить велика кількість різноманітних способів представлення графів. Однак ми викладемо тут тільки найкорисніші з точки зору програмування.

Матриця суміжності

Матриця суміжності Sm - це квадратна матриця розміром NxN (N - кількість вершин в графі), заповнена одиницями і нулями за таким правилом:

Якщо в графі є ребро e. з'єднує вершини u і v. то Sm [u, v] = 1. в іншому випадку Sm [u, v] = 0.

Зауважимо, що дане визначення підходить як орієнтованим, так і неорієнтованим графам. матриця суміжності для неорієнтованого графа буде симетричною щодо своєї головної діагоналі, а для орграфа - несиметричною.

Задати зважений граф за допомогою матриці суміжності теж можливо. Необхідно лише внести невеликі зміни в визначення:

Якщо в графі є ребро e. з'єднує вершини u і v. то Sm [u, v] = ves (e). в іншому випадку Sm [u, v] = 0.

Це добре узгоджується з зауваженням, зробленим в попередньому пункті: незважений граф можна інтерпретувати як зважений, все ребра якого мають однакову вагу 1.

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

Як приклад наведемо матриці суміжності для трьох графів. зображених на рис. 11.5. Мал. 11.6 і рис. 11.7 (див. Рис. 11.8).

Таблиця 11.8. Приклади матриць суміжності