Таблицы Брадиса

Во втором 2,0, 1,1, 1,1,

Во втором 2,0, 1,1, 1,1,

Элементы математики в задачах - Г. А. Мерзон

Определение 4. Количество дуг, входящих в вершину (ориентиро­ванного графа), называется входной полустепенью (или полустепе- нью захода) этой вершины. Количество выходящих дуг называется выходной полустепенью (или полустепенью исхода).

Задача 17. Найдите входные и выходные полустепени каждой вер­шины для всех графов из задачи 10.

Решение. Приведем лишь ответы. Степень вершины будем записы­вать в виде (а, Ь), где а — выходная полустепень, Ь — входная. В пер­вом графе — у всех вершин (1,1). Во втором — (2,0), (1,1), (1,1), (0,2). В третьем — (2,1), (1,2), (1,1), (1,1). В четвертом— (1,1), (1,1), (1,1), (1,1), (0, 0). В пятом— (1,1), (1,1), (2,1), (1, 2). В ше­стом— (1,1), (1,1), (2, 2), (2, 2).

Задача 18. Что можно сказать о сумме всех входных полустепеней и сумме всех выходных полустепеней одного и того же ориентирован­ного графа?

Решение. Эти суммы равны, так как каждой входящей в какую-то вершину дуге соответствует одна и только одна выходящая (из какой- то вершины) дуга.

Задача 19. Сформулируйте и докажите критерий эйлеровости ори­ентированного графа.

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

Критерий эйлеровости ориентированного графа следующий: граф эйлеров, если и только если он связен и в каждую вершину входит столько же стрелок, сколько выходит, т. е. входная полустепень каж­дой вершины равна выходной полустепени.

Необходимость этих условий очевидна. Теперь докажем существо­вание эйлерова цикла при указанных условиях. Доказывать будем индукцией по числу вершин. База очевидна, докажем шаг.