Гамильтоновы графы - раздел Математика, ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Понятие Гамильтонова Графа Очень Близко К Понятию Эйлерова Гр...
Понятие гамильтонова графа очень близко к понятию эйлерова графа, но между ними пропасть, как вскоре выяснится!
ОПРЕДЕЛЕНИЕ 28.Цикл в графе называется гамильтоновым, если каждая вершина графа (кроме начальной) входит в него один раз. (Гамильтонов цикл по определению является простым!) Граф называется гамильтоновым, если в нем существует гамильтонов цикл. Не замкнутый путь в графе называется гамильтоновым, если каждая дуга графа входит в него один раз. Граф называется полугамильтоновым, если в нем существует гамильтонов путь.
Понятия эйлерова и гамильтонова графа независимы: для любой комбинации свойств «эйлеров – не эйлеров», «гамильтонов – не гамильтонов» найдется соответствующий граф! Попробуйте их построить.
В отличие от эйлеровости критерий гамильтоновости неизвестен, да и вряд ли простой критерий существует! Известны некоторые необходимые и некоторые достаточные условия. Докажем одно из достаточных условий.
Теорема 21(Дирак). Неориентированный граф с p вершинами, степени всех вершин которого не менее p/2, гамильтонов.
Пример цикла показывает, что необходимым условие теоремы не является.
Доказательство. Пусть существует граф Г, для которого утверждение нарушается. Поскольку полный граф очевидно является гамильтоновым, то граф Г неполный. Будем добавлять в него дуги, пока он не станет гамильтоновым. Степени вершин при этом могут только вырасти. В полученном гамильтоновом цикле удалим последнюю добавленную дугу, тем самым получим гамильтонову цепь. Занумеруем вершины графа в порядке прохождения вдоль этой цепи от 1 до p. Окрасим в красный цвет вершины, смежные с первой вершиной, и в синий – вершины предшествующие красным. Красных вершин (а тогда и синих) по условию не менее p/2. Значит, вершин, не окрашенных в синий цвет, меньше p/2. Поскольку степень p-й вершины не менее p/2, то существует синяя вершина, смежная с p-й (пусть ее номер k), при этом по построению (k+1)-я вершина смежна с первой. Цикл 1-2-…-k-p-(p-1)-…-(k+1)-1 гамильтонов, что противоречит предположению. При построении цикла использована неориентированность графа.
Проверка гамильтоновости графа и построение гамильтонова цикла в общем случае задача трудоемкая. Для этого применяются различные методы направленного перебора, наиболее распространенным из которых является поиск с возвращением. Суть этого метода состоит в том, что строится простая цепь, пока это возможно. При невозможности дальнейшего построения делается шаг назад, выбирается следующая вершина
Этот метод применим к широкому спектру задач. Полезно, например, рассмотреть задачу о расстановке на доске 6´6 шести ферзей таким образом, чтобы они не били друг друга.
К задаче о построении гамильтоновых циклов примыкает, возможно, самая известная задача комбинаторной оптимизации – задача коммивояжера(в русскоязычной литературе ее иногда называют задачей о бродячем торговце). Пусть есть сеть пунктов, где коммивояжеру необходимо побывать со своим товаром, причем по окончании надо вернуться домой. При этом известны расстояния между всеми парами пунктов (если проезд есть). Естественно, при этом маршрут коммивояжера должен быть кратчайшим. На языке теории графов необходимо найти гамильтонов цикл минимальной длины. Здесь также применим поиск с возвращением, который в этом случае называется методом ветвей и границ. Это название отражает то обстоятельство, что если один гамильтонов цикл уже построен, то его длина становится границей, переступать за которую нецелесообразно: если вес части пути превосходит границу, то надо делать шаг назад. Таким образом, если быстро получим гамильтонов цикл с длиной, близкой к минимальной, то это позволит ускорить поиск.
Все темы данного раздела:
Основной принцип комбинаторики
1.1.1 . От Москвы до Уфы можно добраться поездом, самолетом или теплоходом, а от Уфы до Чишмов – поездом, автобусом или на такси. Сколькими способами можно в совокупности добраться
Размещения с повторениями
1.2.1 . Замок в автоматической камере хранения состоит из 4 дисков, на каждом из которых написаны буквы а, б, в, г, д, е. Сколько различных кодов можно получить?
1.2.2 . В
Размещения без повторений
1.3.1 . Сколько словарей следует издать, чтобы можно было переводить тексты непосредственно с любого из шести языков на каждый из них? А если языков десять?
1.3.2 . Каков о
Перестановки
1.4.1 .Сколькими способами могут встать в очередь 10 человек?
1.4.2 . Каков ответ в задаче 1.3.3, если студентов 20?
1.4.3 . Каков ответ в задаче 1.3.4, если разли
Сочетания (без повторений)
1.5.1 .В шахматном турнире участвовали 10 человек. Сколько состоялось партий, если каждая пара игроков встретилась один раз?
1.5.2 .Из колоды карт (36 штук) игрок получает
Свойства биномиальных коэффициентов
1.6.1. Докажите, что . Сделайте это четырьмя способами: по определению, по формуле и используя результаты задач 1.5.6 и 1.5.7.
1.6.2. Докажите, что
.
Сдел
Разбиения множеств
Число сочетаний можно интерпретировать как число способов, которым n-элементное множество можно разбить на два подмножества, в одном из которых m, а во втором ( ) элем
Сочетания с повторениями
1.8.1. В магазине продаются карандаши двух видов. Сколькими способами можно купить пять штук? А если надо купить 8 карандашей 4 видов?
1.8.2. Каков ответ в задаче 1.2.4, ес
Разные задачи
В предыдущих параграфах вы познакомились с основными приемами элементарной комбинаторики. В этом параграфе эти приемы (или их комбинации) применяются в различных ситуациях.
Производящие функции
По биному Ньютона (задача 1.5.7) коэффициентами многочлена являются величины .
1.10.1. Каков смысл коэффициентов при zm многочленов
Использование рекуррентных соотношений
1.11.1. Пусть f(n.m) – число сочетаний с повторениями из n по m (задача 8.4). Проверьте, что
1.11.2. f(n.0)=1, f(
Формула включений и исключений
1.12.1. В группе 25 студентов, 15 занимаются лыжами, 12 – коньками, 8 и тем, и другим. Сколько студентов не занимается этими видами спорта?
1.12.2. (Обобщение) Проверьте, ч
Комбинаторные величины при больших значениях параметров
1.13.1. Докажите, что при n≥2.
1.13.2. Докажите, что биномиальные коэффициенты возрастают при возрастании k от 0 до и убывают при возрастании k о
Булеан множества
Каждое множество порождает новое множество несколько необычным образом.
ОПРЕДЕЛЕНИЕ 1. Булеаном множестваA называется совокупность всех подмножеств множества A
Прямое произведение множеств
ОПРЕДЕЛЕНИЕ 2. Прямым произведением множествA1, A2,…, An называется множество
A1´A
Отношения на множествах
ОПРЕДЕЛЕНИЕ 3. n-арным отношением на множествеA называется подмножество G прямого произведения An. Таким образом, n-арное отношение на A
Отображения (функции)
С понятием «функция»в некоторых частных случаях вы познакомились в школе. Приведем общее определение.
ОПРЕДЕЛЕНИЕ 7. Пусть A, B - множества. Отображением(ф
Мощность множеств
Речь пойдет о том, как сравнивать между собой разные множества. Начнем с простого примера. Перед вами кучки болтов и гаек. Требуется ответить на вопрос: поровну ли деталей в этих ку
Счетные множества
ОПРЕДЕЛЕНИЕ 15. Множество, равномощное множеству N, называется счетным.
Иными словами счетными являются такие множества, элементы которых можно занумеровать н
Некоторые свойства бесконечных множеств
Уже отмечалось, что конечное множество не равномощно своей части, в то же время, бесконечное множество может быть равномощным своей части. Оказывается, это характеристическое
Вопросы для самопроверки
1. Что такое объединение, пересечение, дополнение, симметрическая разность множеств?
2. Какими алгебраическими свойствами обладают операции над множествами?
3. Что
Упражнения
1. Существуют ли такие множества A,B,C, что
2. Справедливы ли следующие утверждения для любых A,B,C?
А) Если A¹B и B¹ C, то
Компьютерные представления графов
Естественно, графы представляются в виде некоторых наборов данных. Подобных представлений существует множество, у каждого есть свои достоинства и недостатки. Общий недостаток состои
Маршруты и связность
ОПРЕДЕЛЕНИЕ 22.Маршрутом (путем)в графе называется последовательность вида , где v – вершины, e – дуги, . Этот маршрут соединяет вершины
Кратчайшие пути в графах
Рассмотрим следующую задачу. В графе Г выделены две вершины: b (начальная) и e (конечная). Требуется найти все пути минимальной длины из b в e (если e
Деревья
ОПРЕДЕЛЕНИЕ 25.Лесомназывается неориентированный граф без циклов. Деревомназывается связный лес.
Таким образом, дерево характеризуется тремя
ПРЕДЛОЖЕНИЕ.
1. Всякие две вершины дерева можно соединить единственной цепью.
2. Если в дереве не менее двух вершин, то у него не менее двух листов.
Доказательство.
1. Поскольку дерев
Кодирование деревьев
Для помеченных деревьев существует эффективный способ кодирования(его можно использовать для компьютерного представления деревьев).
Найдем лист с минимальным номером, удали
Центр дерева
Под расстоянием d(a,b) между вершинами неориентированного графа, как и ранее, понимается минимальное число дуг в пути, соединяющем эти вершины.
Минимальное остовное дерево(остов)
Пусть некоторое семейство пунктов требуется связать сетью дорог. Известна стоимость прокладки дороги между теми парами пунктов, для которых это возможно. Стоимость прокладки сети до
Эйлеровы графы
Вернемся к задаче Эйлера о кенигсбергских мостах. По существу, задача сводится к построению в графе цикла, который содержит каждую дугу графа по одному разу. Графы, в которых такой
Графовые векторы
Понятие степени вершины было введено выше.
ОПРЕДЕЛЕНИЕ 29.Графовым вектором(иногда говорят о графовом разбиении) неориентированного графа называется
Паросочетания и реберные покрытия
ОПРЕДЕЛЕНИЕ 30.Паросочетаниемв неориентированном графе называется семейство дуг, попарно не имеющих общих вершин.
Очевидно, что подмножество паросоч
Паросочетания в двудольных графах
Двудольные графы упоминались ранее, но формального определения не было.
ОПРЕДЕЛЕНИЕ 32.Граф Г называется двудольным, если множество его вершин являе
Правильная нумерация вершин графа
ОПРЕДЕЛЕНИЕ 33.Нумерация вершин в ориентированном графе называется правильной(или топологической), если наличие дуги (vi,vj
Сетевые графики
ОПРЕДЕЛЕНИЕ 34.Сетевым графикомназывается ориентированный взвешенный ациклический граф с единственным истоком и единственным стоком.
Сетевые графики
Потоки в сетях
Весам дуг можно дать иную интерпретацию, в результате возникает интересная и важная задача. Пусть в ориентированном взвешенном графе выделены две вершины (b – начальная и
Вопросы для самопроверки
1. Что такое граф? Из чего он состоит? Какие виды графов вы знаете?
2. Какие вершины, дуги называются смежными? Инцидентными?
3. Какие графы называются изоморфными
Упражнения
1. Существует ли неориентированный граф, степени всех вершин которого различны?
2. Постройте неориентированный граф, степени вершин которого равны 2,2,2,3,3,4,5. Существует
Предметный указатель
n-арное отношение на множестве, 21
алгоритм Дейкстры, 50
алгоритм построения матрицы достижимости, 48
Новости и инфо для студентов