Консультация № 189265
25.04.2016, 17:21
0.00 руб.
0 1 1
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Полный граф имеет 99 вершин. Существует ли в данном графе эйлеров цикл?
Заранее спасибо!

Обсуждение

давно
Старший Модератор
312929
1973
26.04.2016, 06:59
общий
это ответ
Здравствуйте, plaob!

Эйлеров цикл - это замкнутый путь, проходящий через каждое ребро графа ровно по одному разу. Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный, и в нём отсутствуют вершины нечётной степени.
Полный граф - это простой граф (не содержащий кратных рёбер и петель), в котором каждая пара различных вершин смежна, то есть каждая вершина соединена рёбрами со всеми остальными вершинами графа и, следовательно, все вершины имеют степень n-1 (n - число вершин).
Связный граф - это граф, содержащий ровно одну компоненту связности, то есть граф, между любой парой вершин которого существует как минимум один путь.
Очевидно, что любой полный граф является связным, так как любые две вершины будут связаны путём, состоящим из одного ребра (соединяющего эти вершины). Поскольку степень всех вершин в полном графе одинакова и на единицу меньше числа вершин, все полные графы с нечётным числом вершин будут связными и не иметь вершин нечётной степени, то есть удовлетворять условиям теоремы Эйлера.
Итак, полный граф содержит эйлеров цикл тогда и только тогда, когда число вершин в нём нечётно. В данном случае граф имеет 99 вершин, поэтому эйлеров цикл в нём существует.
5
Форма ответа