 |
Понятия смежности, инцидентности, степени
|
|
|
|
Федеральное агентство по образованию Российской Федерации
Государственное образовательное учреждение высшего
Профессионального образования
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Теория графов
ПРАКТИКУМ
По дисциплине «Дискретная математика»
Уфа 2005
Федеральное агентство по образованию Российской Федерации
Государственное образовательное учреждение высшего
профессионального образования
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра вычислительной математики и кибернетики
Кафедра проектирования средств информатики
ТЕОРИЯ ГРАФОВ
ПРАКТИКУМ
по дисциплине «Дискретная математика»
Уфа 2005
Составители: Н.И. Житникова, Г.И. Федорова, А.К. Галимов
УДК 519.6 (07)
ББК 22.193 (я7)
Теория графов. Практикум по дисциплине «Дискретная математика». /Уфимск. гос. авиац. техн. ун-т.; Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005 -39 с.
Предназначен для студентов направлений 010503: «Математическое обеспечение и администрирование информационных систем», 230100: «Информатика и вычислительная техника» для подготовки к практическим занятиям по дисциплине «Дискретная математика».
Ил. 15. Библиогр.: 9 назв.
Рецензенты: - зам. зав. кафедрой ВМК УГАТУ
д.ф.-м.н., проф. Бронштейн Е.М.
- зав. каф. высшей алгебры и геометрии БашГУ
д.ф.-м.н., проф. Хабибуллин Б.Н.
© Уфимский государственный
авиационный технический университет, 2005
Содержание
Введение ………………………………………………………………… 5
Цели и задачи...…………………………………………………………. 5
|
|
|
1. Краткий перечень основных понятий теории графов.…………….. 6
1.1. Общие понятия ……………………………………………………... 6
1.2. Понятия смежности, инцидентности, степени …….……………... 8
1.3. Маршруты и пути ……………………………….………….………. 8
1.4. Матрицы смежности и инцидентности…..….……………………. 9
1.5. Связность. Компоненты связности……………………………….. 10
1.6. Матрицы достижимости и связности……….……………………. 10
1.7. Расстояния в графе………………………..…………….…………. 11
1.8. Образ и прообраз вершины и множества вершин …………..…... 11
1.9. Нагруженные графы ………………..……………………………... 12
1.10. Деревья и циклы ………………………….………….…………... 13
2. Решение контрольных задач …………………………...…………… 14
2.1. Компоненты сильной связности ориентированного графа..……. 14
2.2. Расстояния в ориентированном графе..…………………………... 17
2.3. Минимальный путь в нагруженном ориентированном графе...... 21
2.4. Эйлеровы циклы и цепи……………..………………………….…. 23
2.5. Минимальное остовное дерево…………………………………… 25
2. 6. Задача о коммивояжёре…………………………………………... 27
3. Задания для самостоятельного решения ……….…………...……... 35
Список литературы…………………………………………………..… 38
Введение
Теория графов – это математический аппарат для формализации (моделирования) реальных задач по исследованию свойств конечных множеств с заданными отношениями между их элементами. В их числе задачи из области администрирования сетей, информационных потоков, планирования, проектирования и управления различными системами.
Задачи на графах удобно переводить на языки программирования, то есть решать с использованием современной вычислительной техники.
Умение решать задачи на графах позволит будущему специалисту приобрести опыт разработки технологий и методов теории операций для решения задач при научных исследованиях и проектно-конструкторской деятельности
|
|
|
В данном практикуме рассмотрены основные типы задач на графах, подходы и методы их решения, конкретные примеры.
Цели и задачи
Цель раздела «Теория графов» состоит в формировании у студентов умений и навыков, необходимых при исследовании различных систем и проектировании технических объектов.
Для достижения указанной цели решаются следующие задачи:
- формирование знаний методов и алгоритмов эффективного решения задач дискретной оптимизации;
- формирование умений и навыков использования изученных методов для решения типовых задач математического моделирования и оценки пределов применимости полученных результатов.
Краткий перечень основных понятий теории графов
Общие понятия
Графы помогают описывать и исследовать различные системы объектов и их связи. Например, в графе, изображенном на рис. 1, точки (вершины графа) можно интерпретировать как города, а линии, соединяющие вершины (ребра), как дороги, соединяющие эти города.
Рис. 1.
Формальное определение графа таково [1-9]. Графом Г=(V, X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами. Если v, w Î V, x=(v,w)ÎX, то говорят, что ребро x соединяет вершины v и w или x инцидентно v и w. Таким образом, {v,w} – обозначение ребра. Если Х представляет собой упорядоченные пары (т. Е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары {v,w} называют дугами. Если множеству X принадлежат пары v = w, то такие ребра (v, v) называют петлями. Существование одинаковых пар {v,w} соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар.
Например, кратность ребра { v 1,v2} в графе, изображенном на рис. 2, равна двум, кратность ребра { v 3,v4} − трем.
Рис.2.
Псевдограф − граф, в котором есть петли и/или кратные ребра.
Мультиграф − псевдограф без петель.
Заметим, что графом также называют мультиграф, в котором ни одна пара не встречается более одного раза.
Итак, используемые далее обозначения:
V – множество вершин;
X – множество ребер или дуг;
|
|
|
v (или vi)– вершина или номер вершины;
G, G 0 – неориентированный граф;
D, D 0 – ориентированный;
{ v, w } − ребра неориентированного графа;
{ v, v } – обозначение петли;
(v, w) − дуги в ориентированном графе;
v, w – вершины, x, y, z – дуги и ребра;
n (G), n (D) количество вершин графа;
m (G) – количество ребер, m (D) – количество дуг.
Примеры
1) Ориентированный граф D =(V, X), V ={ v 1, v 2, v 3, v 4},
X ={ x 1=(v 1, v 2), x 2=(v 1, v 2), x 3=(v 2, v 2), x 4=(v 2, v 3)}.
Рис. 3.
2) Неориентированный граф, изображенный на рис. 4:
G =(V, X), V ={ v 1, v 2, v 3, v 4, v 5},
X ={ x 1={ v 1, v 2}, x 2={ v 2, v 3}, x 3={ v 2, v 4}, x 4={ v 3, v 4}}.
Рис. 4.
Понятия смежности, инцидентности, степени
Если x ={ v, w } - ребро, то v и w − концы ребра x.
Если x =(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.
Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).
Вершины v, w называются смежными, если { v, w }Î X.
Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.
Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.
Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).
Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).
Маршруты и пути
Последовательность v 1 x 1 v 2 x 2 v 3… x k v k+1, (где k ³1, v iÎ V, i =1,…, k +1, x iÎ X, j =1,…, k), в которой чередуются вершины и ребра (дуги) и для каждого j =1,…, k ребро (дуга) x j имеет вид { vj, vj +1} (для ориентированного графа (vj, vj +1)), называется маршрутом, соединяющим вершины v 1 и vk +1 (путем из v 1 в vk +1).
Пример
В графе, изображенном на рис.4, v 1 x 1 v 2 x 2 v 3 x 4 v 4 x 3 v 2 – маршрут, v 2 x 2 v 3 x 4 v 4 – подмаршрут;
маршрут можно восстановить и по такой записи x 1 x 2 x 4 x 3;
если кратности ребер (дуг) равны 1, можно записать и так v 1 v 2 v 3 v 4 v 2.
Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.
|
|
|
Цикл − замкнутая цепь (в неориентированном графе).
Контур − замкнутый путь (в ориентированном графе).
Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.
Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.
Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.
Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.
Длина маршрута (пути) − число ребер в маршруте (дуг в пути).
Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.
Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.
|
|
|
