8. Понятие гамильтонова графа. Теорема о достаточном условии.

Цикл, который проходит по всем вершинам графа один раз наз. гамильтоновым циклом. Гамильтонова цепь – простая цепь, проходящая по всем вершинам графа.

Т. Если граф G=(X, U, F) содержит наибольшую простую цепь Q=x0U1x1U2x2…xl-1Ulxl длины l, такую, что , тогда в графе G существует гамильтонов цикл.

Док-во:

Докажем с начала существование в графе G простого цикла С длиной l+1, содержащего все вершины цепи Q и только эти вершины.

Т.к. цепь Q – наибольшая и след-то, максимальная, то её вершины x0 и xl могут быть смежны только с вершинами этой же цепи. При l ≥ 3 среди ребер цепи Q обязательно найдется такое ребро U=(xi-1,xi), что вершина xi-1 смежна с xl, а вершина xi с x0. Это следует из того, что Тогда требуемый цикл C состоит из отрезка цепи Q от x0 до xi-1, ребра (xi-1,xl), обращенного отрезка цепи Q от xl до x2 и ребра (xi,x0). Докажем теперь, что найденный цикл явл. гамильтоновым. От противного. Предположим, что цикл С содержит не все вершины графа G. В силу связности графа G имеется такое ребро U, один конец которого принадлежит циклу C, а другой не принадлежит. Заменяя одно из двух ребер цикла C, смежных с ребром U на это ребро U и добавляя вторую кольцевую вершину этого ребра, мы получим простую цепь длины >l, что противоречит условию теоремы. Т.о. цикл C содержит все вершины графа и является гамильтоновым.

Связь между эйлеровыми и гамильтоновыми циклами.

Т. Если граф G – эйлеров, то граф смежностный ему эйлеров и гамильтонов.

Док-во:

В смежностном графе смежность вершины U=(x,y) определяется величиной p(U)=p(x)+p(y)-2

Т.к. вершина U инцидентно четное число ребер. При переходе от графа G к L(G) связность не нарушается, след-но, L(G) – эйлеров. Докажем, что смежностный граф будет гамильтонов. Т.к. исходный граф – эйлеров, то запишем эйлеров цикл в виде:

Cэ=x0U1x1U2x2… xl-1Ulxl, x0=xl. Здесь любые два соседних ребра смежны, след-но при переходе к смежностному графу данный цикл будет являться описанием гамильтонова цикла, т.к. он содержит все вершины L(G) по одному разу.

9. Основные числа теории графов. Свойства цикломатического числа и ранга. Цикломатическое число

Пусть дан граф G=(X, U, F) число вершин – n, ребер – m, p – число компонент связности

J(G)=m-n+p цикломатическое число

χ(G)=n-p – ранг графа

Т. В произвольном графе G число ребер и вершин – положительные числа

Док-во: Если есть исходный граф, он голый. m=0, n=p, χ=0, j=0

Предположим, в графе появилось ребро U1 m=1, n=0, p=n-1, j=o, χ=0-(n-1)=1

Пусть к графу добавляется ещё одно ребро между вершинами, между которыми не было маршрута.

m=2, p=n-2, χ=2, j=0

Предположим, что появилось ещё одно ребро, которое связывает ещё один маршрут. m=3, p=n-2, χ=2, j=1

Т.о. мы доказали:

1. при увеличении числа ребер ранг и цикломатическое число графа не убывает.

2. если ребро добавляется между вершинами, связанными маршрутом, т.е. появляется цикл, то ранг графа не изменяется, а цикломатическое число увеличивается на 1, т.е. цикломатическое число определяет максимальное число независимых циклов в графе (т.е. циклов, каждый из которых содержит хотя бы одно ребро, не входящее ни в один из оставшихся циклов). Цикломатическое число характеризует то минимальное число ребер, которое нужно удалить из графа, чтобы в нем не было ни одного цикла.

m=8, p=1, n=5, j=4