Cykle Eulera w komponentach połączonych podwójnie

9

Jeśli wykres ma cykl Eulera, to czy połączone elementy mają również cykle Eulera?

graph-theory eulerian-paths
źródło
1
Jeśli jest to problem związany z pracą domową, być może najlepiej spróbować go samodzielnie? Wykres może mieć Cykl Eulera, ale wydaje się, że nie podąża naturalnie za podzbiorem (nawet połączonym podwójnie). Czy próbowałeś wymyślić przykład z licznikiem?

Odpowiedzi:

9

Tak. Jeśli zaczniesz od cyklu Eulera dla wykresu i ograniczysz się do komponentu połączonego dwuskładnikowo, wówczas nadal masz cykl na komponencie podwójnie połączonym (w zasadzie, jeśli cykl eulera pozostawia wierzchołek v w komponencie podwójnie połączonym, to wiesz, że musi on zwrócić do składnika połączonego przez v, w przeciwnym razie moglibyśmy powiększyć nasz składnik połączony - co jest sprzeczne z jego maksymalnością).


źródło