Теория графов

Понятие графа

Начало теории графов часто ведут от 1736 года и связывают с решением Эйлером знаменитой задачи о Кенигсбергских мостах.

С C

A D A D

В B

Жителям в те далекие времена, чтобы придать воскресному гулянию осмысленность, предлагалось выйдя из дома (на любом участке суши (А, В, С или D) пройти по всем мостам строго по одному разу и вернуться домой….

На втором рисунке этот корявый план нарисован в виде графа.

Следует отметить некоторые практические особенности теории графов. Слово граф однокоренное со словом графика. Поэтому не удивительно, что многие задачи теории графов представляются в виде специального рисунка – графа. Однако, это, как правило, возможно только для простейших вариантов задач. Рисовать графы для задач с сотнями вершин и тысячами дуг, если и возможно, то бессмысленно. Теряется главное преимущество рисунка – наглядность. Кроме того, сегодня при решении задач теории графов широко используется вычислительная техника, а для нее - решение задачи, заданной рисунком – одно из самых неудобных представлений, какие можно придумать. А наглядность компьютер понимает по-своему :-|

Граф G задается как совокупность двух сущностей: множества вершин Х и множества соединений – множества дуг или ребер. Г. G = <Г, Х>,

Графически это может выглядеть следующим образом:

m

b

e

x5

j

x4

Традиционная «аналитическая» запись для этого рисунка будет:

Г_x1 = {x₂} Г_x4 = {x₃, x₃}

Г_x2 = {x_2, x₃, x₄} Г_x5 = {x₂}

Г_x3 = Æ

Другой способ задания графа - с помощью матрицы инциденций.

	a	b	d	h	j	e	m
х1	-1
х2	+1		-1			-1	+1
х3			+1	-1
х4				+1	-1	+1
х5					+1		-1

Самый популярный вид матрицы для графов – матрица смежностей

	х1	х2	х3	х4	х5
х1
х2
х3
х4
х5

Граф с ненаправленными соединениями (ребрами) - неориентированный.

Граф с направленными стрелками (дугами) – ориентированный (орграф).

Мультиграф – граф, между вершинами которого может быть больше одной дуги.

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

a b c a

a 1

3 1

c b c 3

1 2 3 2 b

2

Один и тот же граф.

Дуга может выходить из вершины или заходить в нее. Она будет соответственно называться исходящей или заходящей.

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

Длина пути измеряется числом пройденных дуг.

Путь, начинающийся и заканчивающийся в одной и той же вершине - контур.

Контур длиной в единицу - петля.

Путь называется простым, если каждое из ребер встречается на этом пути один раз.

Путь называется элементарным, если любая вершина на этом пути один раз.

Дуга, исходящая (или заходящая) в вершину называется инцидентной данной вершине (и наоборот вершина инцидентна дуге).

Вершины инцидентные одной дуге называются смежными.

Полустепенью исхода вершины x - r^-(x) называется число исходящих из нее дуг

r^-(x₃) = 3.

Полустепенью захода вершины x - r⁺(x) называется число заходящих в нее дуг

r⁺(x₃) = 2.

r = r^-(x) + r⁺(x). - степень вершины х.

Теорема: В любом графе число вершин с нечетной степенью четно.

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

Теорема: В графе без петель, где вершин больше двух всегда найдется пара вершин с одинаковой степенью.

Доказательство заменим решением задачки «про шахматистов»:

Пусть среди n человек нет двух таких, кто сыграл бы одинаковое число партий в шахматном турнире. Тогда обязательно должно быть:

1-ый сыграл: 0 партий

2-ой сыграл: 1 партию

:

n-ый сыграл n-1 партий

т.е. из вершины n-го игрока исходит (n-1) стрелка, а в 0-ую не входит ни одна. Но этого не может быть.

Граф G_A = <Г_A, A> - называется подграфом графа G = <Г, X>, если A Í Х, Г_A Í Г.

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

Граф называется связным (компонентом связности), если между любыми двумя вершинами есть цепь.