Цикломатика графов

Свойства графов, которые мы будем изучать в данной главе, присущи графам общего вида и не зависят от ориентации.

4.1. Цикломатическое число

Определение

Цикловые ребра и перешейки
Назовем ребро цикловым, если оно содержится хотя бы в одном цикле; в противном случае назовем его перешейком (bridge).
Точкой сочленения (шарниром) называется вершина, при
удалении которой число компонент увеличивается.

Свойства цикломатического числа

4.2. Деревья

Определения
Связный граф без циклов называется деревом (tree). Висячие вершины дерева называются листьями (leaf - leaves).
Граф, все компоненты связности которого – деревья, называется лесом (forest).

Свойства дерева

Свойство 5. Добавление ребра (разумеется, без добавления
вершины) приводит к увеличению λ на единицу,
то есть к появлению цикла.
Свойство 6 проверяется непосредственно: все вершины дерева,
кроме висячих, являются точками сочленения.
Свойство 7. В любом графе с числом вершин ≥2 есть по крайней
мере две вершины, не являющиеся точками сочленения.
Для дерева это висячие вершины.

4.3. Каркасы

Определение
Каркас связного графа является деревом.

Алгоритм нахождения каркаса
Алгоритм является модификацией волнового алгоритма нахождения кратчайшей цепи.
Шаг 1. Выберем произвольную вершину и пометим ее меткой 0.
Шаг 2. Все непомеченные вершины, смежные с вершинами, имеющими метку k, помечаем меткой k + 1. Разметка продолжается
до тех пор, пока все вершины не будут помечены. При такой разметке метки смежных вершин не могут отличаться более чем на
единицу.

Пример
0
1
1
2
2
2
2
3

Кратчайший каркас графа

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

Robert C. Prim (b. 1921) along with coworker Joseph Kruskal developed two different algorithms (see greedy algorithm) for finding a minimum spanning tree in a weighted graph, a basic stumbling block in computer network design. His self-named algorithm, Prim's algorithm, was originally discovered in 1930 by mathematician Vojtěch Jarník and later independently by Prim in 1957. It was later rediscovered by Edsger Dijkstra in 1959. It is sometimes referred to as the DJP algorithm or the Jarník algorithm
en.wikipedia.org/wiki/Robert_C._Prim

f
a
b
c
d
e
g
h
4
3
2
7
8
6
8
1
3
3
9
5
9
0
2↑
3←
4↙
2↑
6←
3←
4↙
8↖
1↑
1↑
9
3↙
3←
3↙
3←
5←
7↖
5←
5←
Пример

Теорема о хорде каркаса

Пример

Эта теорема имеет два полезных следствия.
Во- первых, она дает возможность перебирать каркасы.

Во-вторых, она утверждает, что число независимых циклов в графе равно цикломатическому числу.

Каждому суграфу G ’=(V,E ’) графа G=(V,E) взаимно однозначно
соответствует подмножество ребер E ’⊆E ; каждое E ‘ задается
вектором
,
у которого
Далее суграфом называют и E ‘, и
0⊕0=0, 1⊕0=1, 0⊕1=1, 1⊕1=0

Однореберные суграфы
линейно независимы, а любой суграф есть их линейная комбинация
=
Пример: сумма суграфов (1,1,0,1) ⊕(1,0,1,1)=(0,1,1,0)

В этом разделе цикл определяется как суграф, все вершины ко-
торого имеют четные валентности. Сумма двух циклов есть цикл
(не обязательно цикл в обычном понимании: это могут быть два
цикла без общих вершин). Множество циклов образует линейное
пространство.
Пусть теперь T -- некоторый каркас графа G. Каждой хорде этого
каркаса поставим в соответствие тот единственный цикл, который
она образует вместе с некоторыми ребрами T, и тем самым полу-
чим систему из λ(G ) циклов. Элементы этой системы линейно не-
зависимы и образуют базис пространства циклов размерности λ(G ).
Любой другой цикл может быть получен как линейная комбинация
независимых (базисных) циклов.