2

Подскажите, как наиболее оптимально определить данные параметры для неориентированного взвешенного графа( задается матрицей или списком смежности ):

  • определить, существуют ли в графе циклы (из одной (любой) вершины вернуться в нее же, проходя по дугам не более одного раза)
  • определить, существуют ли в графе Эйлеровы циклы (возможность вернуться в вершину, пройдя по всем вершинам и по всем дугам только 1 раз)
  • определить, существуют ли в графе Эйлеровы пути (возможность пройти по всем вершинам графа произвольное количество раз при обязательном условии прохождения по всем дугам точно 1 раз)
3
  • 3
    Вы пытались поискать? Эта информация есть в любой методичке по теории графов. PS. У "оптимальности" нет превосходной степени.
    – Vlad
    Commented 27 мая 2015 в 11:10
  • да, пытался. у Вас случайно нету ссылки на подобную методичку?
    – Alex May
    Commented 27 мая 2015 в 11:34
  • Вот, например.
    – Vlad
    Commented 27 мая 2015 в 11:36

1 ответ 1

4

Если граф неориентированный, то определить наличие циклов можно простым обходом (например, обходом в глубину). Если при обходе вы встречаете вершину, в которой уже были, значит, вы нашли цикл.

Фактически, вам нужно доказать, что граф является деревом. Если вам известно, что граф связный, то достаточно просто посчитать число рёбер: число рёбер в дереве всегда на один меньше, чем число вершин.

Определить, существует ли эйлеров цикл в неориентированном графе довольно просто -- достаточно с помощью любого обхода графа проверить, что он связный и проверить, что нет вершин с нечётной степенью.

Для определения наличия эйлерова пути достаточно проверить связность графа, как в случае с циклом, и удостовериться, что вершин с нечётными степенями нет (тогда путь совпадает с циклом), или есть ровно две.

Про определение связности графа уже есть ответ в вопросе Является ли неориентированный взвешенный граф связным.

1
  • Если граф связный, то «число рёбер в дереве всегда на один меньше, чем число вершин» является необходимым и достаточным условием того, что граф — дерево.
    – VladD
    Commented 27 мая 2015 в 15:01

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.