Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический

• Название: Простые графы (графы) Способы задания графа Основные способы задания графов графический
• Анкор: Глава 2.Ненаправленные графы, часть 1.doc
• Дата: 04.09.2018
• Размер: 1.28 Mb.
• Имя файла: Глава 2.Ненаправленные графы, часть 1.doc
• Тип: Глава; #24055
• страница: 8 из 14

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).
  
• 
  Циклы связного графа могут быть найдены линейной комбинацией фундаментальных циклов.