Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы

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

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

Теорема 1. Если в связном графе все вершины четны, то этот граф содержит эйлеров цикл.

Верно и обратное утверждение: если граф содержит эйлеров цикл, то все его вершины четны.

Теорема 2. Если в связном графе две вершины нечетны, а все остальные – четны, то этот граф содержит эйлерову разомкнутую цепь.

Всякую линию, которую можно провести, проходя по заданным участкам точно по одному разу, называют уникурсальной

Теорема 3. Если в связном графе G содержится 2k нечетных вершин, то в нем имеется k разомкнутых эйлеровых цепей, в совокупности содержащих все ребра графа G точно по одному разу.

Теорема 4. В любом связном графе можно построить замкнутый маршрут, проходящий через каждое ребро точно два раза.

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

цикл, содержащий по одному разу каждую вершину графа, стали называть гамильтоновой линией (гамильтоновым циклом), а граф, содержащий гамильтонову линию, – гамильтоновым графом.

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

Цепь (цикл) в G называется гамильтоновой (гамильтоновыми), если она (он) проходит по одному разу через каждую вершину псевдографа G.

Граф является гамильтоновым, если он содержит гамильтонов цикл.

Теорема. Если в простом графе с n (і 3) вершинами локальная степень каждой вершины не менее , то граф является гамильтоновым.