Cykle Eulera w komponentach połączonych podwójnie

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

graph-theory eulerian-paths

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:

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ą).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.