Lintasan dan Sirkuit Euler

Pengertian Lintasan dan Sirkuit Euler

euler

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graph tepat satu kali. Sedangkan Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali.


Jika suatu graph memiliki sirkuit, maka otomatis memiliki lintasan juga. Sebaliknya, jika tidak memiliki sirkuit maka tidak memiliki lintasan. Namun, apabila suatu graph memiliki lintasan, belum tentu ia memiliki sirkuit.

Dari pengertian di atas, maka dapat dinamakan bahwa :

  • Graph yang mempunyai sirkuit Euler disebut graph Euler (Eulerian graph)

  • Graph yang mempunyai lintasan Euler saja dinamakan graph semi-Euler (semi-Eulerian graph)

  • Graph yang tidak mempunyai lintasan serta sirkuit dinamakan graph non-Euler (non-Eulerian graph)

Contoh:

teorema-2

Lintasan euler : a,b,c,d,e,c,h,b,f,h,e,f,g,a

Graph tersebut memiliki sirkuit euler karena berawal dari simpul a dan berakhir di simpul a

Jawaban : Graph Euler

teorema-1

Lintasan euler : a,b,c,d,e,f,g,b,d,f,a,g

Graph tersebut tidak memiliki sirkuit euler karena simpul awal dan simpul akhir lintasan nya tidak sama.

Jawaban : Graph semi-Euler

screenshot_2018-12-26-course-note-4-graph-euler-dan-hamilton-pdf

Graph di atas tidak memiliki lintasan maupun sirkuit euler

Jawaban : Graph non-Euler

Teorema-Teorema

  • Teorema 1

Graph terhubung G adalah Euler jika dan hanya jika derajat dari masing-masing vertex adalah genap.

fig2_5_17-2

Jumlah derajat vertex:

A→4                                D→2

B→2                                E→4

C→4                                F→2

Teorema 1 terbukti

  • Teorema 2

    Jika Graph G memiliki lebih dari dua vertex berderajat ganjil, maka G adalah Graph non Euler.

    Jika G memiliki dua vertex berderajat ganjil, maka G memiliki lintasan Euler dan ini berlaku juga ketika memiliki satu vertex berderajat ganjil.

uryxn

Jumlah derajat vertex:

a→3                                d→2

b→2                                e→3

c→3                                f→3

Graph di atas non-Euler

semi-eulerian_graph

Jumlah derajat vertex:

A→3                                D→3

B→2                                E→2

C→2                                F→2

Graph di atas semi-Euler

Teorema 2 terbukti

  • Teorema 3

    Suatu Graph terhubung adalah Graph Semi Euler jika dan hanya jika memiliki tepat dua vertex yang berderajat ganjil.

th

Jumlah derajat vertex:

1→2                                3→2

2→3                                4→3

Graph semi-Euler

Teorema 3 terbukti

  • Teorema 4

    Graph berarah G memiliki sirkuit euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat masuk dan derajat keluar sama.

    G memiliki lintasan euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat masuk dan derajat keluar sama kecuali dua simpul

fig2_5_17

Jumlah derajat masuk dan derajat keluar:

A→2 dan 2                                D→1 dan 1

B→1 dan 1                                E→2 dan 2

C→2 dan 2                                F→1 dan 1

Setiap simpul memiliki derajat masuk dan derajat keluar yang sama, sehingga graph di atas memiliki sirkuit euler

screenshot-229

Jumlah derajat masuk dan derajat keluar:

a→1 dan 1                                  c→1 dan 1

b→2 dan 1                                 d→1 dan 2

setiap simpul memiliki derajat masuk dan derajat keluar sama kecuali dua simpul, sehingga graph di atas memiliki lintasan euler

Teorema 4 terbukti

Poin Penting Graph yang Memiliki Sirkuit Euler

  1. Derajat vertex tidak sama dengan 0

  2. Jika semua derajat genap, maka dipastikan memiliki lintasan dan sirkuit euler

  3. Jika dua vertex derajat ganjil, maka memiliki lintasan euler tapi tidak memiliki sirkuitnya

  4. Jika dua atau lebih derajat ganjil, maka tidak memiliki lintasan maupun sirkuit euler

Contoh Soal-Jawab

1. Apakah graph di bawah  merupakan non-Euler? Jika iya, buktikan!

soal1

Jawab:

Jumlah derajat vertex :

A→ 2

B→2

C→2

D→3

E→3

F→3

G→3

Dikarenakan graph di atas memiliki lebih dari 2 vertex berderajat ganjil, maka graph tersebut merupakan non-Euler

2. Apakah jenis graph di bawah ini ? Sertakan bukti!

soal2-2

Jawab :

Jumlah derajat vertex :

a→ 2

b→3

c→3

d→2

e→3

f→4

g→3

h→2

Dikarenakan graph di atas memiliki lebih dari 2 vertex berderajat ganjil, maka graph tersebut tidak memiliki lintasan maupun sirkuit, sehingga graph ini dinamakan non-Euler

 

Demikian materi tentang Lintasan dan Sirkuit Euler yang saya ulas, jika ada yang belum paham/ingin bertanya/memberikan kritik serta saran, bisa menambahkan di kolom komentar.

Terima kasih ?

NAMA           : TANIA YOLANDA

NIM               : A11.2017.10055

KELOMPOK : A11.4301

Tagged , , , , , , . Bookmark the permalink.

About Tania Yolanda

Hello, follow me, Youtube Channel: Tania Joelan IG: yolandatania_ xoxo

Leave a Reply

Your email address will not be published. Required fields are marked *