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

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

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

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

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

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

Методические рекомендации

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

Литература

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 4.1(1)

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

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

Рис.4.1(2)

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

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

Рис.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

Рис. 4.1(4)

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

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

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

Рис.4.1(5)

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

Рис. 4.1.(6)

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

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

Пример 4.1.(2)

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

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

Рис.4.1(4)

Во многих случаях необходимы графы, у которых ребра, по существу, представляют собой улицу с односторонним движением. Это означает, что если рассматривается ребро, выходящее из вершины а в вершину 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).

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

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

G H

Рис.4.2(2)

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

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

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

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

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

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

Аналогично реберная связность λ=λ(G) графа G определяется как наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.

Пример несвязного графа, состоящего из 2 компонент связности, приведен на рис. 4.2(3)

Рис. 4.2(3)

Пример 4.2.(2)

В государстве 100 городов, из каждого выходит две дороги, кроме столицы страны Фрейдинска, откуда выходят 5 дорог, и города Лаканово, куда ведет только одна дорога

1) Сколько всего дорог в государстве?

2) Доказать, что, хоть и с пересадками, но из Фрейдинска в Лаканово можно доехать

1)Число концов дорог 98 · 2 + 5 + 1 = 202. Самих дорог, соответственно, 202:2=101

2) Требуется показать, что столица и город находятся в одной компоненте связности.

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

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

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

Рис. 4.2(4)

Непересекающиеся части, на которые граф разбивает плоскость, включая внешнюю часть, называются гранями (странами). Иными словами, Грань планарного графа — максимальный участок

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

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