Практикум по дисциплине «Дискретная математика»

Исходя из утверждений 1 и 2, чтобы найти Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая Эйлерова цепь.

1. 
   Выделим из G цикл ₁. (так как степени вершин четны, то висячие вершины отсутствуют). Положим l=1, G=G.
   
2. 
   Удаляем из G ребра, принадлежащие выделенному циклу ₁. Полученный псевдограф снова обозначаем как G. Если в G отсутствуют ребра, то переходим к шагу 4. Если ребра есть, то выделяем из G цикл _l+1 и переходим к шагу 3.
   
3. 
   Присваиваем l:=l+1 и переходим к шагу 2.
   
4. 
   По построению выделенные циклы содержат все ребра по одному разу. Если l:=1, то искомый Эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл, который является искомым.
   

Найдем Эйлерову цепь в неориентированном графе G, изображенном на рис. 10.

Прежде, чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа G − согласно утверждению 2, для существования Эйлеровой цепи, необходимо и достаточно, чтобы в графе G ровно 2 вершины нечетной степени.

Рис. 10.
В рассматриваемом графе нечетные степени имеют вершины v₃ и v₁ (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 11, получаем граф G:

Рис. 11.
Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем циклы _i так, чтобы хотя бы один из них начинался или кончался на вершинах v₃ или v₁.

Пусть цикл ₁ составят ребра, проходящие через следующие вершины: v₃ v₄ v₇ v₆ v₁ v₂ v₃. Согласно алгоритму, удаляем из G все ребра, задействованные в цикле ₁. Теперь граф G’ будет таким, как показано на рис. 12.

Составляем следующий цикл ₂: v₄ v₅ v₆ v₂ v₅ v₇ v₄. Граф G после удаления ребер, составляющих цикл ₂, изображен на рис. 13.

Рис.12	Рис. 13

Очевидно, что последний цикл ₃ будет состоять из v₃ v₅ v₁|v₃, где последнее ребро, соединяющее вершины v₁ и v₃ – фиктивно. После удаления ребер, составляющих цикл ₃, в графе G не останется ни одного ребра.

1. 
   Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G₂ графа G. Положим i:=2.
   
2. 
   Если i=n(G), то задача решена и G_i – искомое минимальное остовное дерево графа G. Иначе переходим к шагу 3).
   
3. 
   Строим граф G_i+1. Для этого добавим к графу G_i новое ребро минимальной длины из оставшихся, которое инцидентно какой-либо вершине графа G_i и одновременно вершине, не содержащейся в G_i. Вместе с этим ребром включаем в G_i+1 и эту инцидентную ему вершину. Присваиваем i:=i+1 и переходим к шагу 2).
   

Найдем минимальное остовное дерево в неориентированном нагруженном графе, изображенном на рис.14.

Рис.14.
Обозначим ребро, соединяющее вершины v_i и v_j через x_ij.

Поскольку i=8=n(G), работа алгоритма заканчивается.

Таким образом, искомое минимальное остовное дерево графа G − граф G₈, изображенный на рис. 15, длина которого равна 22.

Рис.15.