Teorema 5.13.
Graf \(\bfG\) merupakan graf Euler jika dan hanya jika graf tersebut terhubung dan setiap simpulnya berderajat genap.
Subbab 5.3 Graf Euler dan Hamilton
Teori graf adalah bidang matematika yang memiliki banyak penerapan dalam berbagai disiplin. Sepanjang buku ini, kita akan menjumpai sejumlah penerapan tersebut. Namun, asal-usul teori graf dapat ditelusuri ke sebuah masalah di Königsberg, Prusia (sekarang Kaliningrad, Rusia) hampir tiga abad yang lalu. Sungai Pregel mengalir melintasi kota itu, dengan dua pulau besar di tengah alirannya. Pulau-pulau tersebut terhubung ke daratan utama melalui tujuh jembatan seperti ditunjukkan dalam Gambar 5.12. Konon, warga Königsberg sering bertanya-tanya apakah seseorang dapat meninggalkan rumahnya, berjalan mengelilingi kota sambil melintasi setiap jembatan tepat satu kali, lalu kembali lagi ke rumah. Leonhard Euler menyelesaikan masalah ini pada tahun 1736 dengan menggunakan teori graf dalam bentuk Teorema 5.13.
Peta skematis Sungai Pregel yang membagi empat daratan Königsberg, dengan tujuh jembatan yang menghubungkannya
Misalkan \(\bfG\) adalah graf tanpa simpul terisolasi. Kita menyebut \(\bfG\) sebagai graf Euler jika terdapat barisan \((x_0,x_1,x_2,\dots,x_t)\) yang terdiri atas simpul dari \(\bfG\text{,}\) dengan pengulangan diperbolehkan, sedemikian sehingga
-
\(x_0=x_t\text{;}\)
-
untuk setiap \(i=0,1,\dots, t-1\text{,}\) \(x_ix_{i+1}\) merupakan sisi dari \(\bfG\text{;}\)
-
untuk setiap sisi \(e\in E\text{,}\) terdapat tepat satu bilangan bulat \(i\) dengan \(0\le i\lt t\) yang memenuhi \(e=x_ix_{i+1}\text{.}\)
Jika \(\bfG\) merupakan graf Euler, barisan yang memenuhi ketiga syarat tersebut disebut sirkuit Euler. Barisan simpul \((x_0,x_1,\dots,x_t)\) disebut sirkuit jika hanya memenuhi dua syarat pertama. Perhatikan bahwa barisan yang hanya terdiri atas satu simpul merupakan sirkuit. Sebelum melanjutkan ke karakterisasi Euler yang anggun bagi graf Euler, mari gunakan SageMath untuk menghasilkan beberapa graf yang bersifat Euler maupun yang tidak.
Jalankan kode di bawah ini. Kode tersebut akan terus berjalan hingga menemukan graf \(\bfG\) yang bersifat Euler. Keluaran yang dihasilkan berupa daftar derajat simpul-simpul graf \(\bfG\text{,}\) diikuti gambar \(\bfG\text{.}\)
Kami menganjurkan Anda menjalankan kode di atas beberapa kali, bahkan dengan mengubah jumlah simpul dan sisinya. Jika eksekusinya terasa lama, mungkin jumlah sisi yang Anda tetapkan terlalu sedikit; cobalah menambahnya sedikit. Apakah Anda memperhatikan sesuatu pada derajat simpul-simpul graf yang dihasilkan?
Sekarang mari kita coba menemukan graf \(\bfH\) yang tidak bersifat Euler. Sekali lagi, keluarannya berupa daftar derajat simpul \(\bfH\text{,}\) diikuti gambar \(\bfH\text{.}\)
Salah satu hal yang mungkin Anda perhatikan ketika menjalankan blok kode kedua adalah bahwa hasilnya cenderung muncul jauh lebih cepat daripada blok pertama. Hal ini menunjukkan bahwa graf non-Euler lebih banyak daripada graf Euler. Apakah Anda memperhatikan perbedaan pada derajat simpul-simpul graf ini dibandingkan dengan graf Euler?
Teorema dasar berikut memberikan karakterisasi lengkap bagi graf Euler. Buktinya menghasilkan algoritma yang mudah diimplementasikan.
Bukti.
Jelas bahwa graf Euler harus terhubung. Selain itu, jika \((x_0,x_1,\dots,x_t)\) merupakan sirkuit Euler dalam \(\bfG\text{,}\) maka untuk setiap \(i=0,1,\dots,t-1\text{,}\) sisi \(x_ix_{i+1}\) dapat dipandang keluar dari \(x_i\) dan masuk ke \(x_{i+1}\text{.}\) Derajat setiap simpul harus genap karena, untuk setiap simpul \(x\text{,}\) banyaknya sisi yang keluar dari \(x\) sama dengan banyaknya sisi yang masuk ke \(x\text{.}\) Selain itu, setiap sisi yang bersisian dengan \(x\) pasti keluar dari \(x\) atau masuk ke \(x\text{.}\)
Sekarang kita uraikan suatu proses deterministik yang akan (a) menemukan sirkuit Euler, (b) menunjukkan bahwa graf tak terhubung, atau (c) menemukan simpul berderajat ganjil. Uraian ini disederhanakan dengan mengasumsikan bahwa simpul-simpul \(\bfG\) telah diberi label bilangan bulat positif \(1,2,\dots,n\text{,}\) dengan \(n\) menyatakan banyaknya simpul dalam \(\bfG\text{.}\) Selain itu, kita tetapkan \(x_0=1\text{.}\)
Kita memulai algoritma dengan sirkuit trivial \(C\) yang hanya memuat simpul \(x_0=(1)\text{.}\) Selanjutnya, misalkan kita memiliki sirkuit parsial \(C\) yang didefinisikan oleh \((x_0,
x_1,\dots,x_t)\) dengan \(x_0=x_t=1\text{.}\) Sisi-sisi berbentuk \(x_ix_{i+1}\) telah dilalui, sedangkan sisi-sisi lain dalam \(\bfG\) (jika ada) belum dilalui. Jika syarat ketiga bagi sirkuit Euler terpenuhi, proses selesai; jadi, kita asumsikan bahwa syarat itu belum terpenuhi.
Kemudian kita memilih bilangan bulat terkecil \(i\) sehingga terdapat sisi yang bersisian dengan \(x_i\) dan belum dilalui. Jika tidak ada bilangan bulat semacam itu, sementara masih terdapat sisi yang belum dilalui, berarti kita telah menemukan bahwa graf tersebut tak terhubung. Kita dapat mengasumsikan bahwa bilangan bulat \(i\) tersebut ada. Tetapkan \(u_0=x_i\text{.}\) Kita mendefinisikan barisan \((u_0,u_1,\dots,u_s)\) secara rekursif. Jika \(j\ge 0\text{,}\) tetapkan
\begin{equation*}
N_j=\{y: u_jy\text{ is an edge in }\bfG\text{ and has not yet been traversed.} \}
\end{equation*}
Jika \(N_j\neq\emptyset\text{,}\) kita pilih \(u_{j+1}\) sebagai bilangan bulat positif terkecil dalam \(N_j\text{.}\) Jika \(N_j=\emptyset\text{,}\) maka \(j\ge1\text{;}\) kita tetapkan \(s=j\) dan menghentikan subrutin ini.
Ketika subrutin berhenti, kita meninjau dua kasus. Jika \(u_0\neq u_s\text{,}\) maka \(u_0\) dan \(u_s\) merupakan simpul berderajat ganjil dalam \(\bfG\text{.}\) Dengan demikian, tersisa kasus \(u_0=u_s=x_i\text{.}\) Dalam kasus ini, kita cukup memperluas barisan semula \((x_0,x_1,\dots,x_t)\) dengan mengganti bilangan bulat \(x_i\) oleh barisan \((u_0,u_1,\dots,u_s)\text{.}\)
Sekarang kita merangkum algoritma dalam bukti Teorema 5.13. Perhatikan bahwa di sini algoritma ditentukan dengan memprioritaskan simpul menurut urutan numerik, dengan asumsi \(V(\bfG) = [n] \text{.}\) Jika, seperti dalam beberapa latihan, simpul diberi label huruf, Anda harus menafsirkan algoritma ini sebagai memprioritaskan simpul menurut urutan alfabetis. Algoritma ini juga diuraikan secara iteratif, tetapi menghasilkan sirkuit Euler yang sama dengan metode rekursif dalam bukti tersebut.
Algoritma 5.14. Pencari Sirkuit Euler.
- Masukan
-
Sebuah graf \(\bfG=([n],E)\)
- Keluaran
-
Sebuah sirkuit Euler \(C\) dalam \(\bfG\text{,}\) sebuah simpul berderajat ganjil dalam \(\bfG\text{,}\) atau sebuah komponen terhubung dari \(\bfG\) beserta sebuah sisi \(\bfG\) yang tidak berada dalam komponen terhubung tersebut.
-
Inisialisasikan \(C=(1)\text{.}\)
-
Selama belum semua sisi \(\bfG\) dilalui, tentukan apakah ada simpul \(C\) yang bersisian dengan sisi yang belum dilalui.
-
Jika semua sisi yang bersisian dengan setiap simpul \(C\) telah dilalui, kembalikan simpul-simpul \(C\) sebagai komponen terhubung dari \(\bfG\text{,}\) beserta sebuah sisi yang tidak dilalui oleh \(C\) sebagai bukti bahwa \(\bfG\) tak terhubung.
-
Jika \(C\) memiliki simpul yang bersisian dengan sisi yang belum dilalui, sebut simpul itu \(u_0\text{.}\) Bentuk sebuah jalan \(W\) yang dimulai dari \(u_0\text{.}\) Dari simpul \(u_i\text{,}\) ikuti sisi yang belum dilalui oleh \(C\) maupun \(W\) menuju tetangga \(u_i\) dengan label terkecil.
-
Pembentukan \(W\) berhenti pada simpul \(u_s\) ketika semua sisi yang bersisian dengan simpul tersebut telah dilalui.
-
Jika \(u_s\neq u_0\text{,}\) kembalikan \(u_0\) sebagai simpul berderajat ganjil, yang menunjukkan bahwa \(\bfG\) bukan graf Euler.
-
Jika \(u_s = u_0\text{,}\) perbarui sirkuit \(C\) dengan mengganti \(u_0\) dalam \(C\) menggunakan jalan \(W\text{.}\) Lanjutkan iterasi dengan kembali ke langkah 2.
-
-
-
Kembalikan \(C\text{.}\)
Sebagai contoh, perhatikan graf \(\bfG\) yang ditunjukkan dalam Gambar 5.15. Jelas bahwa graf ini terhubung dan semua simpulnya berderajat genap. Berikut adalah barisan sirkuit yang dimulai dengan sirkuit trivial \(C\) yang hanya memuat simpul \(1\text{.}\)
\begin{align*}
C \amp =(1)\\
\amp \mapsto (1,2,4,3,1)\quad \text{start next from }2\\
\amp \mapsto(1,2,5,8,2,4,3,1)\quad\text{start next from } 4\\
\amp \mapsto(1,2,5,8,2,4,6,7,4,9,6,10,4,3,1)\quad\text{start next from } 7\\
\amp \mapsto(1,2,5,8,2,4,6,7,9,11,7,4,9,6,10,4,3,1)\quad\text{Done!!}
\end{align*}
Graf terhubung dengan sebelas simpul bernomor satu sampai sebelas; setiap simpul berderajat genap
Perlu diperhatikan bahwa Teorema 5.13 berlaku untuk graf tanpa gelang yang memperbolehkan sisi rangkap. Euler menggunakan teoremanya untuk menunjukkan bahwa multigraf Königsberg yang ditampilkan dalam Gambar 5.16, dengan setiap daratan sebagai simpul dan setiap jembatan sebagai sisi, bukan graf Euler; karena itu, warga kota tidak dapat menemukan rute yang mereka inginkan. (Perhatikan bahwa dalam Gambar 5.16 terdapat sisi rangkap di antara pasangan simpul yang sama.)
Multigraf dengan empat simpul yang mewakili daratan Königsberg dan tujuh sisi yang mewakili jembatannya, termasuk beberapa sisi rangkap
Sebuah graf \(\GVE\) disebut graf Hamilton jika terdapat barisan \((x_1,x_2,\dots,x_n)\) sedemikian sehingga
-
setiap simpul \(\bfG\) muncul tepat satu kali dalam barisan;
-
\(x_1x_n\) merupakan sisi dari \(\bfG\text{;}\) dan
-
untuk setiap \(i=1,2,\dots,n-1\text{,}\) \(x_ix_{i+1}\) merupakan sisi dalam \(\bfG\text{.}\)
Barisan simpul semacam itu disebut siklus Hamilton.
Graf pertama yang ditampilkan dalam Gambar 5.17 bersifat Euler sekaligus Hamilton. Graf kedua bersifat Hamilton, tetapi tidak Euler.
Dua graf berlabel G dan H; G merupakan graf Euler sekaligus Hamilton, sedangkan H merupakan graf Hamilton tetapi bukan graf Euler
Dalam Gambar 5.18, ditampilkan sebuah graf terkenal yang disebut graf Petersen. Graf ini bukan graf Hamilton.
Graf Petersen dengan sepuluh simpul, digambar sebagai segi lima luar dan bintang bersudut lima di bagian dalam
Berbeda dengan sirkuit Euler, belum ada metode yang diketahui untuk menentukan dengan cepat apakah suatu graf merupakan graf Hamilton. Namun, terdapat sejumlah syarat cukup yang menarik. Berikut salah satu contoh terkenal yang dikemukakan oleh Dirac.
Teorema 5.19.
Jika \(\bfG\) adalah graf dengan \(n\geq 3\) simpul dan setiap simpul dalam \(\bfG\) memiliki setidaknya \(\lceil
\frac{n}{2}\rceil\) tetangga, maka \(\bfG\) merupakan graf Hamilton.
Bukti.
Misalkan teorema tersebut salah, dan misalkan \(n\) adalah bilangan bulat positif terkecil sehingga terdapat graf \(\bfG\) dengan \(n\) simpul, setiap simpul dalam \(\bfG\) memiliki setidaknya \(\lceil n/2\rceil\) tetangga, tetapi tidak terdapat siklus Hamilton dalam \(\bfG\text{.}\) Jelas bahwa \(n\ge4\text{.}\)
Sekarang, misalkan \(t\) adalah bilangan bulat terbesar sehingga \(\bfG\) memiliki lintasan \(P=(x_1,x_2,\dots,x_t)\) pada \(t\) simpul. Jelas bahwa semua tetangga \(x_1\) maupun \(x_t\) muncul pada lintasan ini. Berdasarkan Prinsip Sarang Merpati, terdapat bilangan bulat \(i\) dengan \(1\le i\lt t\) sedemikian sehingga \(x_1x_{i+1}\) dan \(x_{i}x_t\) merupakan sisi dalam \(\bfG\text{.}\) Namun, hal ini menyiratkan bahwa
\begin{equation*}
C=(x_1,x_2,x_3,\dots,x_i,x_t,x_{t-1},x_{t-2},\dots,x_{i+1})
\end{equation*}
merupakan siklus dengan panjang \(t\) dalam \(\bfG\text{.}\) Hal ini mengharuskan \(\lceil n/2\rceil \lt t\lt
n\text{.}\) Namun, jika \(y\) adalah sembarang simpul yang tidak berada pada siklus tersebut, maka \(y\) harus memiliki tetangga pada \(C\text{.}\) Ini menyiratkan bahwa \(\bfG\) memiliki lintasan pada \(t+1\) simpul. Kontradiksi tersebut menyelesaikan bukti.
