Jawaban:

Graph sering digunakan untuk merepreesntasikan sebuah objek dan hubungannya dengan objek lain. Sejarah teori graph bermula saat ahli matematika Swiss Leonhard Euler memecahkan masalah jembatan Königsberg . Masalah jembatan Königsberg adalah teka-teki lama mengenai kemungkinan menemukan jalan setapak di tujuh jembatan yang membentang di sepanjang sebuah sungai bercabang yang melewati sebuah pulau tapi dengan tanpa melewati jembatan dua kali. Euler berpendapat bahwa tidak ada jalan semacam itu. Buktinya hanya mengacu pada susunan fisik jembatan, namun intinya dia membuktikan teorema pertama dalam teori graph (Carlson, 2017).

Seperti yang digunakan dalam teori grafik, grafik istilah tidak mengacu pada grafik data, seperti grafik garis atau grafik batang. Sebaliknya, ini mengacu pada sekumpulan simpul (yaitu titik atau simpul) dan tepi (atau garis) yang menghubungkan simpul. Bila dua simpul digabungkan lebih dari satu tepi, grafiknya disebut multi graph. Grafik tanpa loop dan paling banyak satu tepi antara dua simpul disebut grafik sederhana. Kecuali dinyatakan lain, grafik diasumsikan mengacu pada grafik sederhana. Bila setiap simpul dihubungkan oleh ujung ke setiap titik lainnya, grafik disebut grafik lengkap. Bila sesuai, arah dapat diberikan ke masing-masing ujung untuk menghasilkan apa yang dikenal sebagai grafik terarah, atau digraf (Carlson, 2017).

Graph pada dasarnya mempunyai komponen berupa simpul dan sisi dan pada graph tersebut sehingga membentuk graph terbuka dan graph tertutup sehingga membentuk sejumlah lintasan dan sirkuit. Sehingga pada teorema graph telah dapat menyelesaikan tanda tanya dalam penyelesaian teka-teki jembatan Konigsberg dan dengan solusi masalah yang sama (Wirdasari, 2011).

Masalah di Konigsberg (7 crossing point on progel river)

Euler adalah seorang ahli matematika yang mencoba untuk memecahkan teka-teki tersebut dan lebih dikenal dengan masalah Jembatan Konigsberg (Wirdasari, 2011). Terdapat 7 (tujuh) buah jembatan yang dapat menghubungkan 2 (dua) pulau dan juga sebuah sungai, seperti yang ditunjukkan pada Gambar 1 .

Urban planning problem

Dalam mecari solusi tersebut euler seorang matematika tersebut mencoba metode dari masalah ini adalah dengan membentuk model dari jembatan Konigsberg yang dikenal dengan multigraph, diperlihatkan pada Gambar 2. Pada multigraph tersebut memiliki 2 (dua) elemen yaitu himpunan verteks (titik/node) dan himpunan edge (garis) yang saling menghubungkan garis antar verteks (Wirdasari, 2011).

Titik-titik yang diberi label X, Y, Z, dan W pada Gambar 2 itulah yang disebut verteks dan dengan garis saling menghubungkan antar titik itulah yang disebut dengan edge.

Pada semua multigraph euler telah membuat sebuah aturan yang dapat dipakai dalam mencari solusi pada jembatan Konigsberg, sehingga aturan ini disebut dengan sebutan Eulerian path, yang berbunyi:

“Andai kita mempunyai sebuah multigraph untuk beberapa pasang verteks sehingga akan terdapat sebuah path (lintasan) diantara verteks-verteks tersebut. Multigraph tersebut memiliki eulerian  path dan jika terdapat 0 datau 2 verteks tersebut maka banyak edge yang meninggalkan verteks tersebut akan berjumlah ganjil”

Pada Multigraph jembatan Konigsberg tersebut memiliki empat verteks dan pada ke-empat verteks tersebut memiliki edge sehingga meninggalkan verteks yang berjumlah ganjil. Maka Eulirian path tersebut tidak dimiliki pada multigraph jembatan Konigsberg. Multigraph yang ditunjukkan pada Gambar 3 tidak memiliki panah, sehingga disebut dengan undirected graph (graph tak berarah). Sehingga disebut dengan directed graph (graph berarah) adalah multigraph yang memiliki panah yang ditujukan pada gambar 4.

Definisi 1. Sebuah simple graph (undirected graph) adalah pasangan dari G = (V , E) dimana:

V =  himpunan berhingga dari elemen yang disebut verteks

E =  sebuah relasi yang irrefleksif dan simetri pada V.

Pasangan berurutan pada E disebut edge dari graph yang berurutan . Lebih spesifik, jika e = (u, v) Î E , dikatakan bahwa edge e adalah antara u dan v (dan juga antara v dan u ), dan dikatakan bahwa u adjacent ke v . Lebih jauh, dapat dikatakan bahwa e incident ke u (dan juga v ). Karena E simetri, maka kita dapat menotasikan e sebagai pasangan tak berurut {u, v}.

Pemecahan oleh Euler

Hasil dari Teka-Teki Jembatan Konigsberg berdampak sungguh luar biasa terhadap ilmu pengetahuan. Dari teka-teki tersebut sangat berguna dan telah membuka jalan bagi terciptanya teorema baru yang disebut teorema graph. (Studi & Informatika, n.d.).

Penjelasan: