Эйлеровость, согласованная с ориентацией

? Поставим перед собой задачу описать ориентированные графы, которые рисуются одним росчерком так, чтобы направление движения карандаша было согласовано с ориентацией дуг орграфа. Такие ориентированные графы называются уникурсальными орграфами. Более строго: ориентированный граф называется уникурсальным, если все его дуги можно включить либо в простой контур (тогда это эйлеров контур), либо в простой путь (тогда это эйлеров путь).

Ясно, что необходимым, но конечно же не достаточным условием уникурсальности орграфа является уникурсальность его симметризации. Ранее было доказано, что неориентированный граф является уникурсальным графом, если и только если он связан и содержит не более двух нечетных вершин (см. пункт 2.1). Поэтому связность и существование не более двух нечетных вершин для ориентированного графа являются необходимыми условиями его уникурсальности. Для того чтобы сформулировать достаточные условия, дадим несколько новых определений.

Пусть А — некоторая вершина конечного орграфа G.

Число

равное разности положительной и отрицательной полустепеней вершины А, называется дефектом степени вершины А. Легко убедиться в справедливости следующих соотношений:

Вершина Л ориентированного графа G называется уравновешенной, если она имеет нулевой дефект степени Д<�т (Д) = 0, и, следовательно, <7 *(А) = <7 ~(А). Ясно, что уравновешенная вершина является четной. Орграф называется равновесным, если все его вершины уравновешены. Равновесный орграф не имеет нечетных вершин.

Лемма. Для любой неизолированной вершины конечного равновесного орграфа существует контур с началом в этой вершине.

Действительно, пусть А — неизолированная вершина конечного равновесного орграфа. Так как а ⁺(А) = (Т ~(/Г) 0, то существует некоторая дуга а/ с началом в вершине А. Пусть А; - конец дуги а/. Так как а *(Аj) = а «(Л,) * 0, то существует дуга а₂ с началом в вершине А/. Обозначим через А₂ конец дуги а₂ и будем продолжать этот процесс выделения последовательности различных дуг а, а₂, а₃,____ Заметим, что в соответствующей последовательности А, Л₁, А₂, А_},… вершины могут повторяться. Так как число дуг конечного орграфа конечно, то на каком-то этапе процесс закончится. В силу равновесности орграфа из каждой вершины можно выйти по дугам столько же раз, сколько в нее пришли, поэтому конечной точкой построенного маршрута может быть только вершина А. Следовательно, выделенный маршрут из различных дуг является контуром с началом в вершине А. Заметим, что этот контур может не включать в себя всех дуг орграфа, т. е. не обязан быть эйлеровым контуром.

Теорема 26. Орграф является эйлеровым контуром тогда и только тогда, когда он связный и равновесный. При этом, начало и конец уникурсального контура могут находиться в любой вершине орграфа.

Доказательство. Необходимость теоремы очевидна. Доказательство достаточности проведем методом математической индукции по количеству дуг орграфа.

• 1. База индукции. Связный равновесный орграф с одной дугой является петлей и, следовательно, уникурсален.
• 2. Для доказательства индуктивного перехода предположим, что связный равновесный орграф, содержащий п<�к ребер, является эйлеровым циклом.

Рассмотрим связный равновесный орграф, содержащий п=к+1 ребер. Так как орграф связен, он не имеет изолированных вершин. Пусть А — некоторая вершина. Рассмотрим контур с началом в вершине А (он существует по лемме 1). Если этот контур включает в себя все дуги орграфа, то он — искомый эйлеров контур. В противном случае удалим из исходного орграфа дуги выделенного контура. В результате получим ориентированный суграф, который имеет несколько компонент связности (возможно, всего одну) G, (/=/, 2, …, г). При этом будут выполняться следующие свойства:

• • каждая часть G, является связным равновесным орграфом;
• • каждая часть G, хотя бы одной вершиной примыкает к вершинам удаленного контура;
• • каждая часть G, имеет не более к дуг.

По предположению.

индукции каждая из частей G, является эйлеровым контуром, причем, начало и конец пути могут находиться в любой из вершин (в частности ими могут быть точки примыкания к вершинам удаленного контура).

Поэтому, алгоритм построения уникурсального контура можно сформулировать так: двигаясь из вершины А по выделенному контуру, попутно обходить выделенные части G, (см. схему на рис. 185).

Итак, оба шага математической индукции доказаны. Следовательно, теорема 26 верна для орграфа с любым конечным количеством дуг.

Перейдем теперь к изучению уникурсальных орграфов, содержащих эйлеров путь. Если такой путь начинается в вершине А и заканчивается в вершине В, то Дет (А) = -1, Дет (В) = 1, а остальные вершины орграфа являются уравновешенными. Докажем обратное утверждение: если связный орграф имеет две нечетные вершины А и В, Дсг (Л) = -1, Дет (Д) = 1, а остальные вершины орграфа являются уравновешенными, то этот орграф является эйлеровым путем с началом в А и концом в В. Для этого добавим дугу а, ведущую из В в А. В результате получим связный равновесный орграф. По теореме 26 он содержит эйлеров контур с началом в вершине А. При этом порядок движения по дугам можно выбрать таким образом, чтобы дуга а оказалась последней дугой в эйлеровом контуре. Если затем удалить дугу а, то эйлеров контур превратится в эйлеров путь, ведущий из А в В. Итак, можно сформулировать следующий результат:

Теорема 27. Орграф является эйлеровым путем тогда и только тогда, когда он связный, имеет две нечетные вершины, А и В, Д<7(Д) = -1, Дсг (Д) = 1, а остальные вершины? орграфа являются уравновешенными. При этом начало пути совпадает с вершиной А, а конец — с вершиной В.

Рассмотрим теперь произвольный конечный связный орграф и подсчитаем количество росчерков, необходимых для его изображения. При этом потребуем, чтобы движение карандаша было согласовано с ориентацией графа.

Будем называть степенью неравновесности орграфа G число 8(G), равное сумме абсолютных величин дефектов степеней всех вершин: 8(G) = ^|Дст (Д)|.

АеГ

В силу равенства^Дсг (Д) = 0 сумма положительных.

Ae.V

дефектов всех вершин равна сумме всех отрицательных дефектов и равна половине степени неравновесности орграфа. Ясно, что степень неравновесности всегда четна. Так, для эйлерова контура (т.е. для равновесного связного графа) 8(G)=0, а для эйлерова пути 8(G)-2.

Теорема 28. Для согласованного с ориентацией изображе-ния конечного связного неравновесного орграфа необходимое количество росчерков равно половине степени неравновесности этого орграфа.

Доказател ьство. Пусть степень неравновесности связного орграфа G равна 2л: 8(G)=2n. Добавим к графу G п дуг таким образом, чтобы каждая добавляемая дуга выходила из вершины с положительным дефектом степени и приходила в вершину с отрицательным дефектом степени. В результате получим равновесный связный орграф, являющийся эйлеровым контуром. Этот орграф рисуется одним росчерком (подобно окружности). Если теперь вернуться к орграфу G, удалив п дуг, то нам придется «разорвать» уникурсальный контур ровно и раз и он разобьется на л эйлеровых путей (если окружность «разрезать» л раз, то она «распадется» на л дуг). Итак, для согласованного с ориентацией изображения орграфа G необходимо ровно л росчерков.