Графа обход

- маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами. Наиболее известными Г. о. являются эйлеровы и гамильтоновы цепи и циклы. Маршрут (замкнутый маршрут) наз. эйлеровой. Маршрут (замкнутый маршрут) наз. гамильтоновой цепью (гамильтововым циклом), если он содержит все вершины графа н через каждую проходит по одному разу. Известен ряд достаточных условий существования гамильтоновых циклов, напр.: граф не имеет петель и кратных ребер и для любых двух его несмежных вершин сумма степеней не меньше числа вершин этого графа; граф является плоским и 4-связным; граф не имеет петель н кратных ребер, а число пего вершин и число т его ребер удовлетворяют условиям [img: http://localhost:8080/file/010429-30.jpg] Граф наз. гамильтоновым (эйлеровы м), если он имеет гамильтонов (эйлеров) цикл. Граф наз. гамильтовово связным, если любые две его вершины соединены гамильтоновой цепью, и k- гамильтоновым, если любая простая цепь длины kвходит в нек-рый гамильтонов цикл. Известная задача о коммивояжере состоит в том, чтобы найти в графе, ребрам к-рого приписаны неотрицательные числа (длины ребер), гамильтонов цикл, имеющий наименьшую сумму длин ребер. Эта и другие задачи о Г. о. имеют различные технич. и экономия, приложения.