Лекция 4. Графы

4.1.Графы. Определение, виды графов

4.2. Свойства графов

Программные положения

Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков. (Ф.Харари «Теория графов»)

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

Литература

Контрольные вопросы

1. Что такое граф?
2. Что называют вершиной и ребром графа?

3. Можно ли обвести данную схему, не отрывая карандаша и не проходя дважды никакие ребра

1. Может ли сумма степеней вершин графа быть нечетным числом?
2. Можно ли организовать турнир между 11 командами, так, чтобы каждая сыграла ровно 5 матчей?

6. Покажите равносильность определений из п.4.1.(6) (что описывают один и тот же объект)

7.Покажите, что изоморфны графы

8. Покажите, что изоморфизм есть отношение эквивалентности на графах.

9.На какое минимальное количество частей нужно разделить кусок проволоки, чтобы из нее можно было сделать каркас куба

10. Покажите, что граф является планарным

Графы. Определение, виды графов

Отцом теории графов является Л.Эйлер A707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов.

В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рис. 4.1.(1) (A,D – острова, B,C – берега реки). Задача состояла в следующем: найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей. Л.Эйлеру удалось найти решение этой задачи заключается в доказательстве невозможность такого маршрута.

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки. Получился «граф». Этот граф показан на рис. 4.1.(2), где точки

отмечены теми же буквами, что и четыре части суши на рис. 4.1(1). Утверждение о несуществовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рис. 4.1(2).

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

Примером другой проблемы, которую можно промоделировать на основе теории графов, является задача о снабжении трех домов тремя видами коммунальных услуг. Согласно условию задачи к каждому из трех домов необходимо подключить три вида коммунальных услуг, например, воду, газ и электричество, посредством подземных линий труб и кабелей. Вопрос состоит в том, можно ли обеспечить эти три дома коммунальными услугами без пересечения линий снабжения. Граф, моделирующий данную задачу, показан на рис. 4.1(3) (Эта известная модельная задача иногда формулируется как задача про дома и колодцы)

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

Определение 4.1(1)

Граф есть конечное множество V, называемое множеством вершин, и множество Е двухэлементных подмножеств множества V. Множество Е называется множеством ребер. Элемент множества Е называется ребром. Граф обозначается G(V, E). Элементы а и b множества V называются соединенными, или связанными ребром {а, b}, если .

Иначе говоря, граф – это схема, состоящая из точек, некоторые из которых соединены отрезками.

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

Определения 4.1(2)

Если {а, b} - ребро, тогда вершины а и b называются концами ребра {а, b}. Ребро {а, b} называют также инцидентным к вершинам а и b. Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}. Две вершины называются смежными (соседними ), если они являются концами ребра, или, что то же самое, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.

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

Если в графе все вершины соседние, граф называется полным .

Граф с одной вершиной и без ребер (состоящий из 1 точки – вершины), называется тривиальным.

Определение 4.1(3)

Степенью вершины v обозначается deg(v), называется количество ребер, инцидентных этой вершине (исходящих из нее).

Вершина степени 0 (то есть из вершины не исходит ни одного ребра, это «одинокая» точка) называется изолированной.

Вершина степени 1 называется висячей.

Вершины могут быть четными и нечетными.

Определения 4.1.(4)

Путь (между вершинами) – последовательность ребер и промежуточных вершин, их соединяющая

Длина пути – количество ребер, входящих в путь

Простой путь – путь, в котором все ребра и вершины различны

Цикл (петля) – замкнутый путь ненулевой длины, в котором все вершины различны кроме начала, совпадающего с концом

Примеры 4.1(1).

1. Граф с множеством вершин V = {а,b,с} и множеством ребер Е {{а, b}, {b, с}} может быть изображен, как показано на рисунке 4.1(4) (Простой) путь между вершинами a и c включает ребра {a,b}, {b,c} и вершину c

Замечание: оба рисунка отражают одну и ту же ситуацию. С точки зрения графов в первую очередь имеет значение наличие связи между точками, а не ее геометрия.

2. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},

может быть изображен диаграммой, показанной на рис. 4.1.(5). Граф содержит два цикла {b, e, a}, {b, c, d}.

3. На рис. 4.1.(6)вершины а и с – смежные и е 1 , е 2 и е 3 - смежные ребра, вершины а и f смежными не являются, а е 2 и е 5 не являются смежными ребрами. Вершины b, с и d имеют степень 2, в то время как вершины a и f имеют степень 3.

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

В первом случае все вершины должны иметь четные степени, во втором – четными должны быть все вершины, кроме входа и выхода.

Пример 4.1.(2)

Можно ли пройти граф на рис. 4.1(4), не пропуская и не проходя дважды никакие ребра?

Степени всех вершин четны, кроме вершин с и j со степью 3. Соответственно, единственный путь обхода – имеющий вершины c и j началом и концом (или наоборот)

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

Определение 4.1(5)

Ориентированный граф или орграф G , который обозначается через G(V, Е) состоит из множества V вершин и множества Е упорядоченных пар элементов из У, называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован. Элемент множества Е называется ориентированным ребром. Если , то а называется начальной вершиной ребра (а, b), b называется конечной вершиной.

Пример 4.1(3)

Орграф, у которого V = {а, b, с, d] и Е = {(а, b), (b, с), (с, с), (c, d), (d,b),(c,d),(d,a)} изображен на рис.

Определение 4.1.(6)

Рассмотрим несколько равносильных определений графа дерево.

1) Это связный граф, не имеющий циклов (о свойстве связности см 4.2.)

2) Граф, в котором любые 2 вершины соединены простым путем

3) Связный граф, теряющий связность при удалении любого ребра

4) Граф, в котором ребер на 1 меньше, чем вершин

Примеры деревьев:

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

Свойства графов

Теорема 4.2(1).

Сумма степеней вершин графа всегда четная.

Доказательство

Поскольку каждое ребро графа имеет два конца, степень каждого конца увеличивается на 1 за счет одного ребра. Таким образом, в сумму степеней всех вершин каждое ребро вносит 2 единицы, поэтому сумма должна в два раза превышать число ребер. Следовательно, сумма является четным числом.

Теорема 4.2.(2)

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

Доказательство

Доказательство проведем методом от противного: предположив, что теорема не верна, найдем противоречие, из которого будет следовать, что теорема справедлива. Если теорема не верна, то имеется нечетное количество вершин, степени которых нечетны. Но сумма степеней вершин с четными степенями четна. Сумма степеней всех вершин есть сумма степеней вершин с нечетными степенями плюс сумма степеней вершин с четными степенями. Поскольку сумма нечетного числа и четного числа есть число нечетное, сумма степеней всех вершин нечетная. Но это противоречит теореме 4.1(1), поэтому мы пришли к противоречию. Следовательно, делаем вывод, что теорема справедлива.

Пример 4.2.(1)

Можно ли организовать футбольный турнир между 7 командами так, чтобы каждая сыграла ровно по 3 матча?

Нет, так как, если мы составим граф с 7 вершинами, и попытаемся вывести по 3 ребра из каждой вершины. Согласно теореме 4.2(2), такой граф построить невозможно.

Определение 4.2(1).

Изоморфными называются графы одинаковой структуры. Два графа G и Н изоморфны (записывается или иногда G=H), если между их множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность. Например, G и H на рис. 4. 2(2) изоморфны при соответствии .

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

Заметим, что изоморфизм есть отношение эквивалентности на графах.

Определения 4.2(2)

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

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

Связностью x=x(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Из определения следует, что связность несвязного графа равна 0, а связность связного графа, имеющего точку сочленения, равна 1. Полный граф нельзя сделать несвязным, сколько бы вершин из него ни удалять.

ГРАФЫ

Графы возникли в восемнадцатом столетии, когда известный мате­матик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсбер­ге было два oстровa, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рис. 7.1. 3адача со­стоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра - с мостами, которыми связаны эти части. Как мы покажем в § 7.1, Эйлеру удалось доказать, что искомого маршрута обхода города не существует.

Рисунок 7.1. Схема старого Кенигсберга

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

Графы и терминология

На рис. 7.1 изображены семь мостов Кенигсберга так. как они были расположены в восемнадцатом столетии. В задаче, к которой oбpa­тился Эйлер, спрашивается: можно ли найти маршрут прогулки, ко­торый проходит ровно один раз по каждому из мостов и начинается и заканчивается в одном и том же месте города?

Модель задачи - это граф, состоящий из множества вершин и множества ребер, соединяющих вершины. Вершины А, В, С и D символизируют берега реки и острова, а ребра а,в , c ,d, f и g обозначают семь мостов (см. рис. 7.2). Искомый маршрут (если он существует) соответствует обходу ребер графа таким образом, что каждое из них проходится только один раз. Проход ребра, очевидно, соответствует пересечению реки по мосту.

Рисунок 7.2. Модель задачи о мостах Кенигсберга

Граф, в котором найдется маршрут, найдется маршрут, на­чинающийся и заканчивающийся в одной вершине, и проходящий по всем ребрам графа ровно один раз, называется зйлеровым графом. Последовательность вер­шин (может быть и с повторениями), через которые проходит иско­мый маршрут, как и сам маршрут, называется эйлеровым циклом . Эйлер заметил, что если в графе есть эйлеров цикл, то для каждого ребра, ведущего в какую-то вершину, должно найтись другое ребро, выходящее из этой вершины 1 , и получил из этого простого наблюдсния такой вывод: если в данном графе существует эйлеров цикл, то к каждой вершине должно подходить четное число ребер.

Кроме того, Эйлеру удалось доказать и противоположное утвер­ждение, так что граф, в котором любая пара вершин связана не­которой последовательностью ребер, является Эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. Степенью вершины v называется число δ(v) ребер, ей инцидентных 2 .

Теперь совершенно очевидно, что в графе, моделирующем задачу о мостах Кенигсберга, эйлерова цикла найти нельзя. Действитель­но, степени всех его вершин нечетны: δ(B ) = δ(С) = δ(D) = 3 и δ(A ) = 5. С легкой руки Эйлера графы, подобные тому, который мы исследовали при решении задачи о мостах, стали использовать­ при решении многих практических задач, а их изучение выросло в значительную область математики.

Простой граф определяется как пара G = (V, Е), где V - ко­нечное множество вершин, а Е - конечное множество ребер, при­чем не может содержать петель (ребер, начинающихся и закан­чивающихся в одной вершине) и кратных ребер (кратными назы­ваются несколько ребер, соединяющих одну и ту же пару вершин). Граф, изображенный на рис. 7.2. не является простым, поскольку, например, вершины А и В соединяются двумя ребрами (как раз эти ребра и называются кратными).

Две вершины u и v в простом графе называются смежными , если они соединяются каким-то ребром е , про которое говорят, что оно инцидентно вершине u (и v). Таким образом, мы можем предста­влять себе множество Е ребер как множество пар смежных вершин, определяя тем самым нерефлексивное, симметричное отношение на множестве V. Отсутствие рефлексивности связано с тем, что в простом графе нет петель, т. е. ребер, оба конца которых находятся в одной вершине. Симметричность же отношения вытекает из того факта, что ребро е , соединяющее вершину и с v, соединяет и v с и (иначе говоря, ребра не ориентированы, т. е. не имеют направления). Единственное ребро простого графа, соединяющее пару вершин u и v, мы будем обозначать как иv (или vи).

Логическая матрица отношения на множестве вершин графа, котopoe задается его ребрами, называется ,матрицей смежности. Симметричность отношения в терминах матрицы смежности М озна­чает, что М симметрична относительно главной диагонали. А из-за нерефлексивности этого отношения на главной диагонали матрицы М стоит символ «Л».

Пример 7.1. Нарисуйте граф G(V, Е) с множеством вершин V = {а, Ь, с, d, е} и множеством ребер E = {ab, ae, bc, bd, ce, de}. Выпишите его матрицу смежности.

Решение. Граф G показан на рис. 7.3.

Рисунок 7.3.

Его матрица смежности имеет вид:

Для восстановления графа нам достаточно только тех элементов матрицы смежности, которые стоят над главной диагональю.

Подграфом графа G = (V, E) называется граф G’ = (V’, E’), в котором E’ C E и V’ C V.

Пример 7.2 Найдите среди графиков H, K и L, изображенных на рис. 7.4, подграфы графа G.

Решение. Обозначим вершины графов G, H и K как показано на рис. 7.5. Графы H и K – подграфы в G, как видно из наших обозначений. Граф L не является подграфом в G, поскольку у него есть вершина индекса 4, а у графа G такой нет.

Маршрутом длины k в графе G называется такая последовательность вершин v 0 , v 1 , …, v k , что для каждого i = 1, …, k пара v i – 1 v i образует ребро графа. Мы будем обозначать такой маршрут через v 0 v 1 … v k . Например 1 4 3 2 5 – это маршрут длины 4 в графе G из примера 7.2.

G H

K L

Рисунок 7.4.

Циклом в графе принято называть последовательность вершин v 0 , v 1 , … , v k , каждая пара которых является концами одного ребра, причем v 0 = v 1 , а остальные вершины (и ребра) не повторяются. Иными словами, цикл – это замкнутый маршрут, проходящий через каждую свою вершину и ребро только один раз

1 2 1 2 3

Рисунок 7.5

Пример 7.3. Найдите циклы в графе G из примера 7.2.

Решение. В этом графе есть два разных цикла длины 5:

1 3 2 5 4 1 и 1 2 5 4 3 1

Мы можем пройти эти циклы как в одном направлении так и в другом, начиная с произвольной вершины цикла. Кроме того, в графе есть три разных цикла длины 4:

1 2 5 4 1, 1 2 3 4 1 и 2 5 4 3 2,

и два цикла длины 3:

1 2 3 1 и 1 3 4 1.

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

Граф, называют связным, если любую пару его вершин соединяет какой – нибудь маршрут. Любой общий граф можно разбить на подграфы, каждый из которых окажется связным. Минимальное число таких связных компонент называется числом связности графа и обозначается через c (G ) . Вопросы связности имеют важное значение в приложениях теории графов к компьютерным сетям. Следующий алгоритм применяется для определения числа связности графа.

Алгоритм связности.

Пусть G = (V, E) – граф. Алгоритм предназначен для вычисления значения c = c (G ), т.е. числа компонент связности данного графа G.

V’ :=V;

while V’≠ ø do

Выбрать y Є V ’

Найти вершины, соединяющие маршрутом с у;

Удалить вершину у из V ’ и

соответствующие ребра из Е;

c := c +1;

Пример 7.4. Проследите за работой алгоритма связности на графе, изображенном на рис. 7.6.

Рисунок 7.6.

Решение. Смотри табл. 7.1.

Таблица 7.1.

Исходные значения	{1,2,3,4,5,6,7,8}
Выбор у = 1
Выбор у = 2
Выбор у = 7

Итак, c (G ) = 3. Соответствующие компоненты связности приведены на рис. 7.7.

5

Основные вопросы:

Сведения из истории графов. Граф и
его элементы.
Пути и маршруты в графах
Связные графы. Деревья
Операции над графами.

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

История возникновения графов

Впервые основы теории графов
появились в работах Леонарда
Эйлера (1707-1783;
швейцарский, немецкий и
российский математик) , в
которых он описывал решение
головоломок и математических
развлекательных задач.
Теория графов началась с
решения Эйлером задачи о
семи мостах
Кёнигсберга.

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

История возникновения графов

Термин "граф" впервые появился в книге
венгерского математика Д. Кенига в 1936 г., хотя
начальные важнейшие теоремы о графах
восходят к Л. Эйлеру.

В основе теории лежит понятие графа.

- совокупность конечного числа
точек, называемых вершинами графа, и
попарно соединяющих некоторые из этих
вершин линий, называемых ребрами или
дугами графа. Иногда граф в целом
можно обозначать одной заглавной
буквой.
G V , X называется пара двух
конечных множеств: множество точек V и
множество линий X (ребер, дуг),
соединяющих некоторые пары точек.

Состав графа

Граф состоит из вершин, связанных линиями. Вершины
графа обозначают латинскими буквами A, B, C, D или
цифрами.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в
неё же, называется петлей.
дуга
А
ребро
В
петля
С

Ориентированный граф -

граф, вершины которого соединены дугами. С
помощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя

Взвешенный граф

Это граф, рёбрам или дугам которого поставлены
в соответствие числовые величины (они могут
обозначать, например, расстояние между городами
или стоимость перевозки).
Вес графа равен сумме весов его рёбер.
4
B
C
2
3
2
A
1
E
D
A
B
C
D
Е
A B C D Е
3 1
4
2
3 4
2
1
2 2
Таблице (она называется весовой
матрицей) соответствует граф.

Если
ребро графа G соединяет две его
вершины V и W, (т.е. V ,W X), то говорят,
что это ребро им инцидентно.
Две вершины графа называются смежными,
если существует инцидентное им ребро: на
рисунке смежными являются вершины А и В,
А и С.
А
С
В

Если граф G имеет ребро, у которого начало
и конец совпадают, то это ребро называется
петлёй. На рисунке ребро q(С, С) – петля.
q
E
С
A
D
B

Два ребра называются смежными, если они
имеют общую вершину.
На рисунке смежными являются, например,
рёбра х1 и х2 с общей вершиной С.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Рёбра, которые начинаются в одной и
той же вершине, заканчиваются также
в одной и той же вершине, называются
кратными, или параллельными.
Количество одинаковых пар вида
(V , W) называется кратностью ребра (V , W)
Число рёбер, инцидентных вершине А,
называется степенью этой вершины и
обозначается deg(A) (от англ. degree –
степень).

На рисунке кратными являются, например,
рёбра х1(А, В), х2(А, В). Вершинам А и С
инцидентны рёбра х3, х4, х5. Следовательно,
ребро АС имеет кратность, равную 3, а ребро
АВ – кратность, равную 2.
А
х4
х1
х3
С
х2
х5
В

На рисунке вершина А имеет степень,
равную 1, вершина С – 4, вершина D – 2.
Записывается это в виде: deg(A)=1, deg(C)=4,
deg(D)=2.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Вершина графа, имеющая степень, равную нулю,
называется изолированной.
Граф, состоящий из изолированных вершин,
называется нуль-графом.
Вершина графа, имеющая степень, равную 1,
называется висячей.
Граф, не имеющий ребер (дуг), называется
пустым.
E
C
A
D
B
На рисунке вершина
Е – изолированная:
deg(E)=0.

На рисунке вершины А, В, Е, G, H – висячие.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Теорема 1. В графе G V , X сумма
степеней всех его вершин – число чётное,
равное удвоенному числу рёбер графа:
n
deg(V) 2m
i 1
i
Количество ребер в любом графе равно
половине суммы степеней его вершин.
где n V
- число вершин;
m X - число рёбер графа.

Вершина называется чётной (нечётной),
если её степень – чётное (нечётное) число.
На рисунке deg(D)=2, deg(F)=3, значит у
графа вершина D является чётной, а F –
нечётной.
х5
D
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Задача. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью

другими?

Теорема 2. Всякий (неориентированный)
граф содержит четное число нечетных
вершин.
Следствие. Невозможно начертить граф с
нечётным числом нечётных вершин.
Граф G называется полным,
если любые две его различные
вершины соединены одним и
только одним ребром.

Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 - по 4 друга, а 10 - по 5 друзей?

Дополнением графа G V , X называется
граф G V , X с теми же вершинами V, что и
граф G, и имеющий те и только те рёбра X ,
которые необходимо добавить к графу G, чтобы он
стал полным. На рисунке дополнением графа G1 до
графа G является граф
G1
G
G1
G1

Закономерность 1.
Закономерность 2.
Степени вершин
Сумма степеней
полного графа
одинаковы, и
каждая из них на 1
меньше числа
вершин этого
графа
вершин графа число
четное, равное
удвоенному числу
ребер графа. Эта
закономерность
справедлива не
только для полного,
но и для любого
графа.

Закономерность 3.
Закономерность 4.
Число нечетных
Невозможно
вершин любого
графа четно.
начертить граф с
нечетным числом
нечетных вершин.

Закономерность 5.
Закономерность 6.
Если все вершины
Граф, имеющий всего
графа четные, то
можно не отрывая
карандаш от бумаги
(«одним росчерком»),
проводя по каждому
ребру только один раз,
начертить этот граф.
Движение можно
начать с любой
вершины и закончить
его в той же вершине.
две нечетные
вершины, можно
начертить, не
отрывая карандаш
от бумаги, при этом
движение нужно
начать с одной из
этих нечетных
вершин и закончить
во второй из них.

Закономерность 7.
Граф, имеющий более
двух нечетных
вершин, невозможно
начертить «одним
росчерком». Фигура
(граф), которую можно
начертить не отрывая
карандаш от бумаги,
называется
уникурсальной.

Пути и маршруты в графах

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

В качестве примера рассмотрим орграф,
представленный на рисунке. Одним из существующих
путей, соединяющих вершины 1 и 3, является
последовательность вершин 1, 2, 1, 4, 3. Единственным
простым путем для той же пары вершин является
последовательность 1, 4, 3. Пути из вершины 1 в
вершину 5 для того же графа не существует.

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

Путь называется замкнутым, если
начальная и конечная вершины совпадают.
Замкнутый путь называется циклом, если все
его вершины (кроме начальной и конечной)
различны.
Рассмотрим граф. Для него путь 2, 1, 6, 5, 4, 1,
2 является замкнутым; а путь 1, 6, 5, 4, 1
является циклом.

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

На рисунке HCDFD – маршрут длиной 4.
Обозначение: |HCDFD|=4. Маршрут принято
задавать
как
последовательность
рёбер,
поскольку это удобно при наличии кратных
рёбер.
х
D
х1
5
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

В графе на рисунке (t, s, p, r), (u, s, t, r) – циклы
длиной 4, (r, t, q, s, u) – цикл длиной 5, (t, s, u, r, t, s, p, r)
– 8-цикл, (p, u) – 2-цикл, петля (q) – 1-цикл.
E
q
C
s
A
p
t
D
r
B
u

Операции над графами

Одноместные операции
1. Удаление ребра графа - при этом все вершины графа
сохраняются
2. Добавление ребра графа между двумя
существующими вершинами.
3. Удаление вершины (вместе с инцидентными
ребрами).
4. Добавление вершины (которую можно соединить с
некоторыми вершинами графа).
5. Стягивание ребра - отождествление пары вершин, т.е.
удаление пары смежных вершин, и добавление новой
вершины, смежной с теми вершинами, которые были
смежны, хотя бы одной из удаленных вершин)
6. Подразбиение ребра с- удаление ребра и добавление
новой вершины, которая соединяется ребром с каждой из
вершин удаленного ребра.

Операции над графами

Двуместные операции
Объединением графов G1 (V1 , X 1) и G2 (V2 , X 2)
называется граф G G1 G2 , множество вершин
которого V V1 V2 , а множество рёбер X X 1 X 2 .
Пересечением графов G1 и G2 называется
граф G G1 G2 , для которого X X 1 X 2 множество рёбер, а V V1 V2 - множество вершин.
Кольцевой суммой двух графов называется граф
G G1 G2 , порождённый множеством вершин
т.е.
V V1 V2 и множеством рёбер (X1 X 2) \ (X1 X 2) ,
множеством рёбер, содержащихся либо в G1 , либо в
G2 , но не в G1 G2 .

V4
V2
х3
х2
V3
х4
V1
х1
V5
х2
х7
х3
х4
х4
V1
х7
V1
G=G1UG2
V3
х4
V5
х2
V1
х3
G=G1∩G2
V2
х1
G2
V4
V2
х5 х6
х6
V3
V1
V4
V3
V4
х5
х3
х1
G1
V2
V5
V2
V4
х5 х6V
3
х7
G=G1 G2

Применение графов

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

Применение графов

Лабиринт - это граф. А исследовать его - это найти
путь в этом графе.
дальше

Использует графы и
дворянство.
На рисунке приведена
часть генеалогического
дерева
знаменитого
дворянского рода Л. Н.
Толстого. Здесь его
вершины – члены этого
рода, а связывающие их
отрезки – отношения
родственности,
ведущие от родителей к
детям.
дальше

Применение графов

Графами являются блок – схемы программ для
ЭВМ.
дальше

Применение графов

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

Применение графов

Типичными графами на картах города
являются схемы движения городского
транспорта.
дальше

Выводы

Графы – это замечательные математические
объекты, с помощью, которых можно решать
математические, экономические и логические
задачи. Также можно решать различные
головоломки и упрощать условия задач по
физике, химии, электронике, автоматике. Графы
используются
при
составлении
карт
и
генеалогических древ.
В математике даже есть специальный раздел,
который так и называется: «Теория графов».
содержание

Вполне несвязные графы . Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с п вершинами через N n ; N 4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

Полные графы . Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами обычно обозначается через. Графы и изображены на рис. 2 и 3. имеет ровно n (n - 1)/2 ребер.

Регулярные графы . Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф К n - регулярным степени n - 1.

Платоновы графы . Среди регулярных графов особенно интересны так называемые Платоновы графы - графы образованные вершинами и ребрами пяти правильных многогранников - платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;

Двудольные графы . Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V 1 и V 2 так, что каждое ребро в G соединяет какую-нибудь вершину из V 1 с какой-либо вершиной из V 2 (рис. 7);

тогда G называется двудольным графом. Такие графы иногда обозначают G(V 1, V 2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому - в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой - синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V 1 соединена с каждой вершиной из V 2 ; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается где m, n - число вершин соответственно в V 1 и V 2 . Например, на рис. 8 изображен граф K 4 , 3 . Заметим, что граф имеет ровно m + n вершин и mn ребер. Полный двудольный граф вида называется звездным графом; на рис. 9 изображен звездный граф.

Связные графы . Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой (связности) графа G. (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом . (рис.2 )

Графы, в которых не построены все возможные ребра, называются неполными графами . (рис.3 )

Графы, в которых построены все возможные ребра, называются полными графами . (рис.4 )


Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным .

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

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

Степени вершин и подсчет числа ребер.

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если степени всех вершин графа равны, то граф называется однородным . Таким образом, любой полный граф - однородный.

На рисунке 5 изображен граф с пятью вершинами.

Степень вершины А обозначим Ст.А.

На рисунке:
Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Число нечетных вершин любого графа четно .

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

Эйлеровы графы.

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

Такими графы названы в честь учёного Леонарда Эйлера .


Закономерность 3. (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.

Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.

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

Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком ».

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

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

На рисунке 7, очевидно, изображен несвязный граф.

Граф называется несвязным , если это условие не выполняется.

Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.(рис.8 )

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом .

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8 )

Несвязный граф состоит из нескольких «кусков ». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.

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

Деревья.

Деревом называется любой связный граф, не имеющий циклов.

Циклом называется путь, в котором совпадают начало с концом.

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

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

В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро (рис.10 ).
(кружком обведены висячие вершины).


Для каждой пары вершин дерева существует единственный путь, их соединяющий .

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

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается » на два дерева.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом .

(о висячей вершине). В каждом дереве есть висячая вершина.

. В дереве число вершин на одну больше числа ребер.

Изоморфизм. Плоские графы и теорема Эйлера.

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

Докажем, что графы изображенные на рисунке 11 изоморфны.


Пронумеруем вершины первого и второго графов от 1 и до 4 (рис.12 ).


В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.

Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:

• одинаковое количество вершин
• если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.

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

Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков.(равенство V -E+F=2 обычно называют формулой Эйлера) .

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

Понтрягина – Куратовского . Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.

(В основном используется в старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса - является ли рассматриваемый граф плоским или нет, рис.13 )

Ориентированные графы.

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

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

Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах - улицах рассматриваемой схемы (графа) города.

Граф, на рёбрах которого расставлены стрелки, называется ориентированным .

Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих » из вершины).

Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих » в вершину).

Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3.

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, ..., Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

На рисунке.15 показаны примеры путей в ориентированном графе. Причем, первые два пути простые - ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым,т. к. через вершину Г путь «проходил » дважды.

Ориентированным циклом называется замкнутый путь в ориентированном графе.

На рисунке 15 приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй - 3,
а третий - 4.

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным(обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

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