*Apakah graph berikut, graph Euler? Semi Euler? Mengapa?GHR

Margono Slamet

*b) d(V1) = 2, d(V2) = 2, d(V3) = 4, d(V4) = 6, d(V5) = 2,d(V6) = 4, d(V7) = 2, d(V8) = 2 Graph H ini termasuk graph Euler karena semua titik pada H berderajat genap.

Margono Slamet

*2. a) Apakah graph komplit Kn graph Euler? Jelaskan!Penyelesaian:Bukan graph Euler.Misal, ambil graph komplit K4Graph komplit K4 ini bukan graph Euler karena derajat setiap titik pada K4 ini ganjil.

Margono Slamet

Syaratnya adalah m dan n harus genap*Syaratnya adalah m harus ganjil dan n = 2

Margono Slamet

Ya, karena sebuah graph Euler harus memuat sebuah sirkuit Euler dan sebuah sirkuit Euler harus memuat semua sisi pada graph G tersebut sehingga graph G harus terhubung.

*

Margono Slamet

Agar setiap jembatan dapat dilewati tepat satu kali, maka graph jembatan tersebut harus membentuk graph Euler. *Penyelesaian:

Margono Slamet

*

Margono Slamet

Penyelesaian:STEP 1: Pilih titik V1 : J0 = V1STEP 2: Pilih sisi e1 = V1V3J1 = (V1e1V3) Pilih sisi e2 = V3V2J2 = (V1e1V3e2V2) Pilih sisi e3 = V2V4J3 = (V1e1V3e2V2e3V4) Pilih sisi e4 = V4V3J4 = (V1e1V3e2V2e3V4e4V3) Pilih sisi e5 = V3V5J5 = (V1e1V3e2V2e3V4e4V3e5V5) Pilih sisi e6 = V5V6J6 = (V1e1V3e2V2e3V4e4V3e5V3e6V6) Pilih sisi e7 = V6V4J7 = (V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4) Pilih sisi e8 = V4V8J8 = (V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4e8V8) Pilih sisi e9 = V8V6J9 = (V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4e8V8e9V6) Pilih sisi e10 = V6V7J10 = (V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4e8V8e9V6e10V7) Pilih sisi e11 = V7V4J11 = (V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4e8V8e9V6e10V7e11V4) Pilih sisi e12 = V4V1J12 = (V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4e8V8e9V6e10V7e11V4e12V1)STEP 3: STOPJ12 =(V1e1V3e2V2e3V4e4V3e5V3e6V6e7V4e8V8e9V6e10V7e11V4e12V1) Jejak Tutup

*

Margono Slamet

Jawaban : STEP 1: Pilih V1 Jejak J0 = V1STEP 2: Pilih sisi e1 = V1V2J1 = (V1e1V2)Pilih sisi e2 = V2V3J2 = (V1e1V2e2V3)Pilih sisi e3 = V3V1J3 = (V1e1V2e2V3e3V1)Pilih sisi e4 = V1V3J4 = (V1e1V2e2V3e3V1e4V3)Pilih sisi e5 = V3V2J5 = (V1e1V2e2V3e3V1e4V3e5V2)Pilih sisi e6 = V2V5J6 = (V1e1V2e2V3e3V1e4V3e5V2e6V5)Pilih sisi e7 = V5V3J7 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3)Pilih sisi e8 = V3V6J8 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6)Pilih sisi e9 = V6V5J9 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5)Pilih sisi e10 = V5V4J10 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4)Pilih sisi e11 = V4V7J11 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7)Pilih sisi e12 = V7V1J12 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1)Pilih sisi e13 = V1V8J13 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1e13V8)Pilih sisi e14 = V8V5J14 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1e13V8e14V5)Pilih sisi e15 = V5V7J15 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1e13V8e14V5e15V7)Pilih sisi e16 = V7V8J16 =(V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1e13V8e14V5e15V7e16V8)Pilih sisi e17 = V8V1J17 =(V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1e13V8e14V5e15V7e16V8e17V1)STEP 3 : STOPJ17 = (V1e1V2e2V3e3V1e4V3e5V2e6V5e7V3e8V6e9V5e10V4e11V7e12V1e13V8e14V5e15V7e16V8e17V1)s

*

Margono Slamet

*Jumlah titik pada grap G merepresentasikan jumlah ruangan pada denah rumah sementara jumlah sisi pada graph G merepresentasikan jumlah pintu pada denah rumah.

Margono Slamet

Pak pos akan menelusuri semua jalan yang ada mulai dari kantor pos dan akhirnya kembali lagi ke kantor pos sedemikian sehingga setiap jalan dilewati tepat satu kali. Jelaskan kenapa hal tersebut tidak mungkin ia lakukan? Kalau pak pos tetap ingin menelusuri semua jalan yang ada untuk mendistribusikan surat-surat tentu ada jalan-jalan tertentu yang harus dilewati lebih satu kali. Tentukan jalan-jalan mana yang harus ia lewati lebih dari satu kali agar total jarak yang ditempuh minimum. Tulislah strategi yang harus dia lakukan.*

Margono Slamet

a) Pak Pos akan berangkat dari V11 dan kembali lagi ke V11 ini mengakibatkan ada ruas jalan yang harus dilalui satu kali. Hal ini terjadi karena rute (Graph) di atas adalah graph semi-euler.

*b) Lintasan Terpendek

Margono Slamet

*V1V7V5V4V3V2V6V8V10V9V12V11V13V16V15V14544446541215321555164424545

Margono Slamet

*

Margono Slamet

SELESAI

Margono Slamet