Например:

Граф G: Граф R:

Граф G – связен.

Граф R – несвязен, в графе R три компоненты связности, R₁ = {1,2,3}, R2 ={4}, R3={5,6,7}.

7. Деревья и остовы. Остовы кратчайших маршрутов.

Дерево – связный граф, не содержащий циклов.

Лес (ациклический граф) – произвольный граф, не содержащий циклов. Компонентами леса являются деревья.

Теорема о дереве (5 различных определений дерева).

1. Граф G – дерево, связный ацикличный граф.

2. Любые две несовпадающие вершины графа G соединены единственной простой цепью.

3. Граф G связен и количество ребер в нем на 1 меньше, чем количество вершин.

4. Граф G ацикличен: q=p-1, p=q+1.

5. Граф G ацикличен, и если любую пару его несовпадающих несмежных вершин соединить ребром е, то полученный граф G+e будет содержать ровно один цикл.

Теорема о висячих вершинах дерева. В любом нетривиальном (p2) дереве имеется, по крайней мере, 2 висячие вершины.

Теорема о центре дерева. Центр любого дерева состоит либо из 1, либо из 2 смежных вершин.

Двоичные деревья (b – деревья) – это деревья, у которых степени любых не концевых вершин равны 2.

Способы обхода деревьев

1. Способ обхода в глубину Поиск в глубину подразумевает просмотр ветвей дерева.

2. Способ обхода в ширину Подразумевает просмотр вершин по ярусам в иерархическом представлении. Здесь под использованием вершины подразумевается просмотр всех «соседей» данной вершины.

Остов (каркас, скелет) графа G – это остовный подграф графа G, задающий дерево на каждой компоненте связности графа G.

Для связного графа остов – это дерево, покрывающее все вершины исходного графа. Очевидно, что в каждом графе существует остов, в общем случае не один. Его можно получить, разрушая циклы в каждой компоненте связности.

Ребра остова Т некоторого графа G называются ветвями, а ребра графа G, не вошедшие в остов называются хордами.

Алгоритмы поиска остовов кратчайших маршрутов

Имеется граф, заданный матрицей весов, т.е. существует G = (V,E), C = ||C_ij||, i, j = , где C_ij  вес ребра, если оно существует. Требуется найти остов с минимальным суммарным весом ребер.

Алгоритм Краскала

Выбирается произвольная вершина графа G.

Упорядочиваем ребра в порядке не убывания их весов.

На каждом шаге пустому графу Ор, где р  количество вершин исходного графа, добавляется ребро с min весом из списка. Добавляемое ребро не должно приводить к образованию цикла. Алгоритм заканчивает работу, если количество ребер в формируемом графе станет равным р – 1.

Алгоритм Прима

Отличается от алгоритма Краскала тем, что на каждом шаге строится не просто граф без циклов, но дерево.

Упорядочиваем ребра исходного графа в порядке не убывания. Строим пустой граф Ор, где р  количество вершин исходного графа.

На каждом шаге в граф Ор добавляем ребро из списка ребер, чтобы не образовался цикл и не должно нарушать связность. Для этого список ребер каждый раз просматривается, начиная с I ребра, и алгоритм начинает остов кратчайших маршрутов посредством разрастания поддерева T с одной вершиной. Поддерево T постепенно разрастается за счет присоединения ребер (x_i, x_j), где вершина x_i  текущему дереву, а x_j  ему не принадлежит и вес ребра (x_j, x_i) наименьший из всех возможных.