| [Pelawat (223.104.*.*)]jawapan [Cina ] | Masa :2024-11-18 | Terangkan maksud litar Euler
Penentuan laluan Eulerian dan litar Euler adalah mudah
Graf tidak terarah
Syarat yang mencukupi dan perlu untuk kewujudan laluan Euler ialah:
untuk graf ketersambungan dan
Terdapat hanya dua nod singariti (bucu dengan darjah ganjil) atau tiada nod singariti
Akibat 1:
Semasa
ialah graf bersambung dengan hanya dua nod tunggal,
Laluan Euler mestilah titik akhir dengan kedua-dua nod ini
Semasa
ialah graf bersambung tanpa nod tunggal,
Mesti ada litar Euler
Syarat yang mencukupi dan perlu untuk rajah Euler (kehadiran gelung Euler) ialah
ialah graf bersambung tanpa nod tunggal
graf terarah
Syarat yang mencukupi dan perlu untuk kewujudan laluan Euler ialah:
ialah graf terarah,
dan semua bucu adalah sama masuk dan keluar; Atau kecuali dua bucu, bucu lain mempunyai darjah keluar dan masuk yang sama, dan dalam dua bucu ini, satu bucu hanya mempunyai darjah keluar dan masuk
, perbezaan antara darjah keluar dan dalam bucu yang lain ialah
Akibat 2:
Apabila kedua-dua bucu dengan perbezaan antara darjah keluar dan masuk adalah sama kecuali untuk dua bucu dengan perbezaan antara keluar-keluar dan masuk, laluan Eulerian berarah mesti bermula dengan bucu dengan perbezaan antara darjah keluar-keluar dan masuk, dan ambil bucu dengan perbezaan antara darjah keluar-keluar dan masuk sebagai titik akhir
Apabila semua bucu sama masuk dan keluar, terdapat gelung Euler terarah
Syarat yang mencukupi dan perlu untuk graf terarah menjadi graf Euler terarah ialah graf asas ialah graf bersambung, dan semua bucu mempunyai darjah output yang sama dan dalam |
|
