Siklus Euler dalam komponen yang terhubung

9

Jika grafik memiliki siklus Euler, apakah komponen-komponen yang tidak terhubung memiliki siklus Euler juga?

graph-theory eulerian-paths
sumber
1
Jika ini adalah masalah pekerjaan rumah, mungkin yang terbaik bagi Anda untuk mencobanya sendiri? Grafik mungkin memiliki Siklus Euler, tetapi tampaknya tidak mengikuti secara alami bahwa subset (bahkan yang biconnected) harus. Sudahkah Anda mencoba menggunakan contoh penghitung?

Jawaban:

9

Iya. Jika Anda mulai dengan siklus Euler untuk grafik dan membatasi ke komponen yang terhubung, maka apa yang Anda miliki masih merupakan siklus pada komponen yang tidak terhubung (pada dasarnya, jika siklus euler meninggalkan simpul v dalam komponen yang terhubung, maka Anda tahu itu harus kembali ke komponen yang terhubung dua kali melalui v, jika tidak kita bisa memperbesar komponen yang terhubung dua kali - bertentangan dengan maksimalnya).


sumber