Цепь – последовательность ребер, в которой ребра не повторяются, цикл – замкнутая цепь. Цикл называется простым, если в нем нет повторяющихся вершин. Цикл является элементарным, если он не содержит внутри себя других циклов. Цикл назывется максимальным (минимальным), если содержит максимальное (минимальное) число ребер.
Примеры циклов для графа, приведенного на рис. 1.2.:
(а1, а8, а7, а6), иначе (х1, х5, х3, х4, х1) – простой цикл, содержащийся в нем цикл (а5, а7, а6), иначе (х5, х3, х4, х5) - элементарный; цикл (а1, а2, а3, а7, а6) – максимальный, цикл (а2, а3, а8) – минимальный.
Маршрут – понятие, справедливое для обоих типов графов. Это последовательность дуг (ребер) такая, что каждые две соседние дуги (два соседних ребра) имеют общую вершину, причем дуги (ребра) и вершины могут повторяться. Пример маршрутов для графа рис. 1..2.: (а2, а4, а7, а3, а4, а6), (а8, а1, а6, а7, а4), для графа рис. 3.1.: (а1, а4, а10, а8, а6), (а4, а10, а8, а7, а9).
В практических задачах часто встречаются особые виды циклов: цикл Эйлера и цикл Гамильтона.
Цикл называется циклом Эйлера, если он содержит все ребра графа. Необходимым и достаточным условием существования цикла Эйлера является для неориентированного графа четность степеней всех его вершин, для ориентированного – равенство для каждой вершины полустепеней исхода и захода. Графы, изображенные на рис. 1.1., 1.2., 3.1. Эйлерова цикла не содержат, т.к. не отвечают этим условиям.
Есть очень простой алгоритм отыскания Эйлерова цикла в неориентированном графе (если такой цикл существует) – алгоритм Флери (2(, который состоит в следующем. Начиная с некоторой вершины, переходить в одну из смежных с ней, вычеркивая пройденное ребро и так далее , пока не будут пройдены все ребра. Замечание: не проходить по ребру, если его удаление приводит к разбиению графа на две не связанные между собой части (не считая изолированных вершин).
Цикл Гамильтона – это простой цикл, содержащий все вершины графа. Общий критерий наличия гамильтонова цикла не известен, существуют лишь частные критерии, например, критерий Дирака: граф имеет гамильтонов цикл, если сумма степеней двух любых его вершин не меньше числа вершин n (((( (( х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:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.