ГРАФА ОБХОД

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

Маршрут (замкнутый маршрут) наз. гамильтоновой цепью (гамильтововым циклом), если он содержит все вершины графа н через каждую проходит по одному разу. Известен ряд достаточных условий существования гамильтоновых циклов, напр.: граф не имеет петель и кратных ребер и для любых двух его несмежных вершин сумма степеней не меньше числа вершин этого графа; граф является плоским и 4-связным; граф не имеет петель н кратных ребер, а число пего вершин и число т его ребер удовлетворяют условиям

Граф наз. гамильтоновым (эйлеровы м), если он имеет гамильтонов (эйлеров) цикл. Граф наз. гамильтовово связным, если любые две его вершины соединены гамильтоновой цепью, и k- гамильтоновым, если любая простая цепь длины kвходит в нек-рый гамильтонов цикл. Известная задача о коммивояжере состоит в том, чтобы найти в графе, ребрам к-рого приписаны неотрицательные числа (длины ребер), гамильтонов цикл, имеющий наименьшую сумму длин ребер. Эта и другие задачи о Г. о. имеют различные технич. и экономия, приложения.

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