- •Введение
- •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.11. Эйлеровы графы.
Содержательная постановка задачи о Кенигсбергских мостах дана в теме 1. Переформулируем эту задачу в терминах теории графов. Для этого рассмотрим следующий неориентированный мультиграф/
Рис. 33
В этом графе вершины v1 и v4 соответствуют берегам, а v2 и v3 – островам. Ребра отображают мосты. Таким образом, на языке теории графов исходная задача формулируется следующим образом: существует ли в указанном мультиграфе цикл, содержащий все ребра данного мультиграфа?
Определение: Цепь (цикл), содержащая все ребра графа и притом по одному разу, называется эйлеровой цепью (эйлеровым циклом). Граф, содержащий эйлеров цикл, называется эйлеровым графом.
Теорема. Для того, чтобы конечный связный неориентированный мультиграф был эйлеровым необходимо и достаточно, чтобы все его вершины имели чётные степени.
Доказательство:
Необходимость. Предположим, что граф является эйлеровым. Это значит, что, в нём есть эйлеров цикл. При этом каждый раз, когда эйлеров цикл проходит через какую-либо вершину, он должен войти в нее по одному ребру, а выйти по другому. Следовательно, условие отсутствия вершин нечетной степени является необходимым.
Достаточность.
Предположим, что все вершины связного
графа G
имеют чётные степени. Тогда, в силу
связности графа G,
для всех его вершин выполняется условие
d(v)>0.
Кроме того, в силу чётности
вершин,
должно быть d(v)2
для всех v.
По теореме Эйлера имеем:
.Это
значит, что:
или
,
и следовательно граф
G
не является деревом, а поэтому он содержит
хотя бы один простой цикл Z1
(Z1
- множество ребер), тогда G\Z1
– остовный подграф, в котором все степени
вершин также четные. Исключим из
рассмотрения изолированные вершины,
тогда в графе G\Z1
существует простой цикл Z2G\Z1,
далее выделим Z3
и т.д. В результате этого получается
разбиение множества ребер на простые
циклы, то есть:
,где
.
Далее,
возьмем какой-либо простой цикл
из полученного разбиения. Если
,
то теорема доказана. Если нет, то в силу
связности графа G,
существуют цикл
и вершина v1
такие, что
и
.
Маршрут, объединяющий
и
,
является циклом. Если
,
то теорема доказана. Если нет, то имеется
цикл
,
при котором существует вершина v2
такая, что
и
.
Далее будем наращивать эйлеров цикл до
тех пор, пока не исчерпаем всё разбиение.
В результате получаем эйлеров цикл
всего графа.
Алгоритм построения эйлерова цикла в эйлеровом графе.
Этот алгоритм задается следующими правилами:
Выбирается произвольная вершина v.
Выбирается ребро e инцидентное вершине v и ему присваивается номер 1 (это ребро называется пройденным).
Каждое пройденное ребро вычеркивается и ему присваивается номер на 1 больший номера предыдущего вычеркнутого ребра.
При нахождении в произвольной вершине x, не выбирается ребро, соединяющее x с v, если есть возможность другого выбора.
Ребро не проходится, если оно является перешейком. Перешейк – это ребро, при удалении которого, граф, образованный невычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы одно ребро.
После того, как в графе будут занумерованы все ребра, образуется эйлеров цикл, нумерация рёбер которого соответствует последовательности обхода ребер.
П
ример.
Найти эйлеров цикл в эйлеровом графе
Рис. 34
После выбора вершины v и прохождения рёбер 1 и 2 имеется три возможности: выбрать 3,6 или 7. Ребро 7 является перешейком, поэтому выбирается любое из оставшихся рёбер, например 3. Далее идёт обход оставшихся рёбер получается эйлеров цикл.
