6

Тема 4 Элементы теории графов Лекции 7-9

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

План:

1. Определение графов.

2. Смежность, инцидентность, степени.

3. Маршруты, пути, циклы, связность.

4.Способы задания графов.

5. Операции над частями графа.

6. Изоморфизм графов.

7. Эйлеровы и гамильтоновы графы.

8. Ориентированные графы. Пути в орграфах

9. Кратчайший путь. Применение теории графов при проектировании коммуникационных сетей.

Литература: 1. Москвинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях : учебное пособие / Г.И. Москвинова – М. : Логос, 2000. – 240 с.: ил.

2. Е.В. Шикин, А.Г. Чхартишвили. Математические методы и модели в управлении.

3. М.С. Красс, Б.П. Чупрынов. Основы математики и ее приложения в экономическом образовании.

Для чего, в самом деле, полюса, параллели,

Зоны, тропики и зодиаки?

И команда в ответ: «В жизни этого нет,

Это - чисто условные знаки».

Льюис Кэрролл. Охота на Снарка.

"Мне была предложена задача об острове, расположенном в горо­де Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне достойным внимания тем, что для его решения не­достаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, при помощи которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно распо­ложенных мостов или не может".

Из письма Л. Эйлера от 13 марта 1736 г.

1. Определение графов

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

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

Определение. Граф G — фигура, состоящая из заданных точек (вершин), соединенных отрезками, которые, называются ребрами (дугами) графа G:

G = (V, E), где

V={v1,v2,...,v_n} - множество вершин графа;

E ={(vi,vj)} - семейство пар элементов из V, образующие ребра.

Опр.Граф (1,0) называется тривиальным.

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

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

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

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

а) неориентированный граф б) ориентированный граф

Опр. Ребро графа, концевые вершины которого совпадают, называется петлей (vi, vi). Ребра с одинаковыми концевыми вершинами называются кратными.

Опр. 1. Граф с кратными ребрами и петлями называют псевдографом (псевдоорграфом).

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

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

Примеры. 1.Псевдографы (в вершине 1 - петля).

а) ориентированный псевдограф б) неориентированный псевдограф

2. Мультиграфы (из вершины 1 идут две дуги/ребра в вершину 2).

в) ориентированный мультиграф г) неориентированный мультиграф

3. Графы(нет петель и кратных ребер/дуг: дуги (1,2) и (2,1) в орграфе считаются разными).

а) ориентированный граф б) неориентированный граф