Эйлеровы циклы в двусвязных компонентах

9

Если у графа есть цикл Эйлера, то есть ли у двусвязных компонент также циклы Эйлера?

graph-theory eulerian-paths
источник
1
Если это домашняя проблема, возможно, вам лучше попробовать ее самостоятельно? Граф может иметь цикл Эйлера, но он, кажется, не следует естественным образом, что подмножество (даже двусвязное) должно. Вы пытались придумать контрпример?

Ответы:

9

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


источник