Как проверить, имеет ли неориентированный граф цикл нечетной длины

Question

Я пытаюсь найти алгоритм времени O (| V | + | E |), чтобы проверить, имеет ли подключенный неориентированный граф цикл нечетной длины или нет.Сначала найдите на графике и попытайтесь обозначить вершины черными и белыми, чтобы не было смежных двух вершин, помеченных одинаковым цветом.

Есть ли какой-нибудь известный алгоритм для решения этой проблемы за линейное время?

Answer 1

Ваш подход правильный.Вы не можете сделать это лучше.

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

Answer 2

При инициализации также необходимо установить Num [s] = 0.

Answer 3

Это также можно сделать с помощью DFS и нумерации вершин.

1. Часы = 1
2. Начать с вершины 's', отметить ее как "посещенную" и вызвать "Исследовать"(s)

Исследуйте (u)

1. , если вы уже "посетили", то если(clock-Num [u]) нечетный, то есть нечетный цикл,

   еще пометьте 'u' как "посещенный"

2. Num [u] =clock ++;

3. для всех соседних узлов v из u

     i) Explore(v)
     ii) clock=Num[u]