Эйлеровым путем в графе называется цепь, содержащая все ребра
графа.
Эйлеровым циклом называется замкнутый эйлеров путь.
Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Граф является эйлеровым, если его можно "нарисовать", не отрывая карандаша от бумаги, проходя по каждому ребру по одному разу, закончив путь в начальной точке.
Теорема 1. Связный граф G является эйлеровым графом тогда и только тогда, когда степень каждой его вершины четна.
Теорема2. В связном графе существует эйлеров путь тогда и только тогда,когда все вершины графа четные или в точности две вершины нечетные.
20. Гамильтоновы графы.
Простой цикл, содержащий все вершины графа, называется гамильтоновым циклом. Граф называется гамильтоновым графом, если он имеет гамильтонов цикл.
Из определения видно, что необходимым условием гамильтоновости графа является его связность. До сих пор не найдено хорошего необходимого и достаточного условия гамильтоновости графа, Известен ряд достаточных условий гамильтоновости графа. Одно из них выглядит так:
Если G -- связный граф с n вершинами и для каждой вершины v
deg(v) > =(1/2) *п, то этот граф гамильтонов.
Приведенное условие не является необходимым (достаточно рассмотреть пятиугольник).
