Глава 1. История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер (1707 – 1783 гг.). В 1736г. в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей одной из классических задач теории графов. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через р.Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Маринони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».На упрощённой схеме части города (графе) мосты — линии (дуги графа), части города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.Если ровно две вершины графа нечётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой из нечётных вершин и завершить его в другой нечетной вершине.Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все) (рис.3), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

а)
б)	в)
Рис. 1. Кёнигсбергские мосты

 

Рис.1. (название) рис.2

 

 

рис.3

ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Определение 1. Графом G называется пара (V,E), где V={v₁,…,v_n} – непустое множество вершин графа, E = {e₁,e₂,…,e_m} – множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Обычно граф изображают на плоскости в виде точек (они соответствуют вершинам графа) и непрерывных линий, соединяющих некоторые из этих точек (они обозначают ребра графа). Пусть ребро е соединяет вершины u и v. В этом случае пишут e = [u,v] и говорят, что

1) u и v являются концами ребра е;

2) вершины u и v смежны;

3) вершины u и v инцидентны ребру е, ребро е инцидентно вершинам u и v. рис. 4

Определение 2. Степенью вершины называется количество инцидентных ей ребер.

 

Определение 3. Вершина называется изолированной, если она не инцидентна ни одному ребру; вершина называется концевой, если ей инцидентно только одно ребро.(рис.4)

Степень вершины v обозначается через deg(v). В графе (рис.4) вершина – изолированная, так как deg(v₁) = 0; вершина v₂смежна с вершинами v₃ и v₄ и инцидентна ребрам [v₂, v₃] и [v₂, v₄], следовательно, deg(v₂) = 2; вершина v₃смежна с вершинами v₂ и v₄ и инцидентна ребрам [v₂, v₃] и [v₃, v₄], поэтому, deg(v₃) = 2;вершина v₄]смежна с вершинами v₂, v₃ и v₅, инцидентна ребрам [v₂, v₄], [v₃, v₄] и [v₄, v₅], следовательно, deg(v₅) = 3; вершинаv₅ – концевая, поскольку deg(v₅) = 1; она смежна только с вершиной v₄ и инцидентна только ребру [v₄, v₅].

 

Утверждение 1. Если в графе количество вершин n≥2, то в нем найдутся хотя бы две вершины с одинаковой степенью.

Докажем это утверждение от противного. Пусть все вершины графа имеют разные степени. Для удобства будем считать, что deg(v ₁) = 0, deg(v ₂) = 1,…, deg(v_n) = n – 1. Но согласно последнему равенству вершина v_n смежна со всеми вершинами графа, в том числе и с вершиной v ₁, а равенство deg(v ₁) = 0 означает, что v ₁ – изолированная вершина. Получили противоречие. Следовательно, в любом графе с количеством вершин n ≥2 обязательно найдутся две или более вершины с одинаковой степенью.

Кроме наглядного изображения на плоскости, граф можно задать с помощью списков смежности, матрицы смежности и матрицы инциденций. В списках смежности для каждой вершины графа указываются все вершины, смежные с ней. Этого достаточно, чтобы однозначно определить исходный граф. Матрицы смежности и инциденций тоже однозначно определяют граф. Но для задания графа матрицей смежности (инциденций) необходимо пронумеровать его вершины (и ребра).

 

Определение 4. Эксцентриситетомвершины u называется число Ɛ(u) равное максимальному расстоянию от вершины u до остальных вершин графа, т.е.

Ɛ(u) = max p(u,v), v ∈ V

Определение 5. Радиусомграфа G называется число r (G), равное минимальному эксцентриситету его вершин, т.е.

r (G) = minƐ(v), v ∈ V

Орпеделение 6. Диаметромграфа G называется число d (G), равное максимальному эксцентриситету его вершин, т.е.

d (G) = maxƐ(v), v ∈ V

Известно, что для любого графа G выполняется соотношение

r (G) ≤ d (G) ≤ 2* r (G)

Орпеделение 7. Центромграфа G называется множество его вершин, имеющих минимальный эксцентриситет.

Пример. Рассмотрим граф G, изображенный на рис.. Эксцентриситеты его вершин:

Ɛ(v₁) = 4, Ɛ(v₂) = 3, Ɛ(v₃) = 4, Ɛ(v₄) = 3, Ɛ(v₅) = 2, Ɛ(v₆) = 3.

Следовательно, его радиус и диаметр r (G) = 2, d (G) = 4, а центр – вершина v₅.

рис. 5