Лекция: Теория графов

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

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

С C

A D A D

В B

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

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

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

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

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

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

Гx1 = {x2} Гx4 = {x3, x3}

Гx2 = {x2, x3, x4} Гx5 = {x2}

Гx3 = Æ

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

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

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

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

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

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

a b c a

a 1

3 1

c b c 3

1 2 3 2 b

2

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

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

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

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

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

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

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

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

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

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

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

r-(x3) = 3.

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

r+(x3) = 2.

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

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

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

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

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

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

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

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

:

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

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

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

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

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