Selasa, 27 Juli 2010

Lintasan dan Sirkuit Euler

Lintasan dan Sirkuit Euler
  • Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali
  • Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali
  • Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler

Contoh
a. Apakah Ada Lintasan Euler ?
b. Apakah ada sirkuit Euler ?

Jawab
a. ADA lintasan euler dengan lintasan :
a,b,c,d,e,f,g,b,d,f,a,g

b. Tidak ADA sirkuit Euler.








a. Apakah ada lintasan Euler ?
b. Apakah ada Sirkuit Euler ?

Jawab
a. ADA lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
b. Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a

Teorema Untuk Lintasan dan sirkuit euler

  • Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali
  • Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap
  • Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar

3 komentar:

gitarringsek mengatakan...

thanks masbro ! sangat amat membantu sekali~

DWIRA mengatakan...

terima kasih:)

kiki holmes mengatakan...

sangat membantu .

Poskan Komentar