fy"> (n, m) - граф з k компонентами зв'язності. Якщо G - не ліс, то в ньому (його компонентах зв'язності) існують цикли. Розглянемо небудь цикл і видалимо з нього деякий ребро. При цьому количест?? Про компонент зв'язності не збільшиться. Якщо після цього ще залишаться цикли, то розглянемо наступний з них і знову видалимо-яке його ребро. Продовжимо цей процес до тих пір, поки не зникнуть всі цикли. Отриманий в результаті подграф, який, очевидно, є лісом і має стільки ж компонент зв'язності, як і вихідний граф G , називається остовом графа G .
Теорема. Число ребер графа G , які потрібно видалити для отримання остова, не залежить від способу видалення і одно m-n + k .
Теорема (Кірхгоф). Число кістяків в зв'язковому графі G порядку n>=2 одно алгебраическому доповненню будь-якого елемента матриці Кирхгофа K (G) графа G .
Теорема. Орграф сильно зв'язний, якщо в ньому існує основний циклічний маршрут.
5. Рішення оптимізаційних задач
Алгоритм Дейкстри.
Алгоритм Дейкстри - алгоритм на графах, винайдений нідерландським ученим Е. Дейкстрой в 1959 році. Знаходить найкоротша відстань від однієї з вершин графа до всіх інших. Алгоритм працює тільки для графів без ребер негативного ваги. Алгоритм широко застосовується в програмуванні і технологіях, наприклад, його використовують протоколи маршрутизації OSPF і IS-IS.
Алгоритм Дейкстри вирішує задачу про найкоротших шляхах з однієї вершини для зваженого орієнтованого графа G=(V, E) з вихідною вершиною s , в якому ваги всіх ребер ненегативні ( (u, v)? 0 для всіх (u, v) E ).
Приклад рішення задачі. Пошук ведеться на даному графі ( Рис. 3.1 ). Ваги відповідають довжині ребер.
Лістинг 2.
networkx as nxmatplotlib.pyplot as plt
G=nx. DiGraph () # Оголошуємо орграф G
G.add_nodes_from (range (1, 7)) # Додаємо вершини з набору чисел (1 .. 7)
for i in range (1,10):. add_edge (i, i - 1) # Додаємо ребро, що з'єднує вершину i з i - 1i in range (1,10): (i +5 < ; 10):. add_edge (i, i +5, weight=i * 0.5 +2) # Встановлюємо ваги на ребра
nx.draw (G, node_color=«m», font_color=«w»). show () (nx.dijkstra_path (G, 2, 8)) # Пошук і висновок масиву вершин
# Використання функції для знаходження маршруту. Пошук починається з вершини 2 і йде до вершини 8.
Вихідні дані:
[2, 1, 6, 5, 4, 3, 8]
Алгоритм пошуку.
0. G - даний орієнтований граф з зваженими ребрами. Потрібно знайти найкоротші шляхи з вершини s в усі інші вершини графа G .
. (Початок). Покласти la...
