graph euler

BAB I

PENDAHULUAN

A.    LATAR BELAKANG

Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.

Sejarah Graf: masalah jembatan Königsberg (tahun 1736)

Gambar. Masalah Jembatan Königsberg

Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?

B.     TUJUAN

C.     MANFAAT

BAB II

PEMBAHASAN

A.    Definisi Graph

(Definisi graph secara singkat)

Graph adalah diagram yang terdiri dari noktah-noktah yang disebut titik, dan garis-garis yang menghubungkan titik-titik tersebut yang dinamakan sisi, dan setiap sisi tepat menghubungkan dua titik.

Contoh:

Graf G = (V, E), yang dalam hal ini:

     V  = himpunan tidak-kosong dari titik-titik (vertices)

= { v₁ , v₂ , ... , v_n }

     E = himpunan sisi  (edges) yang menghubungkan sepasang

    simpul

= {e₁ , e₂ , ... , e_n }

         G₁                                   G₂                                    G₃

                                   

Gambar: (a) graf sederhana, (b) graf ganda, dan (c) graf semu

Pada Gambar, G₁ adalah graf dengan

V = { 1, 2, 3, 4 }

            E =  { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }

G₂ adalah graf dengan

V = { 1, 2, 3, 4  }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }       = { e₁, e₂, e₃, e₄, e₅, e₆, e₇}

G₃ adalah graf dengan

V = { 1, 2, 3, 4  }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }

= { e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈}                                                                                

• Pada G₂, sisi  e₃ = (1, 3) dan sisi e₄ = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
• Pada G₃, sisi e₈ = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

B.     Digraph terhubung

a.      Definisi graph terhubung

Misalkan titik v dan w pada graph G, jika titik v dan w dihubungkan dengan suatu sisi e, maka v dan w dikatakan terhubung langsung.

Misalnya sebuah graph G di bawah ini:

Maka u dan v terhubung langsung, u dan w tidak terhubung langsung, tapi terhubung.

b.      Walk (jalan)

Contoh:

v₁e₁v₂, v₂e₂v₄, v₄e₄v₃, v₃e₃v₂, v₂e₆v₆, v₆e₇v₅, v₅e₅v₃, atau disingkat

v₁ v₂ v₄ v₃ v₂ v₆ v₅ v_3.

Definisi: Walk (Jalan) adalah sederetan bergantian dari titik dan sisi, di mulai dari titik dan berakhir juga pada suatu titik.

Catatan:

1.      Titik dan sisi boleh berulang

2.      Jika titik awal sama dengan titik akhir disebut walk tertutup.

Berikan 3 contoh walk dari graph di bawah ini.

 

c.       Trail (tapak)

Contoh:

Pada graph diatas maka trail yang mungkin antara lain:

v₃ v₇ v₄ v₁ v₂ v₇ v₈ v₅ v_6,

v₇ v₄ v₁ v₂ v₅ v₈ v₇ v₃ v₁ v₇ (Trail Tertutup)

DEFINISI: Trail adalah walk (jalan) dengan sisi-sisi yang berbeda (tidak boleh berulang).

d.      Path (lintasan)

Contoh: Perhatikan contoh graph pada trail diatas. Path yang mungkin antara lain:

v₃ v₇ v₄ v₁ v₂ v₅ v₆

v₇ v₁ v₄ v₅ v₂ v₇ (path tertutup)

DEFINISI: Path adalah trail dengan titik-titiknya semuanya berbeda, kecuali untuk path tertutup di mana titik awal dan titik akhir sama.

e.       Sikel (cycle) atau sirkuit (circuit)

Contoh: Perhatikan contoh graph pada walk diatas. Sikel yang mungkin antara lain:

[v₃ v₁ v₄ v₅ v₈ v₇ v₃],

[v₇ v₄ v₁ v₂ v₅ v₈ v₇]

Definisi: Sikel adalah path tertutup

Definisi: Graph yang tidak punya sikel disebut graph asikel (asiklik)

Contoh graph di bawah ini adalah graph asiklik

Definisi: Panjang walk, trail, path dan sikel adalah banyaknya sisi yang terdapat didalam walk, trail, path dan sikel tersebut.

Definisi: Panjang sikel dari suatu graph G(C(G)) yang terbesar adalah panjang sikel yang terpanjang dari graph G tersebut.

Coba anda tentukan panjang sikel terbesar dari graph pada contoh trail diatas.

Teorema: Sebuah walk u – v dalam sebuah graph G berisi sebuah path u – v 

Bukti:

Misalkan W adalah walk u – v di G.

Andaikan W=u=u₀, u₁, u₂, ….. ,u_n=v sebuah walk terbuka u – v di G.

Pada W mungkin memuat titik yang muncul lebih dari satu kali (perhatikan definisi walk).

Andaikan W=u=u₀, u₁, u₂, ….. ,u_i, u_i+1, u_i+2, ….. , u_i, u_j, u_j+1, ….. ,u_n=v, dari W ini dihapus u_i+1, u_i+2, ….. , u_i.

Diperoleh W₁=u= u₀, u₁, u₂, ….. ,u_i, u_j+1, ….. ,u_n=v.

Tentu banyak suku pada W₁ lebih kecil dari W. Jika dalam W₁ masih terdapat titik yang muncul lebih dari satu kali, maka proses dilanjutkan seperti diatas sampai kita peroleh sebuah lintasan u – v.

C.     Graph Euler

Graph Euler mula-mula muncul pada tahun 1736, ketika seseorang matematikawan dari Swiss Leonhard Euler mencoba memecahkan masalah yang dikenal dengan nama The Konigsberg Bridge Problem seperti di bawah ini.

Masalahnya adalah mungkinkah dimulai dari suatu tempat mengunjungi setiap tempat dengan melewati ketujuh jembatan tersebut tepat satu kali kemudian kembai ketempat semula?

Definisi graph Euler: Graph terhubung G dinamakan graph Euler jika ada trail tertutup yang memuat sisi di G. Trail tersebut disebut trail Euler.

Teorema : jika G graph terhubung, maka G graph Euler jika dan hanya jika setiap titik berderajat genap.

Teorema : sebuah graph nontrivial terhubung, maka G mengandung trail Euler jika dan hanya jika G mempunyai tepat dua titik yang berderajat ganjil. selanjutnya trail dimulai dari salah satu titik yang berderajat ganjil dan berakhir dititik yang berderajat ganjil yang lain.

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.

Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.

Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).

Contoh :

Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1

Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3

Sirkuit Euler pada graf (c)    : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1

Sirkuit Euler pada graf (d)    : a, c, f,  e, c, b, d, e, a, d, f, b, a

Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler

Dimana :(a) dan (b) graf semi-Euler

(c) dan (d) graf Euler

(e) dan (f) bukan graf semi-Euler atau graf Euler

Teorema  :Graf tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.

Teorema :Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.

(Catatlah bahwa graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya)

Teorema  :Graf 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, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

(a) Graf  berarah Euler (a, g, c, b, g, e, d, f, a)

(b) Graf berarah semi-Euler (d, a, b, d, c, b)

(c) Graf berarah bukan Euler maupun semi-Euler

D.    Algoritma Fleury

Jika G merupakan graph Euler, maka langkah-langkah berikut selalu dijalankan dan menghasilkan trail Euler di G.

            1.        Pilih titik awal u

            2.        Jalankan dengan selalu harus memenuhi syarat sebagai berikut :

                       a.        Hapuslah sisi-sisi yang sudah dilewati, apabila dengan menghapus tadi menghasilkan titik terasing hapus juga titik itu.

                       b.        Gunakan jembatan hanya bila terpaksa (pilihan terakhir).

e

a

c

            Contoh :

 

f

d

u

b

            Pilih titik u. ua, ab dihapus, bu tidak bias dipilih karena merupakan jembatan, pilih bc, cd dan hapus, kemudian db, bu, ue, ef, dan fu.

            Jadi trail Eulernya adalah u a b c d b u e f u.

BAB III

PENUTUP

A.    Kesimpulan

Graph Euler mula-mula muncul pada tahun 1736, ketika seseorang matematikawan dari Swiss Leonhard Euler mencoba memecahkan masalah yang dikenal dengan nama The Konigsberg Bridge Problem

Definisi graph Euler: Graph terhubung G dinamakan graph Euler jika ada trail tertutup yang memuat sisi di G. Trail tersebut disebut trail Euler.

Teorema : jika G graph terhubung, maka G graph Euler jika dan hanya jika setiap titik berderajat genap.

Teorema : sebuah graph nontrivial terhubung, maka G mengandung trail Euler jika dan hanya jika G mempunyai tepat dua titik yang berderajat ganjil. selanjutnya trail dimulai dari salah satu titik yang berderajat ganjil dan berakhir dititik yang berderajat ganjil yang lain.

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.

Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.

Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).

B.     Saran

Bagi pembaca yang ingin lebih memahami tentang teory graph khususnya Graph Euler, mungkin makalah ini dapat membantu pembaca. Namun lebih baik lagi jika pembaca menambah literatur lain untuk lebih memahami tentang pembahasan ini.

Semoga makalah ini bermanfaat.

DAFTAR PUSTAKA

Hand Out Mata Kuliah Teory graph.

http//: graph/sirkuit-euler.htm (16 november 2011)

http//: graph/lintasan-dan-sirkuit-euler.html (16 november 2011)