давно
Мастер-Эксперт
17387
18346
21.05.2008, 00:33
общий
это ответ
Здравствуйте, Sashka!
Между эйлеровыми и гамильтоновыми линиями имеется определенная аналогия. Эйлерова линия проходит один раз по каждому ребру, а гамильтонова – через каждую вершину. Но существует и большая разница.
Эилер доказал, что если степени всех вершин связного графа четны, то на таком графе можно найти цикл, содержащий все ребра этого графа, причем в точности по одному разу. Для гамильтонова цикла общего критерия, насколько мне известно, не существует. Поэтому для того, чтобы доказать, что на конкретном графе гамильтонов цикл существует, надо его найти…
Существуют лишь некоторые критерии для частных случаев. Например, если для любой пары вершин графа сумма локальных степеней больше или равна числу вершин графа, то в таком графе существует гамильтонов цикл… Полагаю, что специалисты по дискретной математике дадут более исчерпывающие справки.
С уважением.
Об авторе:
Facta loquuntur.