TUJUH JEMBATAN BERSEJARAH

Juni 15th, 2016

pregel

Foto pada tulisan saya kali ini adalah foto sebuah sungai bersejarah, yaitu sungai Pregel. Sungai tersebut terletak di kota Konigsberg, yang kemudian menjadi ibukota Prusia Timur dan selanjutnya berganti nama menjadi Kaliningrad. Di tengah sungai Pregel terdapat dua pulau (C dan D pada gambar di bawah). Kedua pulau terhubung satu sama lain dengan satu buah jembatan, dan terhubung dengan tepi-tepi sungai (A dan B) dengan enam jembatan.

150620165637

Mengapa sungai tersebut dikatakan bersejarah? Di tahun 1736, seorang jenius matematika bernama Leonhard Euler (1707-1783) berhasil memecahkan suatu pertanyaan sulit yang lama mengusik sebagian penduduk Konigsberg di zaman itu, yaitu suatu pertanyaan yang populer dengan nama Konigsberg Bridge Problem, Masalah Jembatan Konigsberg. Masalah tersebut melibatkan 7 buah jembatan yang dilukiskan pada gambar di atas. Yang dipertanyakan adalah: “Bagaimana caranya, dengan titik berangkat yang manapun, berjalan menelusuri semua jembatan tepat satu kali dan kembali lagi ke titik berangkat tadi?” Euler berhasil menjawab persoalan tersebut menggunakan teori graf (Graph Theory), yang merupakan salah satu topik dalam matematika.

 

Apakah graf itu? Suatu graf G(V,E) terdiri dari suatu himpunan tak kosong V yang beranggotakan verteks-verteks (vertices) dan himpunan E yang beranggotakan tepi-tepi (edges) sedemikian setiap tepi ek ∊ E diidentifikasi dengan suatu pasangan tak berurut (vi,vj), dengan vi, vj ∊ V. Verteks vi dan vj yang mendefinisikan tepi ek dinamakan verteks-verteks ujung ek. Jika verteks vi merupakan suatu verteks ujung dari tepi ek, dikatakan bahwa tepi ek insiden dengan verteks vi. Banyaknya tepi yang insiden dengan verteks vi, ditulis d(vi), dinamakan derajat verteks vi.

 

Masalah jembatan Konigsberg dapat digambarkan secara sederhana sebagai berikut.

Konigsberg

Gambar tersebut mengilustrasikan suatu graf G(V,E), dengan V = {A, B, C, D}, E = {e1, e2, e3, e4, e5, e6, e7} dan e1= (A,C), e2 = (A,C), e3 = (B,C), e4 = (B,C), e5 = (A,D), e6 = (B,D), e7 = (C,D). Tepi e1 diidentifikasi dengan pasangan tak berurut (A,C), e2 dengan pasangan tak terurut (A,C), e3 dengan (B,C), dan seterusnya. Pasangan-pasangan tersebut dikatakan tak berurut dalam arti bahwa (A,C) dapat ditulis (C,A) tanpa ada perubahan arti, demikian juga (B,D) dapat ditulis (D,B), (C,D) dapat ditulis (D,C), dan seterusnya. A dan C adalah verteks-verteks ujung dari tepi e1 dan e2. B dan C adalah verteks-verteks ujung dari e3 dan e4, A dan D adalah verteks-verteks ujung dari e5, B dan D adalah verteks-verteks ujung dari e6, C dan D adalah verteks-verteks ujung dari e7.

 

Konsep derajat suatu verteks diperlukan untuk menjawab masalah jembatan Konigsberg. Karena itu saya memperkenalkan istilah insidensi antara tepi dan verteks, juga derajat suatu verteks. Terdapat 3 buah tepi yang insiden dengan verteks A, yaitu tepi e1, e2, e5 sehingga derajat A adalah d(A) = 3. Terdapat 3 buah tepi yang insiden dengan verteks B, yaitu tepi e3, e4, e6 sehingga derajat B adalah 3, ditulis d(B) = 3. Yang derajatnya paling tinggi adalah C; d(C) = 5 karena ada 5 tepi yang insiden dengan C, yaitu e1, e2, e3, e4, e7. Verteks D memiliki 3 tepi yang insiden dengannya, yaitu e5, e6, e7 sehingga d(D) = 3.

 

Masalah Jembatan Konigsberg, dalam teori graf, mempertanyakan apakah pada graf G(V,E) tersebut di atas memuat suatu garis Euler (Euler line). Garis Euler adalah suatu perjalanan tertutup di suatu graf yang memuat semua tepi graf tersebut. [Perjalanan tertutup di sini berarti perjalanan yang memiliki titik awal berangkat yang sama dengan titik akhir perjalanan.] Graf yang memuat suatu garis Euler dinamakan graf Euler.

 

Apakah graf G(V,E) pada Masalah Jembatan Konigsberg merupakan graf Euler? Euler menjawabnya dengan suatu teorema: “Suatu graf terhubung G merupakan graf Euler jika dan hanya jika semua verteks G berderajat genap.” Pada Masalah Jembatan Konigsberg, semua verteks berderajat ganjil. Jadi, tidak mungkin dibuat suatu perjalanan yang berangkat dan berakhir di tempat yang sama dan menelusuri setiap jembatan tepat satu kali!

 

Contoh paling sederhana graf Euler adalah graf G1(V1,E1) dengan V1 = {A, B, C}, E1 = {p, q, r}, dan p = (A,B), q = (B,C), r = (C,A), yang diilustrasikan sebagai berikut.

Euler_1

Perhatikan bahwa semua verteks dalam graf G1 berderajat genap (yaitu 2). Berangkat dari satu titik, menelusuri semua sisi segitiga itu dan kembali di titik yang sama [rute: ApBqCrA] merupakan suatu garis Euler. Graf G1 merupakan graf Euler.

 

Graf Euler lainnya yang memuat lebih banyak verteks dan tepi adalah suatu graf yang terkenal dengan nama Mohammed’s Scimitars. Graf tersebut memuat 11 buah verteks dan 18 buah tepi, yang dapat diilustrasikan sebagai berikut.

Euler_2

Dapatkah Anda menemukan garis Euler dalam graf tersebut?

 

Mengenai teori graf dapat Anda pelajari di tautan berikut: lemma jabat tangan

 

 

 

 

 

 

Tagging: , ,

Most visitors also read :



Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *