2

Определения

.3.3. Инварианты

Пусть f- функция, относящая каждому графуGнекоторый элементf(G) из множества М произвольной природы.

Эта функция показывается инвариантом, если на изоморфных графах её значение совпадают, т.е. для любыхGиG’ из изоморфизма графовGиG’ следуетf(G)=f(G’).

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

Во многих случаях инварианты имеют всего два значения, 0 и 1 . Значение 1 показывает, что это свойство у графа имеется, а 0 – что это свойство отсутствует. К таким инвариантам относятся:

• связность,

• планарность,

• является ли граф деревом,

• является ли граф двудольным

и т.д.

Другую группу составляют инварианты, равные натуральным числам:

• число вершин и рёбер;

• степень вершин;

• последовательность степеней вершин;

• число компонент связности;

• хроматическое число;

• наличие пути заданной длины;

• наличие гамильтонова цикла;

• число связных компонент

и т.д.

К сожалению, нет универсального алгоритма определения изоморфизма для всех графов по одному инварианту.

Определения

Система инвариантов называется полной системой инвариантов, если из того, что для некоторых двух графов эти инварианты принимают одинаковые значения, следует, что данные графы изоморфны.

Системы инвариантов существуют, но их нахождение является сложнейшей задачей.

2.5. Прогулки, тропы, пути и циклы

Определения

Прогулкой (wаlk) (или [V₀-V_m]-прогулкой) в графеG=(V,E) называется последовательность чередующихся вершин и рёбер (V₀,e₁,V₁,e₂,V₂,e₃,V₃…e_m,V_m), в которой е_i= {V_i-1,V_i} для 1 i k.

Для прогулки нет требования отсутствия повторения вершин и /или ребер. Однако если ввести это требование, то получим особые определения:

Тропа(trail) – это прогулка, в которой запрещены повторы рёбер.

Путь(path) – это прогулка, в которой запрещены повторы вершин.

Из выше приведённых определений можно сделать следующие выводы:

• каждый путь есть тропа, и каждая тропа есть прогулка;

• имеются прогулки, которые не будут тропами, и тропы, которые не будут путями.

Прогулка или тропа будут замкнутыми, если они их концевые вершины совпадают.

Пусть xиyбудут вершинами графаG. Тогда можно говорить о(x-y)-прогулке, (x-y)-тропе или(x-y)-пути, которые имеют концевые вершиныxиy.

Теорема

Если граф Gимеет (x-y)-прогулку, то он имеет (x-y)-путь.

Меры

• 

• длина прогулки (тропы или пути) d(u,v) – число ребер, входящих в прогулку

(тропу, путь) с начальной вершиной uи конечной вершинойv.

• расстояниеdist(u,v) между двумя вершинамиuиv. Определяется как длина

минимального путимежду этими вершинами.

Класс сложности

Нахождение минимального (кратчайшего) пути между двумя вершинами простого графа требует линейного времени.

Алгоритм

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

Теорема

Пусть G=(V,E) будет графом сnвершинамиv₁,v_{2, …,}v_nи матрицей смежности А. Тогда для любого положительного целого числаm(i,j)-элемент матрицы смежности А^m(m– степень матрицы) будет равен числу прогулок длиныmиз вершиныv_iв вершинуv_j,i,j= 1,2,…,n.

Меры

• Эксцентриситет (u) вершиныu- максимальный из всех путей от этой вершины до всех остальных вершин графа.

• ДиаметрD_G- максимальный эксцентриситет графа.

• Радиус R_G - минимальный эксцентриситет графа.

• Сумма расстояний вершиныS(u) - сумма расстояний от этой вершины до всех остальных вершин графа

• Центр тяжести графа - вершина с минимальной суммой расстояний

Замечания

1. Вершины графа, эксцентриситет которых равен радиусу, образуют центрграфа, а вершины с эксцентриситетом, равным диаметру, находятся на периферии графа.

2. Центр и центр тяжести графа не всегда совпадают.

Класс сложности

Проблема нахождения максимального пути в графе относится к NP-тяжелым.

Определения

Замкнутой прогулкой будет прогулка, которая начинается и заканчивается на одной и той же вершине. Подобным образом определяетсязамкнутая тропа – тропа, которая начинается и заканчивается на одной и той же вершине.

Для простого графа цикломназывается замкнутая прогулка длины не менее трех, т.е. у цикла все вершины различны, кроме первой и последней.

• C^k–длина цикла - равна числу входящих в циклkребер.

• g(G) –обхват графа – цикл минимальной длины, содержащийся вG.

• С(G) –окружность графа- цикл максимальной длины, содержащийся в графеG.

Пример

g(G)=1 граф содержит одну или более петель (является псевдографом)

g(G)=2 граф содержит кратные ребра, но не содержит петель (мультиграф)

g(G) 3 Gявляется простым графом

g(G)= Gне содержит циклов

Теоремы

Теорема 1

Если граф Gимеет минимальную степень δ(G) 2, то этот граф содержит цикл.

Теорема 2

Каждая замкнутая с нечетной длиной прогулка графа содержит цикл нечетной длины.

Теорема 2

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

Класс сложности

Нахождение циклов в графе требует линейного времени.

Алгоритмы

• Найти простые циклы в связном графе можно с помощью алгоритма обхода графа в глубину (DSF).

• Циклы связного графа могут быть найдены линейной комбинацией фундаментальных циклов.

2.5.1.Вершинно- и реберно-независимые пути

Определения

Пути между двумя заданными вершинами uиvграфаGназываются:

• вершинно-независимыми(вершинно-разделенными), если они не имеют общих вершин, за исключениемuиv;

• р

  Меры

  еберно-независимыми (реберно-разделенными), если они не имеют общих ребер.

• Расстояние аварии (ошибки)– длина вершинно-независимого пути в графе.

• Диаметр аварии (ошибки)– максимальный среди всех вершинно-независимых путей между двумя вершинами.

Между двумя различными вершинами графа G(V,E) имеется по крайней мере(G) вершинно-независимых путей и по крайней мере(G) реберно-независимых путей.

2.6. Связность

Определения

Непустой граф Gназываетсясвязным, если любые его вершины могут быть соединены путем.

• (G) –вершинная связность.Измеряется наименьшим числом вершин, удаление которых приведет к несвязному или одновершинному графу.

• (G) –реберная связность: наименьшее число ребер, удаление которых приводит к несвязному графу.

 2

 5

4

8

 6





1 

 7

 3

Рис.2.6.1. Связный граф

Теорема Уитни

Если (G) – минимальная степень вершин графаG, то справедливо неравенство

(G)  (G)  (G)

Определения

Пусть G=(V,E) будет графом. Тогда максимальный (т.е. имеющий наибольшее число вершин и/или ребер) связный подграф графаGназываетсякомпонентой графаG.

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

Теоремы

Теорема 1

Любой граф с nвершинами, имеющий более чем (n-1)(n-2)/2 ребер, связан.

Теорема 2

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

Теорема 3

Пусть G=(V,E) будет графом сnвершинами иkкомпонентами. Тогда числоmего ребер удовлетворяет условию

n-k   m   (n-k)(n-k+1)/2

Класс сложности

Определение связности графа требует линейного времени.

Алгоритмы

Алгоритм обхода графа в глубину (DFS) позволяет ответить на вопрос, является ли граф связным. Для этого необходимо:

1. Установить, что все вершины не маркированы (являются белыми);

2. Начиная с любой вершины, выполнить алгоритм обхода в глубину (DFS);

3. Если после выполнения алгоритма поиска в глубину остались немаркированными вершины, то граф является несвязным. В противном случае – граф связный.

Алгоритм обхода графа в ширину также отвечает на вопрос о связности графа в линейное время.

2.6.1. Реберная связность

Определения

Введем следующую запись: если Gесть граф и {v_i,v_j}-его ребро, то будем записыватьG-{v_i,v_j}граф, полученный из исходного графаGудалением ребра {v_i,v_j}.

Формально вновь полученный граф имеет множество вершин V(G) и множество реберE(G) -{v_i,v_j}.

Ребро {v_i,v_j} E(G) называетсяребром разреза (илимостом), еслиG-{v_i,v_j}имеет больше компонентов, чем исходный графG.

Обобщением понятия ребра разреза (моста) является понятие разрывающего множества ребер SграфаG=(V,E). Это – такое множество, что графH=(V,E-S) имеет меньше компонент, чем графG=(V,E).

Граф называется k-связным (илиk-реберносвязным) у, если λ(G) k.