Semua graf Hamiltonian disambungkan dwi, tetapi graf dwisambungan tidak semestinya Hamiltonian (lihat, sebagai contoh, graf Petersen). Graf Eulerian G (graf bersambung di mana setiap bucu mempunyai darjah genap) semestinya mempunyai lawatan Euler, berjalan kaki tertutup melalui setiap tepi G tepat sekali.
Bolehkah graf menjadi Hamiltonian tetapi bukan Eulerian?
Graf bersambung G ialah Hamiltonian jika terdapat kitaran yang merangkumi setiap bucu G; kitaran sedemikian dipanggil kitaran Hamiltonian. … Graf ini ialah KEDUA-DUA Eulerian dan Hamiltonian. Graf ini ialah Eulerian, tetapi BUKAN Hamiltonian. Graf ini ialah Hamiltionian, tetapi BUKAN Eulerian.
Adakah setiap graf Hamiltonian ialah Eulerian?
Tidak. Laluan Hamiltonian melawati setiap bucu tepat sekali tetapi mungkin berulang tepi. Litar Eulerian melintasi setiap tepi dalam graf tepat sekali tetapi mungkin mengulangi bucu.
Apakah Eulerian bukan Hamiltonian?
Graf bipartit K2 yang lengkap, 4 mempunyai litar Eulerian, tetapi bukan Hamiltonian (malah, ia tidak pun mengandungi laluan Hamiltonian). Mana-mana laluan Hamiltonian akan bertukar warna (dan tidak ada bucu biru yang mencukupi).
Adakah semua graf lengkap Eulerian?
Graf ialah Eulerian jika dan hanya jika darjah setiap bucu adalah genap. Oleh itu, Kn ialah Eulerian jika n ialah ganjil. (ii) Satu-satunya graf lengkap separuh Eulerian ialah K2. … Graf disambungkan, dan ada betul-betuldua bucu darjah ganjil.
