ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.06.2021

Просмотров: 103

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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,...,vn} - множество вершин графа;

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

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


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

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

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

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


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


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

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

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

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

П

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


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



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

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

3

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

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



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

Опр. Две вершины в графе (орграфе) G называются смежными, если существует ребро(дуга), которая их соединяет. Пусть v, w вершины, а e=(v,w) - ребро (дуга) их соединяющая. Тогда вершина v и ребро (дуга) e являются инцидентными, вершина w и ребро (дуга) e также являются инцидентными. Два ребра инцидентные одной вершине называются смежными.


Пример 1.2.1. Рассмотрим неориентированный граф на рис.1.1.1.в).

Вершины 1,2 -смежные, а вершины 2,3 не являются смежными.

Вершина 1 инцидентна ребру (1,2). Ребро (2,3) инцидентно вершине 2.

Вершина 1 не инцидентна ребру (3,2).

Ребра (1,2) и (3,2) смежные, т.к. у них есть общая вершина.


Пример 1.2.2. Рассмотрим ориентированный граф на рис. 1.1.1.в).

Вершины 1,2 -смежные, а вершины 2,3 не являются смежными.

Вершина 1 инцидентна дуге (1,2). Дуга (2,3) инцидентна вершине 2.

Вершина 1 не инцидентна дуге (3,2).


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

Вершина графа, имеющая степень 0, называется изолированной, а вершина степени 1 называется висячей.

Степень вершины - На рис. 4 изображен граф с пятью вершинами: d(A)=1, d(Б)=2, d(В) =3, d(Г)=2, d(Д)=0.



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

С уществует всего 4 разных графа порядка 3.



Теорема: Сумма степеней вершин графа равна удвоенному числу его ребер.

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


Опр. Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно.


Полустепенью исхода вершины v орграфа G называется число 6 (v) дуг исходящих из вершины v (т.е. v является началом этих дуг).


Полустепенью захода вершины v орграфа G называется число 6 (v) дуг входящих в вершину v (т.е. v является концом этих дуг).


Замечание. В случае неориентированного псевдографа вклад каждой петли при расчете степени инцидентной вершины равен 2.


Пример 1. Рассмотрим ориентированный псевдограф, изображенный на рис.1.1.1.

а: d-(1)=2, d+(1)=2, d-(2)=0, d+(2)=1.


Пример 2. Рассмотрим неориентированный псевдограф, изображенный на рис.1.1.1.

а: d(1)=4, d(2)= 1, d(3)=1.



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


Пусть G=(V,E) граф с p вершинами и q ребрами, т.е.

V={v1,v2,…,vp}, E={e1,e2,…,eq}.

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

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

1 . Две цепи из трех разных ребер:

2 . Три разные ребра, из которых нельзя образовать цепь:

Опр. Цепь называется простой, если ее вершины различны, кроме, может быть первой и последней.

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


Пример:

Дан граф G.

х1 x2 х3 х6 х7 х2— Маршрут длины 6, соединяющий вершины v1 и v2.

х1 x2 х3 х6 х7 х2 х1— замкнутый маршрут длины 7. Он начинается и заканчивается в вершине v1.

х1 x2 х3 х6 х7 — цепь длины 5 (все ребра в ней различны). Эта цепь не является простой, так как при обходе вершину v3 мы посетили два раза.

х1 x2 х3 — пример простой цепи (все вершины на нашем пути были различны).

х6 х7 х8 х3 — цикл.

х7 х6 х3 — простой цикл.


Опр. Граф без циклов называется ациклическим.

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

Опр. Две вершины графа называются связными, если существует соединяющая их простая цепь. В противном сл. две вершины графа называются несвязными.

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

Опр. Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G. Если G1 – подграф графа G, то G называется надграфом графа G1.

Опр. Остовный подграф - это подграф графа, содержащий все его вершины.


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


4. Матрицы, соответствующие графам.

Пусть дан граф G с вершинами v1,..., vn и ребрами xh ..., хт.

Матрица смежности графа G — это матрица A(G) размера пхп (п — число вершин) с элементами, равными 1, если в графе вершина vi смежна с вершиной vj, и элементами, равными 0, в других случаях.


Матрица инцидентности графа G — это матрица B(G) размера пхm (п — число вершин, т — число ребер) с элементами, равными 1, если вершина vi и ребро xj - инцидентны, и элементами, равными 0, в других случаях.

Для графа G построим матрицу смежности A(G) и матрицу инцидентности B(G).




Так как у графа 5 вершин и 6 ребер, то размеры матрицы смежности будут 5x5, а матрицы инцидентности - 5x6.

Пусть дан граф D с вершинами v1,..., vn и ребрами xh ..., хт.

Матрица смежности орграфа D — это квадратная матрица A(D) размера п*п (п — число вершин) с элементами, равными 1, если в орграфе вершины vi vj соединены дугой, и элементами, равными 0, в других случаях.


М атрица инцидентности орграфа D — это матрица B(D) размера п *т (п — число вершин, т — число ребер) с элементами, равными 1, если j -ая дуга заканчивается в i-ой вершине, с элементами, равными (-1), если j-ая дуга начинается в i-ой вершине, и элементами, равными 0, в других случаях.

Для орграфа D (рис. 9) построим матрицу смежности и матрицу инцидентности.

О
рграф содержит 5 вершин и 6 ребер, поэтому