Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
·вольная вершина V1 графа G принимает цвет 1.
. Если вершины V1, …, Vi раскрашены l цветами е, 2, … е, е ? i, то новой произвольно взятой вершине Vi+1 припишем минимальный цвет, не использованный при раскраске вершин из множества {Vj | ? (Vi+1, Vj) = 1, j < i}.
Для некоторых классов графов последовательная раскраска является минимальной. В общем случае это не так.
Все двудольные графы бихроматические, Х (G) = 2.
Пример:
бихроматическийдвудольный
Любой бихроматический граф является двудольным.
Теорема: для того, чтобы граф был бихроматическим, необходимо и достаточно, чтобы он был связным и не содержал элементарных циклов нечетной длины.
Дано: G - бихромат. граф
Док-ть: связный и не содержит циклов нечетной длины
Док-во (от противного)
Пусть граф содержит циклический элемент
Х = 3, но G - бихромат - противоречие.
Обратная теорема:
Дано: G - связный, не содержит циклов нечет. длины
Док-ть: Х (G) = 2
Док-во:
) рассм. связный граф, который не имеет циклов
) граф, содержит циклы четной длины
5. Эйлеровы и гамильтоновы графы
Как указано в предисловии, задача о Кенигсбергских мостах послужила началом математической теории графов. План расположения семи мостов в Кенигсберге приведен на рис.39.
Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку С. Так как существенны только переходы через мосты, план города можно свести к изображению графа, в котором ребра соответствуют мостам, а вершины - различным разделенным частям города (рис.40).
Очевидно, не существует циклических обходов, проходящих по всем ребрам по одному разу.
Эйлеровым путем в графе называется путь, содержащий все ребра графа.
Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.
Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Принято всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называть универсальной (рис.41).
Рис. 41
Теорема: Если граф обладает эйлеровым циклом, то он связный и всего его вершины четные.
Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз Эйлеров путь приведет конец карандаша в вершину, столько и выведет, причем уже по другому ребру. Следовательно, степень каждой вершины графа должно состоять из двух одинаковых слагаемых: одно - результат подсчета входов в вершину, другое - выходов.
Верно и обратное утверждение.
Задачи на отыскание путей через лабиринты, близкие к задачам на Эйлеровы графы, находят и здесь свое применение.
Уже начиная с мифа о том, как Тезей, убив Минотавра, нашел путь по коридорам лабиринта в Кноссе, задача о поиске прохода через лабиринт стала популярной головоломкой. Во многих средневековых храмах на мозаичных полах изображены лабиринты. Возможно, метод нахождения пути был бы полезен для группы, заблудившейся в пещере. Однако. кроме этого, задачи о лабиринте представляют теперь интерес главным образом для развлечения детей, а также для психологов, когда они выпускают своих подопытных крыс в запутанные лабиринты.
Говоря коротко, лабиринт состоит из коридоров и их перекрестков. Таким образом, он может быть представлен графом, в котором ребра соответствуют коридорам, а вершины перекресткам. На рис.42 изображен план известного лабиринта в саду в Хемптон Корт, а на рис.43 - соответствующий граф.
В терминах графов задача о лабиринте может быть сформулирована следующим образом. Определить метод, позволяющий найти маршрут в графе, который начинается в заданной вершине V0 и наверняка приводит в другую заданную вершину V1 (выход). Очевидно, чтобы не было бесконечного блуждания по циклическим маршрутам, необходимо иметь возможность запоминать уже пройденные вершины и ребра; поэтому нужно предполагать, что заблудившийся располагает средствами помечать каким-то способом проходимые им ребра и вершины.
В 1857 году ирландский математик Гамильтон предложил игру, названную Путешествием по додекаэдру. Игра сводилась к обходу по ребрам всех вершин правильного додекаэдра, при условии, что ни в одну из вершин нельзя заходить более одного раза.
(Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников)
Гамильтоновым циклом (путем) в графе называется цикл (путь), проходящий через каждую вершину графа в точности по одному разу.
Гамильтоновым путем в графе называется путь, проходящий через каждую вершину графа в точности по одному разу.
Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.
Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все ребра, и притом по одному разу каждое, вторые - все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Для решения вопроса о существовании эйлерова цикла на графе достаточно выяснить, все ли его вершины четны. Критерий же существования гамильтонова цикла на произвольном графе еще не найден.
Решение этой проблемы имеет практическую ценность, так как к игре Гамильтона близки известные задачи.
Задача о шахматном коне. Можно ли, начиная с произвольного поля на шахматной доске, ходить конем в такой последовательности, чтобы пройти через все поля и вернуться в исходное?