Смежность, инцидентность, степени.
Тема 4 Элементы теории графов
Лекции 7-9
Цель: изучить одно из важнейших понятий дискретной математики – понятие графа, его виды, элементы и свойства; определить матрицы, соответствующие графам; изучить понятие изоморфизма графов; научиться применять графы при решении задач.
План:
1. Определение графов.
2. Смежность, инцидентность, степени.
3. Маршруты, пути, циклы, связность.
4.Способы задания графов.
5. Операции над частями графа.
6. Изоморфизм графов.
7. Эйлеровы и гамильтоновы графы.
8. Ориентированные графы. Пути в орграфах
9. Кратчайший путь. Применение теории графов при проектировании коммуникационных сетей.
Литература: 1. Москвинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях : учебное пособие / Г.И. Москвинова – М. : Логос, 2000. – 240 с.: ил.
2. Е.В. Шикин, А.Г. Чхартишвили. Математические методы и модели в управлении.
3. М.С. Красс, Б.П. Чупрынов. Основы математики и ее приложения в экономическом образовании.
Для чего, в самом деле, полюса, параллели,
Зоны, тропики и зодиаки?
И команда в ответ: «В жизни этого нет,
Это - чисто условные знаки».
Льюис Кэрролл. Охота на Снарка.
"Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, при помощи которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может".
|
|
|
 |
Из письма Л. Эйлера от 13 марта 1736 г.
- Определение графов
Одним из наиболее важных понятий, относящихся к структуре дискретных систем, является понятие графа. Это понятие, описывающее структуру связей между отдельными частями системы, в силу своей общности используется во многих математических моделях.
Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих объектов. Например, блок-схема алгоритма представляет собой орграф, в котором вершинами являются отдельные операторы, а дуги указывают переходы между ними. Другие примеры графов: схема дорог, узлы и соединения в электрической цепи, множество предприятий с указанием двухсторонних связей между ними, структура управления с указанием объектов и их подчиненности друг другу и т.д.
|
|
|
Определение. Граф 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) в орграфе считаются разными).
а) ориентированный граф б) неориентированный граф
Смежность, инцидентность, степени.
Опр. Две вершины в графе (орграфе) 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.
Дата добавления: 2022-01-22; просмотров: 95; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!