Степенью или валентностью вершины a неорграфа G называется число ребер, инцидентных вершине a (петли считаются дважды). Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.
Лемма о рукопожатиях: Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер.
Критерий «эйлировости» графа: Связный неориентированный мультиграф тогда и только тогда является эйлеровым, когда степень каждой из его вершин – четное число.
Алгоритм построения эйлерова цикла:
1) Выбрать произвольно некоторую вершину a.
2) Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).
3) Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший предыдущего вычеркнутого ребра.
4) Находясь в вершине x, не выбирать ребро, соединяющее x с a, если есть возможность иного выбора.
5) Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при вычеркивании которого граф распадается на две компоненты связности).
|
|
6) После того как в графе будут занумерованы все ребра, образуется эйлеров цикл.
Теорема: Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непересекающихся цепей равно k/2.
Доказательство: Набор реберно непересекающихся цепей покрывает граф G, если каждое его ребро входит в одну из этих цепей.
Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопожатиях число k четно. Рассмотрим граф G’, полученной добавлением к G новой вершины a и ребер, соединяющих a со всеми вершинами нечетной степени графа G. Граф G’ будет содержать эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k/2 цепей, покрывающих G. С другой стороны, граф, являющийся объединением r реберно непересекающихся цепей имеет не более 2r верши нечетной степени. Поэтому граф G нельзя покрыть цепями, число которых меньше k/2.