- •В.С. Васильева, с.В. Коровина, л.В. Марченко дискретная математика
- •Васильева, в.С.
- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия теории множеств. Способы задания множеств
- •1.2. Операции над множествами
- •1.3. Диаграммы Эйлера – Венна
- •1.4. Свойства операций над множествами
- •1.5. Декартово произведение множеств
- •1.6. Бинарные отношения. Свойства бинарных отношений
- •1.7. Функция
- •2. Элементы математической логики
- •2.1. Математическая логика как наука
- •2.2. Высказывания. Логические операции и их основные свойства
- •Логические операции
- •Новые логические операции
- •2.3. Способы решения логических задач
- •2.4. Булевы функции. Свойства элементарных булевых функций
- •2.5. Дизъюнктивные и конъюнктивные нормальные формы булевых функций
- •2.6. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •3. Элементы теории графов
- •3.1. Основные понятия теории графов
- •3.2. Способы задания графов
- •3.3. Связность графов
- •4. Элементы комбинаторики
- •4.1. Перестановки, размещения и их количество
- •4.2. Сочетания и их свойства
- •4.3. Выборки с повторением
- •5. Индивидуальные задания
- •Заключение
- •Библиографический список
- •Оглавление
3. Элементы теории графов
3.1. Основные понятия теории графов
Графы возникли в XVIII столетии, когда известный математик, Леонард Эйлер пытался решить теперь уже классическую задачу о Кёнигсбергских мостах. В то время в городе Кёнигсберге (Калининград) было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом.
Задача состояла в том, что необходимо было совершить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка.
В 1736 г. Эйлер показал, что сделать это невозможно.
С тех пор поток задач с применением графов нарастал. Однако теория графов как математическая дисциплина сформировалась только в середине 30-х гг. XX в. благодаря работам таких математиков, как Г. Кёниг, Л.С. Понтрягин, А.А. Зыков и др.
Впервые же понятие «граф» ввел венгерский математик Д. Кёниг в 1936 г.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема движения автобуса. Точками на ней представлены остановки, а линиями – пути движения автобуса. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое дерево. И это дерево – граф. Применяются графы для решения задач химии, экономики, электротехники и автоматики, также широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.
Определение 1. Неориентированным графом (или графом) называется совокупность двух множеств – непустого множества (множества вершин) и множества неупорядоченных пар различных элементов множества(–множество ребер).
Обычно граф изображают в виде диаграммы, на которой вершины обозначаются точками, а ребра, соединяющие две вершины, – линиями между этими точками.
Например, изображение графа с множеством вершин и множеством реберможет иметь следующий вид (рис. 12).
Изображение графа с множеством вершин и множеством реберможет иметь вид, представленный на рис. 13.
| |
Рис. 12 |
Рис. 13 |
Определение 2. Пусть – вершины,– соединяющее их ребро. Тогда вершинаи реброинцидентны, вершина и ребротакжеинцидентны, при этом называютсяконцами ребра. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Определение 3. Ребро, соединяющее вершину саму с собой, называют петлей. Ребра, инцидентные одной и той же паре вершин, называются параллельными, или кратными.
Определение 4. Степенью вершины называется удвоенное количество петель, инцидентных этой вершине, плюс количество остальных инцидентных ей ребер. Обозначение:. Вершина степени 0 называетсяизолированной, а степени 1 – висячей (концевой). Ребро, инцидентное висячей вершине, называют концевым.
Например, в графе (рис. 14) вершины и– смежные,иинцидентны ребруи являются его концами;– смежные ребра; вершиныине являются смежными, поскольку между ними есть вершина,и– не являются смежными ребрами:
, .
В графе (рис. 15) вершина – изолированная, вершина– висячая; ребро, соединяющее вершинусаму с собой, образует петлю:
, ,.
| |
Рис. 14 |
Рис. 15 |
Теорема 1. Сумма степеней вершин графа всегда четная.
Теорема 2. Сумма степеней всех вершин графа равна удвоенному числу ребер, т. е. , где– число ребер.
Определение 5. Ребро, имеющее направление от одной вершины к другой, называется направленным (или ориентированным, или дугой) и изображается стрелкой, направленной от вершины, называемой началом, к вершине, именуемой концом. Граф, содержащий направленные ребра, называется ориентированным графом (или орграфом).
Замечание 1. В орграфе у каждой вершины две степени: входящая (число ребер, входящих в вершину) и исходящая (число ребер, выходящих из вершины). Петля несет вклад в обе степени по одному.
Например, изображение орграфа (рис. 16) с множеством вершини множеством дуг.
Рис. 16
Дуга : 1 – начало дуги, 2 – конец дуги;– петля; ребра,– кратные: , ,, , .
Определение 6. Чередующаяся последовательность вершин и ребер в графе (или только ребер), в которой любые два элемента инцидентны, называется маршрутом. Количество ребер , входящих в маршрут, называютдлиной маршрута.
Определение 7. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью.
Определение 8. Замкнутая цепь называется циклом, а замкнутая простая цепь – простым циклом.
Определение 9. Цикл, который содержит все ребра графа, называется эйлеровым циклом. Простой цикл, содержащий все вершины графа, называется гамильтоновым.
Например, в графе (рис. 17):
–маршрут, но не цепь (длина – 3);
–цепь, но не простая цепь (длина – 5);
–простая цепь (длина – 4);
–цикл, но не простой цикл (длина – 6);
–простой цикл (длина – 3).
Определение 10. Для орграфов цепь называется путем, а цикл – контуром.
Например, в орграфе (рис. 18):
и – пути;
–контур.
Рис. 17 |
Рис. 18 |
Основные виды графов:
мультиграф – граф, содержащий кратные ребра;
граф с петлями – граф, содержащий петли (рис. 15);
псевдограф – граф, содержащий как петли, так и кратные ребра (рис. 16);
простой граф – граф без петель и кратных ребер (рис. 14);
полный граф – простой граф, в котором каждая пара вершин соединена ребром (рис. 19);
дерево – простой граф, не содержащий циклов;
эйлеровый граф – граф, содержащий эйлеровый цикл;
гамильтоновый граф – граф, содержащий гамильтоновый цикл.
Рис. 19
Вопросы и задачи для самостоятельного решения
1. Для следующего графа (рис. 20):
а) выпишите смежные вершины и смежные ребра;
б) выпишите вершины с инцидентными ребрами;
в) определите степени каждой вершины графа;
г) укажите, как называются вершины ; ребраV и VI;
д) укажите, как называется такой граф.
2. Для следующих графов определите, чем являются последовательности ребер и вершин.
2.1. Для графа на рис. 21:
а) ; в);
б) ; г).
2.2. Для графа на рис. 22:
а) ; в);
б) ; г).
2.3. Для графа на рис. 23: .
3. Для следующего графа (рис. 24):
а) выпишите степени всех вершин;
б) определите, чем являются последовательности ребер и вершин: 1, 2, 1, 3, 4 и 1, 2, 4.
Рис. 20 |
Рис. 21 |
Рис. 22 |
Рис. 23 |
Рис. 24 |
Найдите эйлеровый граф (рис. 25).
а
б
в
Рис. 25