- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
6.12 Гамильтоновы графы.
Н азвание «гамильтонов граф» произошло от задачи «кругосветное путешествие», придуманной Гамильтоном в 19 веке. Нужно обойти все вершины графа, изображенного на рисунке, по одному разу и вернуться в исходную точку.
Рис. 35
Гамильтоновой цепью неорграфа называется цепь, проходящая через его вершину один и только один раз.
Гамильтоновым циклом неорграфа называется цикл, проходящий через каждую вершину один и только один раз, за исключением начальной вершины, совпадающей с конечной.
Граф, содержащий гамильтонов цикл называется гамильтоновым.
Гамильтоновым контуром называется контур орграфа, который проходит через все его вершины, причем только по одному разу.
Эйлеровы и гамильтоновы циклы сходны по способу задания. Эйлеровы содержат все ребра по одному разу, а гамильтоновы – все вершины так же по одному разу. Несмотря на это внешнее сходство, задачи отыскания соответствующих циклов резко отличаются. Так для решения вопроса о существовании эйлерова цикла, достаточно выяснить четность всех вершин графа. Эффективного критерия существования гамильтонова цикла пока ещё не найдено. Известны лишь несколько теорем, дающих достаточные условия существования гамильтоновых циклов.
Теорема 1. В полном, конечном графе (любая пара вершин которого соединена хотя бы в одном направлении) всегда существует гамильтонов цикл.
Теорема 2. Если для любой пары несмежных вершин vi и vj графа G с n вершинами справедливо неравенство d(vi)+d(vj)n , то граф обладает гамильтоновым циклом.
Теорема 3. Граф G с n вершинами имеет гамильтонов цикл, если для любой вершины vi выполняется неравенство d(vi)n\2,где n – число вершин в графе.
6.13. Планарные графы.
При изображении графа имеется полная свобода при размещении вершин и выборе формы соединяющих их ребер. Геометрическим графом называется множество точек в n-мерном евклидовом пространстве, взаимосвязанных между собой набором непрерывных самонепересекающихся кривых.
Теорема 1. В трехмерном пространстве любой конечный граф можно представить так, что линии, соответствующие ребрам (дугам) не пересекаются во внутренних точках.
Доказательство. Пусть граф G=(V,E) содержит n вершин и m рёбер. Возьмём прямую в трёхмерном пространстве и проведём через неё m различных плоскостей. На прямой выделим точки , которые будут соответствовать вершинам графа . Каждое ребро графа G будет соответствовать одной из проведённых плоскостей. Пусть - ребро графа G. В плоскости, соответствующей ребру e, соединим точки ai и aj дугой окружности. Выполнив такое построение для всех рёбер графа G, получим из точек и дуг окружностей требуемую геометрическую реализацию графа G. Теорема доказана.
У кладкой графа на некоторой поверхности называется такое его изображение на этой поверхности, при котором никакие два ребра не будут иметь общих точек, кроме быть может, общего конца этих ребер. Плоский граф – это граф, уложенный на плоскости. Граф называется планарным, если его можно уложить на плоскости. Например, граф, изображённый на рисунке слева, является планарным, так как он может быть уложен на плоскости, как показано справа.
Рис. 36
Область, ограниченная ребрами (дугами) в плоском графе, и не содержащая внутри себя вершин и ребер называется гранью.
Число граней плоского графа обозначается r(G). При этом считается, что внешняя часть плоскости графа также образует грань. Например, вышеприведенный граф К4 (полный граф с 4-я вершинами) имеет 4-е грани.
Для графов, уложенных на некоторой поверхности справедливо определенное соотношение между числом вершин, ребер и граней. Это соотношение называется эйлеровой характеристикой поверхности.
Теорема 2 (Формула Эйлера). В связном планарном графе справедливо соотношение , где n – число вершин, m – число ребер, r –число граней.
Доказательство. Проводится по индукции числа m. Во-первых, при m=0, имеем n=1 и r=1, то есть, теорема справедлива. Во-вторых, положим, что теорема верна для всех графов с m рёбрами, то есть справедливо выражение n-m+r=2. В третьих, добавим к графу ещё одно ребро. Если добавляемое ребро соединяет существующие вершины, то число рёбер в новом графе , число вершин - и число граней - . Следовательно, . Если добавляемое ребро соединяет существующую вершину с новой вершиной, то имеем и следовательно . Таким образом, теорема доказана.
Следствие 1. Если G – связный планарный граф, у которого n>3, то m3n-6.
Доказательство. Обозначим через mi – число рёбер в i-ой грани. Каждая грань плоского графа ограничена, по крайней мере, тремя рёбрами, то есть .Суммируя по всем граням и учитывая то, что каждое ребро входит в две грани, получим: или . В соответствии с эйлеровой характеристикой плоскости имеем:
.
Что и требовалось доказать. Прежде чем приступать к формулировке следующего следствия, необходимо ознакомиться с рядом определений.
Неориентированный граф G называется двудольным, если множество всех ребер графа образует разрез графа, т.е. для некоторого разбиения вершин {V1, V2}, концы любого ребра принадлежат разным частям разбиения.
Если двудольный граф содержит все рёбра соединяющие множества V1 с V2, то он называется полным двудольным графом.
Если |V1|=m, а |V2|=n, то полный двудольный граф обозначается Km,n.
Например, граф K3,3 имеет следующий вид:
Рис. 37
Следствие 2. Графы К5 и К3,3 непланарны.
Доказательство: (от противного) Предположим, что граф К5 – планарен, тогда по первому следствию – получили противоречие, следовательно, граф К5 не является планарным.
Пусть далее К3,3 – планарен. Для него имеем n=6, m=9. В этом графе нет треугольников, а так как. граф планарен, то при его плоской укладке каждая грань ограничена не менее, чем 4 ребрами. Из этого следует, что , а значит 2rm. В соответствии с эйлеровой характеристикой плоскости имеем: 6-9+r=2, следовательно r=5. Таким образом: - противоречие, а это значит, что К3,3 непланарен.
Теорема Понтрягина-Куратовского (критерий планарности).
Граф G планарен тогда и только тогда, когда G не содержит подграфа гомоморфного К5 или К3,3. Эквивалентная формулировка этой теоремы: неориентированный граф G планарен тогда и только тогда, когда G не содержит подграфов, стягиваемых (т.е. получаемых последовательностью отождествлений вершин, связанный ребрами) к графу К5 или К3,3.
Если граф непланарен, то для его плоской реализации удаляют отдельные рёбра, перенося их на другую плоскость. Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения называется числом планарности графа G.
При вынесении этих ребер на вторую плоскость, получается часть графа, которая также может оказаться неплоской. Тогда вновь возникает задача вынесения отдельных ребер на следующую плоскость и т.д.
Минимальное число плоскостей, при которых граф G разбивается на плоские части G1, G2, …, Gm (разбиение производиться по множеству ребер) называется толщиной графа G.
Например, толщина планарного графа равна 1, а графы К5 и К3,3 имеют толщину равную 2.