ГРАФА ОБХОД

ГРАФА ОБХОД - маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами. Наиболее известными Г. о. являются эйлеровы и гамильтоновы цепи и циклы. Маршрут (замкнутый маршрут) наз. эйлеровой цепью (эйлеровым циклом), если он содержит все ребра графа и проходит через каждое ребро по одному разу. Имеется эффективный критерий существования эйлеровых циклов (теорема Эйлера): связный граф имеет эйлеров цикл тогда и только тогда, когда каждая его вершина имеет четную степень.

Маршрут (замкнутый маршрут) наз. гамильтоновой цепью (гамильтоновым циклом), если он содержит все вершины графа и через каждую проходит по одному разу. Известен ряд достаточных условий существования гамильтоновых циклов, напр.: граф не имеет петель и кратных ребер и для любых двух его несмежных вершин сумма степеней не меньше числа вершин этого графа; граф является плоским и 4-связным; граф не имеет петель и кратных ребер, а число n его вершин и число m его ребер удовлетворяют условиям n ≥ 3 и m ≥ 1/2(n² - 3n + 6). Граф наз. гамильтоновым (эйлеровым), если он имеет гамильтонов (эйлеров) цикл. Граф наз. гамильтоново связным, если любые две его вершины соединены гамильтоновой цепью, и k-гамильтоновым, если любая простая цепь длины k входит в нек-рый гамильтонов цикл. Известная задача о коммивояжере состоит в том, чтобы найти в графе, ребрам к-рого приписаны неотрицательные числа (длины ребер), гамильтонов цикл, имеющий наименьшую сумму длин ребер. Эта и другие задачи о Г. о. имеют различные технич. и экономич. приложения.

Лит.: [1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] 3ыков А. А., Теория конечных графов, [в.1], Новосиб., 1969.

В. П. Козырев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.