1.4 Эйлеровы графы.

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

формулируется так: есть ли в мультиграфе G цикл, соединяющий все ребра мультиграфа? В 1736 году Эйлер доказал, что эта задача неразрешима, но при этом сформулировал важное условие, при котором связный граф содержит эйлеров цикл. Цикл называется эйлеровым, если он содержит все ребра графа, а связный граф с эйлеровым циклом называется эйлеровым.

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

Естественно, возникает вопрос об отыскании в любом графе эйлерова цикла, т.е о такой нумерации ребер G, чтобы номер указывал каким по счету это ребро входит в эйлеров цикл.

Один из алгоритмов нумерации называется алгоритмом Флёри:

Начиная, с произвольной вершины Vi присваивается произвольному ребру (Vi, Vi+1) номер 1, затем это ребро вычеркивается и переходит в вершину Vi+1.

Пусть Vi- это вершина, в которую пришли на предыдущем шаге, а R-это номер, присвоенный некоторому ребру на этом шаге. Выбирается любое ребро инцидентное вершине Vi, причем мост выбирается только в том случае, когда нет других вариантов. Ребро обозначается R+1 и вычеркивается.

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