Есть очень простой алгоритм отыскания эйлерова цикла в неориентированном графе (если такой цикл существует) – алгоритм Флери [2], который состоит в следующем: начиная с некоторой вершины переходить в одну из смежных с ней, вычеркивая пройденное ребро, и так далее , пока не будут пройдены все ребра. Замечание: не проходить по ребру, если его удаление приводит к разбиению графа на две не связанные между собой части (не считая изолированных вершин).
Цикл Гамильтона – это простой цикл, содержащий все вершины графа. Общий критерий наличия гамильтонова цикла не известен, существуют лишь частные критерии, например критерий Дирака: граф имеет гамильтонов цикл, если сумма степеней двух любых его вершин не меньше числа вершин n [4]: (" хi, хj Î X) [d(xi) + d(хj)] ³ n.
Можно убедиться, что орграфы, изображенные на рис. 1.1 и 3.1 не имеют гамильтонова контура, а для графа на рис. 1.2. цикл (а1, а2, а3, а7, а6), иначе (х1, х2, х5, х3, х4, х1), является гамильтоновым.
Упражнения
Рис.3.2.
В графах, приведенных на рис.3.2:
3.1. Перечислить простые циклы, элементарные циклы, максимальные и минимальные циклы.
3.2. Указать циклы Гамильтона и Эйлера.
3.3. Сколько ребер содержит гамильтонов цикл в графе с 12 вершинами? С 15 вершинами?
3.4. Возможно ли существование в графе нескольких гамильтоновых циклов? Привести примеры для графов на рис.3.2.
4. ТИПЫ ГРАФОВ.
Граф G(Х, А) называется конечным, если множество вершин Х конечно.
Граф G(Х, А) называется нуль-графом, если множество ребер А = Æ, т.е. граф состоит лишь из изолированных вершин, и пустым графом, если Х = Æ, А = Æ.
Граф G(Х, А) называется полным, если каждая пара вершин в нем связана ребром. В полном ориентированном графе любые две различные вершины связаны парой противоположно направленных дуг.
Граф G(Х, А) называется мультиграфом, если существует хотя бы одна пара вершины, соединенных между собой m ребрами, m>1.
Граф называется связным, если для любой пары вершин существует маршрут.
Графы на рис. 1.1, 1.2, 1.3 – связные.
Граф может состоять из отдельных связных подмножеств вершин и ребер (дуг), которые называются компонентами связности. Например, на рис.4.1 граф G(Х,А) состоит из трех компонент связности, представ-ляющих собою непересекающиеся подмножества вершин Х1,Х2,Х3:
Х1 = {х1, х2, х3, х4};
Х2 = {х5, х6, х7};
Х = Х1 È Х2 È Х3.
Ранг R графа G определяется как разность числа вершин n графа и числа компонент связности р, т.е.
R(G) = n - p.
Для графа на рис. 4.1 R(G)=5.
Изоморфные графы. При геометрическом изображении графа существует большая свобода в размещении вершин графа в пространстве, т.е. один и тот же граф может иметь различное геометрическое представление.
Графы G и G¢ называются изоморфными, если они имеют одинаковое число вершин и если каждой паре вершин, соединенных ребром (дугой), в одном графе соответствует такая же пара вершин, соединенных ребром (дугой той же ориентации) в другом графе. Все изоморфные графы имеют одни и те же свойства, а их различные изображения помогают иногда выявить некоторые свойства, например, планарность графа.
На рис. 4.2, а, б, в изображены изоморфные графы G, G¢ и G¢¢. В графе G¢ на рис. 4.2 б выделен в виде самонепересекающейся цепи гамильтонов цикл {х1, х3, х2, x7, x5, х6, х4, х1); рис. 4.2 в показывает, что граф G¢¢ планарный (плоский) и, следовательно, графы G и G¢ тоже плоские.
|
Граф G (Х, А) называют плоским или планарным, если он может быть изображен на плоскости так, что все его ребра пересекаются только в вершинах Х графа.
При использовании графа в качестве модели принципиальной электрической схемы, решая вопрос о возможности реализации схемы с помощью печатного монтажа, важно знать, является ли граф плоским, и если да, то как получить его изображение на плоскости без пересечения ребер.
Критерий, позволяющий указать общие условия существования плоского графа весьма сложен для практического использования. Здесь мы рассмотрим частные случаи.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.