Некоторые определения, относящиеся к графам
Мультиграф - граф в котором допускается более одного ребра между вершинами. Примером мультиграфа является граф, построенный Эйлером для решения задачи о кенигсбергских мостах - рис.1 и рис.2.
Рис.1 |
Рис.2 |
Графы, в которых не допускаются параллельные ребра, то есть кратные ребра
между вершинами, иногда называют простыми графами.
Псевдограф -
граф, в котором допускается
как наличие петель, так и существование более
одного ребра между двумя вершинами.
Цикл - путь ненулевой длины, соединяющий вершину саму с собой и не
содержащий повторяющихся ребер.
Простой цикл - цикл соединяющий вершину v саму с собой и не содержащий
повторяющихся вершин, кроме v.
Граф называется полным, если любые две его вершины соединены одним ребром.
Степенью вершины называется количество ребер, инцидентных этой вершине.
Цикл, который включает все ребра и вершины графа называется эйлеровым
циклом. (По определению цикла путь, составляющий эйлеров цикл, не может
проходить дважды по одному и тому же ребру, но может проходить несколько раз
через одну и ту же вершину).
Теорема о существовании эйлерова цикла.
Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда,
когда он связный и каждая его вершина имеет четную степень.
Доказательство.
Пусть граф имеет эйлеров цикл. Поскольку он связный все его вершины
принадлежат циклу. Для каждой из них цикл, проходящий через вершину, вносит
2 в ее степень. Поэтому степень любой вершины - четная.
Обратное утверждение доказывается индуктивно. Легко проверить, что при числе
вершин k = 2 и 3 только четные степени вершин обеспечивают наличие эйлерова
цикла.
Пусть граф с k вершинами, имеющими четную степень, имеет эйлеров цикл.
Добавим к нему еще одну вершину с четной степенью. Добавленная вершина должна быть связана общими ребрами с одной или несколькими вершинами
старого, чтобы новый граф остался
связным. При этом к любой старой вершине, связанной ребрами с новой
вершиной, должно подходить четное количество новых ребер, чтобы ее степень
осталась четной. Поэтому, дополнив эйлеров цикл для k-вершинного графа
заходами в новую вершину из каждой старой вершины, связанной с новой,
получим эйлеров цикл для (k+1)-вершинного графа.
Из доказанной теоремы следует невозможность обойти все мосты, изображенные на рис.1, пройдя по каждому из них только один раз.