Apa yang dimaksud dengan Teori Graf?

matematika_diskrit

(Qoirrudin raga pratama) #1

Teori Graf

Terdapat beberapa topik yang dibahas dalam matematika diskrit. Salah satunya adalah Teori Graf. Apa yang dimaksud dengan Teori Graf (graph-included tree)?


Bagaimana merepresentasikan Graf dalam Matriks ?
(Karla Amanda) #2

Teori Graf merupakan suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari graf digunakan untuk mengambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti.

Beberapa contoh graf yang sering dijumpai, antara lain struktur organisasi, bagan alir, pengambilan mata kuliah, peta, rangkaian listrik, dan lain-lain (Hendardi, A. 2012).

Banyak sekali struktur yang bisa dipresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan graf. Sering kali graf digunakan untuk mempresentasikan suatu jaringan. Misalkan jaringan jalan raya dengan kota sebagai simpul ( vertex ) dan jalan yang menghubungkan setiap kota sebagai sisi ( edge ) dan bobotnya ( weight ) adalah panjang dari jalan tersebut.

Secara matematis graf mendefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul ( vertex atau node ) dan E adalah himpunan sisi ( edge ) yang menghubungkan sepasang simpul (Munir, R. 2009)

Simpul ( vertex ) pada graf dapat dinyatakan dengan huruf, bilangan atau gabungan keduanya. Sedangkan sisi-sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang 𝑒𝑒1, 𝑒𝑒2, 𝑒𝑒3 dan seterusnya.

Teori Dasar Graf


Graf G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G=(V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul dan E adalah himpunan sisi yang menghubungkan sepasang simpul (Munir, R. 2005).

Garis yang hanya berhubungan dengan satu titik ujung disebut loop . Dua garis berbeda yang menghubungkan titik yang sama disebut garis paralel. Dua titik dikatakan berhubungan ( adjacent ) jika garis menghubungkan keduanya. Titik yang tidak memiliki garis yang berhubungan dengannya disebut titik terasing ( isolating point ). Graf yang tidak memiliki titik (sehingga tidak mewakili garis) disebut garis kosong.

Jika semua garisnya berarah, maka grafnya disebut graf berarah ( directed graph ), atau sering disingkat di graph . Jika semua garisnya tidak berarah, maka grafnya disebut graf tak berarah ( undirected graph ). Sehinga dapat ditinjau dari arahnya, graf dapat dibagi menjadi dua yaitu graf berarah dan graf tidak berarah.

Graf Berarah (Directed Graf = Digraph)

Pada graf berarah, arah sisi/urutan ikut diperhatikan. Dalam suatu graf, lintasan ( path ) adalah urutan simpul, atau sisi yang dibentuk untuk bergerak dari satu simpul ke simpul yang lain. Dalam graf berarah, titik akhir dari sebuah busur akan menjadi titik awal dari busur berikutnya. Sirkuit adalah lintasan yang memiliki simpul awal dan akhir yang sama. Panjang lintasan adalah banyaknya sisi yang dilalui lintasan tersebut.

Suatu Graf berarah G terdiri dari himpunan titik-titik V(G) {𝑣𝑣1, 𝑣𝑣2, …}, himpunan garis-garis E(G) {𝑒𝑒1, 𝑒𝑒2, … }, dan suatu fungsi yang mengawankan setiap garis dalam E(G) ke suatu pasangan berurutan titik (𝑣𝑣𝑖𝑖 , 𝑣𝑣𝑗𝑗 ). Jika π‘’π‘’π‘˜π‘˜ = (𝑣𝑣𝑖𝑖 , 𝑣𝑣𝑗𝑗 ) adalah suatu garis dalam G, maka 𝑣𝑣𝑖𝑖 disebut titik awal π‘’π‘’π‘˜π‘˜ dan 𝑣𝑣𝑗𝑗 disebut titik akhir π‘’π‘’π‘˜π‘˜ . Arah garis adalah dari 𝑣𝑣𝑖𝑖 ke 𝑣𝑣𝑗𝑗 .

Jumlah garis yang keluar dari titik 𝑣𝑣𝑖𝑖 disebut derajat keluar ( out degree ) titik 𝑣𝑣𝑖𝑖 yang disimbolkan dengan 𝑑𝑑+(𝑣𝑣𝑖𝑖 ), sedangkan jumlah garis yang menuju ke titik 𝑣𝑣𝑖𝑖 disebut derajat masuk ( in degree ) titik 𝑣𝑣𝑖𝑖 , yang disimbolkan dengan π‘‘π‘‘βˆ’(𝑣𝑣𝑖𝑖 ).

Titik terasing adalah titik dalam G dimana derajat keluar dan derajat masuknya adalah 0. Titik pendant (tergantung) adalah titik dalam G dimana derajat masuk dan derajat keluarnya adalah 1. Dua garis berarah dikatakan paralel jika keduanya memiliki titik awal dan titik akhir yang sama.

Contoh

image
Gambar Graf Berarah

Tentukan:

  • Himpunan titik-titik, himpunan garis-garis, dan fungsi perkawanan.
  • Derajat masuk dan derajat keluar tiap titik.
  • Titik terasing dan titik pendant.
  • Garis paralel.

Penyelesaian:

a. V(G) = { 𝑣𝑣1, 𝑣𝑣2, 𝑣𝑣3, 𝑣𝑣4, 𝑣𝑣5, 𝑣𝑣6 }

E(G) = { 𝑒𝑒1, 𝑒𝑒2, 𝑒𝑒3, 𝑒𝑒4, 𝑒𝑒5, 𝑒𝑒6, 𝑒𝑒7, 𝑒𝑒8, 𝑒𝑒9 }

Fungsi mengawankan garis-garis dengan pasangan titik-titik berikut

𝑒𝑒1 dengan (𝑣𝑣1, 𝑣𝑣2)
𝑒𝑒2 dengan (𝑣𝑣4, 𝑣𝑣1)
𝑒𝑒3 dengan (𝑣𝑣1, 𝑣𝑣4)
𝑒𝑒4 dengan (𝑣𝑣1, 𝑣𝑣3)
𝑒𝑒5 dengan (𝑣𝑣3, 𝑣𝑣3)
𝑒𝑒6 dengan (𝑣𝑣3, 𝑣𝑣4)
𝑒𝑒7 dengan (𝑣𝑣3, 𝑣𝑣5)
𝑒𝑒8 dengan (𝑣𝑣5, 𝑣𝑣4)
𝑒𝑒9 dengan (𝑣𝑣5, 𝑣𝑣4)

b.

𝑑𝑑+ (𝑣𝑣1) = 3 π‘‘π‘‘βˆ’ (𝑣𝑣1) = 1
𝑑𝑑+ (𝑣𝑣2) = 0 π‘‘π‘‘βˆ’ (𝑣𝑣2) = 1
𝑑𝑑+ (𝑣𝑣3) = 3 π‘‘π‘‘βˆ’ (𝑣𝑣3) = 2
𝑑𝑑+ (𝑣𝑣4) = 1 π‘‘π‘‘βˆ’ (𝑣𝑣4) = 4
𝑑𝑑+ (𝑣𝑣5) = 2 π‘‘π‘‘βˆ’ (𝑣𝑣5) = 1
𝑑𝑑+ (𝑣𝑣6) = 0 π‘‘π‘‘βˆ’ (𝑣𝑣6) = 0

Dapat dilihat bahwa dalam setiap graf berarah, βˆ‘π‘–π‘– 𝑑𝑑+ (𝑣𝑣𝑖𝑖) = βˆ‘π‘–π‘– π‘‘π‘‘βˆ’ (𝑣𝑣𝑖𝑖)

c. Titik terasing adalah 𝑣𝑣6.
Titik pendant 𝑣𝑣2.

d. Garis paralel adalah 𝑒𝑒8 dan 𝑒𝑒9, dapat dilihat bahwa 𝑒𝑒2 dan 𝑒𝑒3 bukanlah garis paralel karena arahnya berbeda.

Path Berarah dan Sirkuit Berarah

Pengertian walk, path, dan sirkuit dalam graf berarah sama dengan walk, path dan sirkuit dalam graf tak berarah. Hanya saja dalam graf berarah, perjalanan yang dilakukan harus mengikuti arah garis. Untuk membedakan dengan graf tak berarah, maka walk, path berarah, dan sirkuit dalam graf berarah disebut walk berarah, path berarah, dan sirkuit berarah. Suatu graf berarah yang tidak memuat sirkuit berarah disebut Asiklik (Siang, J.J. 2009).

Contoh

Ada 4 macam golongan darah, masing-masing A, B, AB, dan O. Darah golongan O dapat diberikan kepada semua golongan. Darah golongan A dan B dapat diberikan ke golongannya sendiri atau ke golongan O. Darah golongan AB hanya dapat diberikan pada pasien dengan golongan darah AB . Gambarkan graf berarah untuk menyatakan keadaan tersebut. Anggaplah garis dari 𝑣𝑣𝑖𝑖 ke 𝑣𝑣𝑗𝑗 menyatakan bahwa darah dari 𝑣𝑣𝑖𝑖 dapat diberikan pada 𝑣𝑣𝑗𝑗 .

Apakah graf Asiklik?

Penyelesaian:

Graf berarah menyatakan keadaan transfusi darah yang mungkin dilakukan. Dapat dilihat bahwa dalam graf berarah tersebut tidak ada sirkuit berarah sehingga grafnya Asiklik.

image
Gambar Path berarah**

Graf Berarah Terhubung

Suatu graf tak berarah disebut terhubung jika ada walk yang menghubungkan setiap dua titiknya. Pengertian itu berlaku juga bagi graf berarah. Berdasarkan arah garisnya, dalam graf berarah dikenal dua jenis keterhubungan, yaitu terhubung kuat dan terhubung lemah.

Misalkan G adalah suatu graf berarah dan v, w adalah sembarang 2 titik dalam G. G disebut terhubung kuat jika ada path berarah dari v ke w. G disebut terhubung lemah, jika G tidak terhubung kuat, tetapi graf tak berarah yang bersesuaian dengan G terhubung.

Contoh

Manakah di antara graf-graf pada Gambar dibawah ini .yang terhubung kuat dan yang terhubung lemah?


Gambar Graf berarah terhubung

Penyelesaian:

Dalam 𝐺𝐺1, setiap dua titik dapat dihubungkan dengan path berarah sehingga graf berarah 𝐺𝐺1 adalah graf terhubung kuat. Sebaliknya dalam 𝐺𝐺2, tidak ada path berarah yang menghubungkan 𝑣𝑣4 ke 𝑣𝑣3. Akan tetapi, jika semua arah garis dihilangkan (sehingga 𝐺𝐺2 menjadi graf tidak berarah), maka 𝐺𝐺2 merupakan graf yang terhubung. Jadi, 𝐺𝐺2 merupakan graf terhubung lemah.

Isomorfisma dalam Graf Berarah

Pengertian isomorfisma dalam graf berarah sama dengan isomorfisma pada graf tak berarah. Hanya saja pada isomorfisma graf berarah, korespondensi dibuat dengan memperhatikan arah garis.

Contoh

Tunjukkan bahwa graf 𝐺𝐺1 pada Gambar di bawah ini isomorfis dengan 𝐺𝐺2, sedangkan 𝐺𝐺3 tidak isomorfis dengan 𝐺𝐺1


Gambar Isomofisma dalam Graf Berarah

Penyelesaian:

Untuk membuktikan bahwa 𝐺𝐺1 isomorfis dengan 𝐺𝐺2, maka harus dibuat fungsi g : V(𝐺𝐺1) β†’ V(𝐺𝐺2) dan h : E(𝐺𝐺1) β†’ E(𝐺𝐺2) yang mempertahankan titik-titik ujung serta arah garis.

Dalam 𝐺𝐺1, ada 4 garis yang keluar dari 𝑉𝑉3. Titik yang memiliki sifat seperti itu dalam 𝐺𝐺2 adalah titik 𝑣𝑣1, sehingga dibuat fungsi g sedemikian hingga g(𝑣𝑣3) = 𝑣𝑣1, g(𝑣𝑣1) = 𝑣𝑣2, g(𝑣𝑣2) = 𝑣𝑣3, g(𝑣𝑣5) = 𝑣𝑣4, dan g(𝑣𝑣4) = 𝑣𝑣5

fungsi h adalah sebagai berikut:

h ((𝑣𝑣1, 𝑣𝑣2)) = (𝑣𝑣2, 𝑣𝑣3) ; h ((𝑣𝑣2, 𝑣𝑣5)) = (𝑣𝑣3, 𝑣𝑣4) h ((𝑣𝑣5, 𝑣𝑣4)) = (𝑣𝑣4, 𝑣𝑣5) ; h ((𝑣𝑣4, 𝑣𝑣1)) = (𝑣𝑣5, 𝑣𝑣2) h ((𝑣𝑣3, 𝑣𝑣1)) = (𝑣𝑣1, 𝑣𝑣2) ; h ((𝑣𝑣3, 𝑣𝑣2)) = (𝑣𝑣1, 𝑣𝑣3) h ((𝑣𝑣3, 𝑣𝑣5)) = (𝑣𝑣1, 𝑣𝑣4) ; h ((𝑣𝑣3, 𝑣𝑣4)) = (𝑣𝑣1, 𝑣𝑣5)

pada fungsi g dan h dapat dilihat bahwa 𝐺𝐺1 isomorfis dengan 𝐺𝐺2. Selanjutnya, akan dibuktikan bahwa 𝐺𝐺3 tidak isomorfis dengan 𝐺𝐺1. Dalam 𝐺𝐺3, ada garis (𝑣𝑣1, 𝑣𝑣4) dan (𝑣𝑣4, 𝑣𝑣1). Jika 𝐺𝐺1 isomorfis dengan 𝐺𝐺3, maka harus ada fungsi h 𝐺𝐺3 β†’ 𝐺𝐺1 demikian, sehingga h(𝑣𝑣1, 𝑣𝑣4) dan h(𝑣𝑣4, 𝑣𝑣1) merupakan garis-garis dalam 𝐺𝐺1 (dengan kata lain, ada titik 𝑣𝑣𝑖𝑖 dan 𝑣𝑣𝑗𝑗 dalam 𝐺𝐺1 demikian, sehingga ada garis dari 𝑣𝑣𝑖𝑖 ke 𝑣𝑣𝑗𝑗 dan dari 𝑣𝑣𝑗𝑗 ke 𝑣𝑣𝑖𝑖 ). Dalam 𝐺𝐺1 tidak ada garis seperti itu sehingga 𝐺𝐺3 tidak isomorfis dengan 𝐺𝐺1.

Graf Tak Berarah (Undirected Graph)

Suatu graf G terdiri dari dua himpunan yang berhingga, yaitu himpunan simpul-simpul tak kosong (V(G)) dan himpunan jalur-jalur (E(G)). Jika semua jalurnya tidak berarah, maka grafnya disebut graf tak berarah (Siang, J.J. 2009).

Graf Bipartite (Bipartite Graph)

Suatu graf G disebut Graf Bipartite apabila V(G) merupakan gabungan dari dua himpunan tak kosong 𝑣𝑣1 dan 𝑣𝑣2 dan setiap garis dalam G menghubungkan suatu titik dalam 𝑣𝑣1 dengan titik dalam 𝑣𝑣3. Apabila dalam Graf Bipartite setiap titik dalam 𝑣𝑣1 berhubungan dengan setiap titik dalam 𝑣𝑣2, maka grafnya disebut Graf Bipartite lengkap. Jika 𝑣𝑣1 terdiri dari m titik dan 𝑣𝑣2 terdiri dari n titik, maka Graf Bipartite lengkapnya sering diberi simbol πΎπΎπ‘šπ‘š ,𝑛𝑛 .

Contoh

Tentukan mana di antara graf-graf pada Gambar dibawah ini yang merupakan Graf Bipartite dan Bipartite Lengkap.

image
Gambar Graf Bipartite

Penyelesaian:

a. Jelas bahwa titik-titik grafnya terbagi menjadi dua bagian, yaitu 𝑣𝑣1 = {𝑣𝑣1, 𝑣𝑣2, 𝑣𝑣3} dan 𝑣𝑣2 = {𝑣𝑣4, 𝑣𝑣5}. Setiap titik dalam 𝑣𝑣1 dihubungkan dengan setiap titik dalam 𝑣𝑣2 sehingga grafnya merupakan 𝐾𝐾3,2.

b. Hanya merupakan Graf Bipartite saja karena titik-titik dalam graf terbagi menjadi dua bagian, yaitu 𝑣𝑣1 = {𝑣𝑣1, 𝑣𝑣3} dan 𝑣𝑣2 = {𝑣𝑣2, 𝑣𝑣4}. Akan tetapi tidak semua titik dalam 𝑣𝑣1 dihubungkan dengan semua titik dalam 𝑣𝑣2 (𝑣𝑣1 tidak dihubungkan dengan 𝑣𝑣4).

c. Dengan pengaturan letak titik-titiknya, maka graf gambar Β© dapat digambarkan sebagai graf.

image

Tampak bahwa titik-titiknya terbagi menjadi dua bagian, yaitu 𝑣𝑣1 = {𝑣𝑣1, 𝑣𝑣3, 𝑣𝑣5} dan 𝑣𝑣2 = {𝑣𝑣2, 𝑣𝑣4, 𝑣𝑣6}. Setiap menghubungkan sebuah titik dalam 𝑣𝑣1 dengan sebuah titik dalam 𝑣𝑣2 sehingga grafnya merupakan Graf Bipartite.

d. Bila dilihat bahwa meskipun tampil berbeda, sebenarnya graf pada Gambar bagian (d) sama dengan graf pada Gambar bagian (a) sehingga graf pada Gambar bagian (d) adalah 𝐾𝐾3,2.

Posisi titik-titik dalam penggambaran graf kadang-kadang mempengaruhi pandangan, seperti halnya pada Gambar bagian Β© dan (d). Dalam kedua graf tersebut, semua titik tampaknya terhubung dan tidak dapat dipisahkan walaupun kenyataannya tidaklah demikian. Oleh karena itu harus jeli dalam menentukan apakah suatu graf merupakan Graf Bipartite.

SubGraf

Konsep subgraf sama dengan konsep himpunan bagian. Dalam teori himpunan, himpunan A dikatakan merupakan himpunan bagian B bila hanya setiap anggota A merupakan B. Oleh karena graf merupakan himpunan yang terdiri dari titik dan garis, maka H dikatakan subgraf G, jika semua titik dan garis H juga merupakan titik dan garis dalam G. Secara formal, subgraf dapat didefinisikan sebagai berikut.

Misalkan G adalah suatu graf. Graf H dikatakn subgraf G bila dan hanya bila

  • V(H) βŠ† V(G)
  • E(H) βŠ† E(G)
  • Setiap garis dalam H memiliki titik ujung yang sama dengan garis tersebut dalam G.

Dari definisi tersebut ada beberapa hal yang dapat diturunkan

  • Sebuah titik dalam G merupakan subgraf G.

  • Sebuah garis dalam G bersama-sama dengan titik-titik ujungnya merupakan subgraf G.

  • Dalam subgraf berlaku sifat transitif, jika H adalah subgraf G dan G adalah subgraf K, maka K adalah subgraf K.

Contoh

Gambarlah semua Subgraf yang mungkin dibentuk dari graf G pada Gambar dibawah ini.

image
Gambar Sub Graf

Penyelesaian:

G terdiri dari dua titik dan dua garis. Subgraf G yang mungkin dibentuk terdiri dari satu atau dua titik dan 0, satu atau dua garis. Semua Subgraf G yang mungkin dibuat dapat digambarkan sebagai berikut:

image
Gambar Sub-Graf dari Gambar di atas

Derajat (Degree)

Misalkan v adalah titik dalam suatu graf G. derajat titik v (simbol d(v)) adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung dua kali. Derajat total G adalah jumlah derajat semua titik dalam G.

Contoh

Tentukan derajat tiap-tiap titik dalam graf pada Gambar di bawah ini. Berapa derajat totalnya

image
Gambar Derajat (Degree)

Penyelesaian:

d (𝑣𝑣1) = 4 garis yang berhubungan dengan 𝑣𝑣1 adalah 𝑒𝑒2, 𝑒𝑒3 dan loop 𝑒𝑒1 yang dihitung dua kali.

d (𝑣𝑣2) = 2 garis yang berhubungan dengan 𝑣𝑣2 adalah 𝑒𝑒2 dan 𝑒𝑒3.
d (𝑣𝑣3) dan d (𝑣𝑣5) = 1 karena garis yang berhubungan dengan 𝑣𝑣3 dan 𝑣𝑣5 adalah 𝑒𝑒4.
d (𝑣𝑣4) = 2 garis yang berhubungan dengan 𝑣𝑣4 adalah loop 𝑒𝑒5 yang dihitung dua kali. d (𝑣𝑣6) = 0 karena tidak ada garis yang berhubungan dengan 𝑣𝑣6.

Derajat total = βˆ‘6 𝑑𝑑 (𝑣𝑣𝑖𝑖) = 4 + 2 + 1 + 2 + 1 + 0 = 10.

Path dan Sirkuit

Misalkan G adalah suatu graf. Misalkan pula v dan w adalah dua titik dalam G. Suatu Walk dari v dan w adalah barisan titik-titik berhubungan dan garis secara berselang-selang, diawali dari titik v dan diakhiri pada titik w.

Walk dengan panjang n dan v ke w dituliskan sebagai berikut 𝑣𝑣0 𝑒𝑒1 𝑣𝑣1 𝑒𝑒2 𝑣𝑣2… π‘£π‘£π‘›π‘›βˆ’1 𝑒𝑒𝑛𝑛 𝑣𝑣𝑛𝑛 dengan 𝑣𝑣0 = v, 𝑣𝑣𝑛𝑛 = w, 𝑣𝑣𝑗𝑗 βˆ’1, dan 𝑣𝑣𝑖𝑖 adalah titik-titik ujung garis 𝑒𝑒𝑗𝑗 . Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua garisnya berbeda. Path dari v ke w dituliskan sebagai v = 𝑣𝑣0 𝑒𝑒1 𝑣𝑣1 𝑒𝑒2 𝑣𝑣2… π‘£π‘£π‘›π‘›βˆ’1 𝑒𝑒𝑛𝑛 𝑣𝑣𝑛𝑛 = w dengan 𝑒𝑒𝑖𝑖 β‰  w untuk i β‰  j.

image
Gambar Bagan Alur Path dan Sirkuit

Path sederhana dengan panjang n dan v ke w adalah path dari v ke w berbentuk v = 𝑣𝑣0 𝑒𝑒1 𝑣𝑣1 𝑒𝑒2 𝑣𝑣2… π‘£π‘£π‘›π‘›βˆ’1 𝑒𝑒𝑛𝑛 𝑣𝑣𝑛𝑛 = w dengan 𝑒𝑒𝑖𝑖 β‰  w untuk i β‰  j dan π‘£π‘£π‘˜π‘˜ β‰  π‘£π‘£π‘šπ‘š untuk k β‰  m. Sirkuit dengan panjang n adalah path yang dimulai dan diakhiri pada titik yang sama. Sirkuit adalah path yang berbentuk v = 𝑣𝑣0 𝑒𝑒1 𝑣𝑣1 𝑒𝑒2 𝑣𝑣2… π‘£π‘£π‘›π‘›βˆ’1 𝑒𝑒𝑛𝑛 𝑣𝑣𝑛𝑛 = w dengan 𝑣𝑣0 = 𝑣𝑣𝑛𝑛 . Sirkuit sederhana dengan panjang n adalah Sirkuit yang semua titiknya berbeda. Sirkuit sederhana berbentuk v = 𝑣𝑣0 𝑒𝑒1 𝑣𝑣1 𝑒𝑒2 𝑣𝑣2… π‘£π‘£π‘›π‘›βˆ’1 𝑒𝑒𝑛𝑛 𝑣𝑣𝑛𝑛 = w dengan 𝑒𝑒𝑖𝑖 β‰  𝑒𝑒𝑗𝑗 untuk i β‰  j dan π‘£π‘£π‘˜π‘˜ β‰  π‘£π‘£π‘šπ‘š untuk k β‰  m, kecuali 𝑣𝑣0 = 𝑣𝑣𝑛𝑛 .

Sirkuit Euler

Sirkuit Euler adalah Sirkuit yang melalui tiap sisi dalam graf tepat satu kali (Siang, J.J. 2009) Untuk mengenang ahli matematika Leonhard Euler yang berhasil memperkenalkan graf untuk memecahkan masalah tujuh jembatan Koningsberg pada tahun 1736.

Kota Koningberg dibangun pada pertemuan dua cabang sungai Pregel. Kota tersebut terdiri dari sebuah pulau di tengah-tengah dan tujuh jembatan yang mengelilinginya.

image
Gambar Jembatan Konigsberg

Graf Terhubung dan Tidak Terhubung

Misalkan G adalah suatu Graf. Dua titik v dan w dalam G dikatakan terhubung hanya ada walk dari v ke w. Graf G dikatakan terhubung bila hanya setiap dua titik dalam G terhubung. Graf G dikatakan tidak terhubung bila ada dua titik dalam G yang tidak terhubung.

Contoh

Tentukan mana di antara graf pada Gambar dibawah ini yang merupakan Sirkuit Euler. carilah rute perjalanan kelilingnya


Gambar Graf terhubung dan Graf tak terhubung

Penyelesaian:

a. d(𝑣𝑣2) = d(𝑣𝑣3) = d(𝑣𝑣4) = d(𝑣𝑣6) = d(𝑣𝑣10) = 2
d(𝑣𝑣5) = 4
d(𝑣𝑣7) = d(𝑣𝑣8) = d(𝑣𝑣9) = 3
d(𝑣𝑣1) = 5

karena ada titik yang berderajat ganjil, maka (a) bukanlah Sirkuit Euler.

b. Meskipun semua titiknya berderajat dua (genap), tetapi grafnya tidak terhubung. Jadi, (b) bukanlah Sirkuit Euler.

c. d(𝑣𝑣1) = d(𝑣𝑣3) = 2
d(𝑣𝑣2) = d(𝑣𝑣4) = d(𝑣𝑣5) = 4

karna graf ( c) terhubung dan semua titiknya berderajat genap, maka ( c) merupakan Sirkuit Euler.

Sirkuit Hamilton

Suatu graf terhubung G disebut Sirkuit Hamilton bila ada sirkuit yang mengunjungi setiap titiknya tepat satu kali kecuali titik awal yang sama dengan titik akhirnya.

Perhatikan perbedaaan Sirkuit Euler dan Sirkuit Hamilton. Dalam Sirkuit Euler, semua garis harus dilalui tepat satu kali, sedangkan semua titiknya boleh dikunjungi lebih dari satu kali. Sebaliknya, dalam Sirkuit Hamilton semua titik harus dikunjungi tepat satu kali dan tidak harus melalui semua garis. Dalam Sirkuit Euler, yang dipentingkan adalah garisnya. Sebaliknya dalam Sirkuit Hamilton, yang dipentingkan adalah kunjungan pada titiknya(Munir, R. 2009).