Teorema 5.9.
Misalkan \(\deg_\bfG(v)\) menyatakan derajat simpul \(v\) dalam graf \(\GVE\text{.}\) Maka
\begin{equation}
\sum_{v\in V}\deg_\bfG(v) = 2|E|\text{.}\tag{5.1.1}
\end{equation}
Subbab 5.1 Notasi dan Terminologi Dasar untuk Graf
Sebuah graf \(\bfG\) adalah pasangan \((V,E)\text{,}\) dengan \(V\) suatu himpunan (hampir selalu berhingga) dan \(E\) suatu himpunan yang anggotanya merupakan subhimpunan beranggota \(2\) dari \(V\text{.}\) Anggota \(V\) disebut simpul, sedangkan anggota \(E\) disebut sisi. Kita menyebut \(V\) sebagai himpunan simpul dari \(\bfG\) dan \(E\) sebagai himpunan sisi. Untuk memudahkan penulisan, sisi \(\{x,y\}\) lazim disingkat menjadi \(xy\text{.}\) Namun, ingatlah bahwa \(xy\in E\) bermakna persis sama dengan \(yx\in E\text{.}\) Jika \(x\) dan \(y\) adalah dua simpul berbeda dalam \(V\text{,}\) maka \(x\) dan \(y\) disebut bertetangga apabila \(xy\in E\text{;}\) jika tidak, keduanya disebut tidak bertetangga. Sisi \(xy\) dikatakan bersisian dengan simpul \(x\) dan \(y\text{.}\)
Sebagai contoh, kita dapat mendefinisikan graf \(\GVE\) dengan himpunan simpul \(V=\{a,b,c,d,e\}\) dan himpunan sisi \(E=\{\{a,b\},\{c,d\},\{a,d\}\}\text{.}\) Perhatikan bahwa tidak ada sisi yang bersisian dengan \(e\text{;}\) hal ini sepenuhnya diperbolehkan oleh definisi kita. Graf sangat lazim disajikan melalui visualisasi berupa satu titik untuk setiap simpul dan satu garis yang menghubungkan dua simpul apabila keduanya bertetangga. Graf \(\bfG\) yang baru saja kita definisikan ditampilkan pada Gambar 5.1. Penting untuk diingat bahwa meskipun gambar graf merupakan alat bantu yang berguna, gambar tersebut bukanlah graf itu sendiri. Kita dapat menggambar \(\bfG\) dengan beberapa cara berbeda tanpa mengubah grafnya.
Graf dengan \(5\) simpul, yaitu a, b, c, d, dan e; sisinya menghubungkan a dengan b, c dengan d, serta a dengan d, sedangkan e merupakan simpul terisolasi.
Seperti yang sering terjadi dalam sains dan matematika, para penulis menggunakan notasi dan terminologi graf yang sedikit berbeda. Sebagai contoh, sebagian penulis memakai istilah nodus dan busur sebagai pengganti simpul dan sisi. Penulis lain menyebut simpul sebagai titik dan dalam hal ini sering menyebut sisi sebagai garis. Dalam buku ini kami berusaha konsisten memakai istilah simpul dan sisi, meskipun sesekali kami mungkin menyebut simpul sebagai titik. Selain itu, mengikuti kebiasaan banyak penulis lain, simpul-simpul yang bertetangga juga akan kami sebut tetangga. Kami juga menggunakan terminologi yang kurang lebih baku bahwa lingkungan dari simpul \(x\) adalah himpunan semua simpul yang bertetangga dengan \(x\text{.}\) Jadi, pada graf \(\bfG\) dalam Gambar 5.1, simpul \(d\) dan \(a\) bertetangga; lingkungan \(d\) adalah \(\{a,c\}\text{,}\) sedangkan lingkungan \(e\) adalah himpunan kosong. Selanjutnya, derajat dari simpul \(v\) dalam graf \(\bfG\text{,}\) yang dinotasikan dengan \(\deg_\bfG(v)\text{,}\) adalah banyaknya simpul dalam lingkungannya, atau secara ekuivalen, banyaknya sisi yang bersisian dengannya. Sebagai contoh, kita memperoleh \(\deg_\bfG(d)=\deg_\bfG(a)=2\text{,}\) \(\deg_\bfG(c)=\deg_\bfG(b)=1\text{,}\) dan \(\deg_\bfG(e)=0\text{.}\) Jika graf yang sedang dibahas sudah jelas dari konteks, subskrip lazim dihilangkan sehingga cukup ditulis \(\deg(v)\) untuk derajat \(v\text{.}\)
Jika \(\GVE\) dan \(\HWF\) adalah graf, kita menyebut \(\bfH\) sebagai subgraf dari \(\bfG\) apabila \(W\subseteq V\) dan \(F\subseteq E\text{.}\) Kita menyebut \(\bfH\) sebagai subgraf terinduksi apabila \(W\subseteq V\) dan \(F=\{xy\in E: x,y\in W\}\text{.}\) Dengan kata lain, subgraf terinduksi sepenuhnya ditentukan oleh himpunan simpulnya dan graf asal \(\bfG\text{.}\) Kita menyebut \(\bfH\) sebagai subgraf merentang apabila \(W=V\text{.}\) Pada Gambar 5.2, ditampilkan sebuah graf, sebuah subgraf, dan sebuah subgraf terinduksi. Kedua subgraf tersebut bukan subgraf merentang.
Tiga diagram berlabel yang saling berkaitan: graf asal pada kiri, subgraf pada tengah, dan subgraf terinduksi pada tujuh simpul a, b, c, d, e, h, dan i pada kanan.
Graf \(\GVE\) disebut graf lengkap apabila \(xy\) merupakan sisi dalam \(\bfG\) untuk setiap pasangan berbeda \(x,y\in
V\text{.}\) Sebaliknya, \(\bfG\) disebut graf bebas apabila \(xy\not\in E\) untuk setiap pasangan berbeda \(x,y\in V\text{.}\) Graf lengkap dengan \(n\) simpul lazim dinotasikan dengan \(\bfK_n\) , sedangkan graf bebas dengan \(n\) simpul dinotasikan dengan \(\bfI_n\). Pada Gambar 5.3, ditampilkan graf-graf lengkap dengan paling banyak \(5\) simpul.
Lima graf lengkap berlabel K satu sampai K lima: berturut-turut satu simpul tunggal, satu sisi, segitiga, persegi dengan kedua diagonal, serta pentagon dengan semua diagonal.
Urutan \((x_1,x_2,\dots,x_n)\) yang terdiri atas simpul-simpul dalam graf \(\GVE\) disebut jalan apabila \(x_ix_{i+1}\) merupakan sisi untuk setiap \(i=1,2,\dots,n-1\text{.}\) Perhatikan bahwa simpul-simpul dalam suatu jalan tidak harus berbeda. Sebaliknya, jika semua simpulnya berbeda, urutan tersebut disebut lintasan. Untuk menegaskan titik awal dan akhirnya, kita sering mengatakan bahwa urutan \((x_1,x_2,\dots,x_n)\) dari simpul-simpul berbeda merupakan lintasan dari \(x_1\) ke \(x_n\) dalam \(\bfG\text{.}\) Demikian pula, apabila \(n\ge3\text{,}\) lintasan \((x_1,x_2,\dots,x_n)\) yang terdiri atas \(n\) simpul berbeda disebut siklus jika \(x_1x_n\) juga merupakan sisi dalam \(\bfG\text{.}\) Lintasan dengan \(n\) simpul lazim dinotasikan dengan \(\bfP_n\), sedangkan \(\bfC_n\) menyatakan siklus dengan \(n\) simpul. Panjang suatu lintasan atau siklus adalah banyaknya sisi yang dikandungnya. Jadi, panjang \(\bfP_n\) adalah \(n-1\) dan panjang \(\bfC_n\) adalah \(n\text{.}\) Pada Gambar 5.4, ditampilkan lintasan-lintasan dengan panjang paling besar \(4\text{,}\) dan pada Gambar 5.5, ditampilkan siklus-siklus dengan panjang paling besar \(5\text{.}\)
Lima graf lintasan, dari P satu sampai P lima, yang berturut-turut memiliki satu hingga lima simpul dan panjang nol hingga empat.
Tiga graf siklus: C tiga berbentuk segitiga, C empat berbentuk persegi, dan C lima berbentuk pentagon.
Jika \(\GVE\) dan \(\HWF\) adalah graf, kita menyatakan bahwa \(\bfG\) isomorfik dengan \(\bfH\) dan menulis \(\bfG\cong\bfH\) apabila terdapat bijeksi \(f:V\bijection W\) sedemikian sehingga \(x\) bertetangga dengan \(y\) dalam \(\bfG\) jika dan hanya jika \(f(x)\) bertetangga dengan \(f(y)\) dalam \(\bfH\text{.}\) Para penulis juga sering mengatakan bahwa \(\bfG\) “mengandung” \(\bfH\) apabila terdapat subgraf dari \(\bfG\) yang isomorfik dengan \(\bfH\text{.}\) Secara khusus, \(\bfG\) lazim dikatakan mengandung siklus \(\bfC_n\) (demikian pula untuk \(\bfP_n\) dan \(\bfK_n\)) apabila \(\bfG\) mengandung subgraf yang isomorfik dengan \(\bfC_n\text{.}\) Graf-graf pada Gambar 5.6 bersifat isomorfik. Salah satu isomorfisme antara kedua graf tersebut diberikan oleh
\begin{equation*}
f(a)=5,\quad f(b) = 3, \quad f(c) = 1,\quad f(d) = 6,\quad f(e)=2,\quad f(h)=4.
\end{equation*}
Dua graf dengan enam simpul yang digambar dan diberi label secara berbeda, tetapi memiliki pola ketetanggaan yang sama sesuai pemetaan pada teks.
Sebaliknya, graf-graf yang ditampilkan pada Gambar 5.7 tidak isomorfik, meskipun memiliki banyak simpul dan banyak sisi yang sama. Dapatkah Anda menjelaskan alasannya?
Dua graf yang masing-masing memiliki enam simpul dan enam sisi; graf kiri memiliki sebuah simpul berderajat empat, sedangkan graf kanan tidak, sehingga keduanya tidak isomorfik.
Graf \(\bfG\) disebut terhubung apabila terdapat lintasan dari \(x\) ke \(y\) dalam \(\bfG\) untuk setiap \(x,y\in V\text{;}\) jika tidak, \(\bfG\) disebut tak terhubung. Graf pada Gambar 5.1 tak terhubung (salah satu alasan yang memadai ialah tidak terdapat lintasan dari \(e\) ke \(c\)), sedangkan kedua graf pada Gambar 5.6 terhubung. Jika \(\bfG\) tak terhubung, subgraf terhubung maksimal dari \(\bfG\) disebut komponen. Artinya, subgraf \(\bfH\) dari \(\bfG\) merupakan komponen dari \(\bfG\) apabila tidak terdapat subgraf terhubung \(\bfH'\) dari \(\bfG\) yang memuat \(\bfH\) sebagai subgraf sejati dari \(\bfH'\text{.}\)
Graf disebut tanpa siklus apabila tidak mengandung siklus dengan tiga simpul atau lebih. Graf tanpa siklus juga disebut hutan. Graf terhubung yang tidak memiliki siklus disebut pohon. Jika \(\GVE\) merupakan graf terhubung, subgraf \(\HWF\) dari \(\bfG\) disebut pohon merentang apabila \(\bfH\) sekaligus merupakan subgraf merentang dari \(\bfG\) dan sebuah pohon. Pada Gambar 5.8, ditampilkan sebuah graf beserta salah satu pohon merentangnya. Topik pohon merentang akan dibahas kembali dalam Bab 12.
Dua diagram pada himpunan sepuluh simpul berlabel yang sama: graf asal di kiri dan sebuah subgraf terhubung tanpa siklus di kanan yang merupakan pohon merentangnya.
Teorema berikut sangat mendasar, dan sebagian penulis menyebutnya “teorema pertama teori graf”. Meskipun demikian, hasil dasar ini ternyata dapat sangat berguna.
Bukti.
Kita menghitung berapa kali sebuah sisi \(e=vw\in E\) menyumbang pada masing-masing ruas (5.1.1). Suku \(\deg_\bfG(v)\) dan \(\deg_\bfG(w)\) pada ruas kiri masing-masing menghitung \(e\) satu kali, sehingga \(e\) dihitung dua kali pada ruas tersebut. Pada ruas kanan, \(e\) juga jelas dihitung dua kali. Oleh karena itu, kesamaan yang dinyatakan berlaku.
Akibat 5.10.
Dalam setiap graf, banyaknya simpul berderajat ganjil selalu genap.
Kita akan membahas pohon kembali nanti, tetapi sebelum melanjutkan, mari kita buktikan sebuah proposisi dasar mengenai pohon. Pertama, daun dalam pohon \(\bfT\) adalah simpul \(v\) dengan \(\deg_\bfT(v)=1\text{.}\)
Proposisi 5.11.
Setiap pohon dengan \(n\geq 2\) simpul memiliki sekurang-kurangnya dua daun.
Bukti.
Bukti ini menggunakan induksi pada \(n\text{.}\) Untuk \(n=2\text{,}\) hanya ada satu pohon, yang isomorfik dengan \(\bfK_2\text{.}\) Kedua simpul dalam graf ini merupakan daun, sehingga proposisi berlaku untuk \(n=2\text{.}\) Sekarang, misalkan untuk suatu bilangan bulat \(m\geq 2\text{,}\) setiap pohon dengan paling banyak \(m\) simpul memiliki sekurang-kurangnya dua daun, dan misalkan \(\bfT=(V,E)\) merupakan pohon dengan \(m+1\) simpul. Pilih sebuah sisi \(e\in E\text{,}\) lalu bentuk graf baru \(\bfT'=(V',E')\) dengan menghapus \(e\) dari \(\bfT\text{.}\) Jadi, \(V'=V\) dan \(E'=E-\{e\}\text{.}\) Karena \(\bfT'\) tidak memuat lintasan dari salah satu ujung \(e\) ke ujung lainnya, \(\bfT'\) tak terhubung. Namun, menghapus sebuah sisi tidak dapat menciptakan siklus, sehingga \(\bfT'\) merupakan hutan. Lebih lanjut, graf tersebut memiliki tepat dua komponen, dan masing-masing merupakan pohon dengan paling banyak \(m\) simpul. Jika setiap komponen memiliki sekurang-kurangnya dua simpul, maka menurut hipotesis induksi, masing-masing memiliki sekurang-kurangnya dua daun. Dalam kasus terburuk, dua di antara daun-daun ini merupakan kedua ujung \(e\text{,}\) sehingga sekurang-kurangnya dua simpul lainnya tetap menjadi daun dalam \(\bfT\text{.}\) Jika setiap komponen dari \(\bfT'\) hanya memiliki satu simpul, maka \(\bfT\cong \bfK_2\text{,}\) yang memiliki dua daun. Jika tepat satu komponen hanya memiliki satu simpul, simpul itu pasti merupakan daun dalam \(\bfT\text{.}\) Dengan menerapkan hipotesis induksi pada komponen lainnya, diperoleh satu daun kedua dalam \(\bfT\text{.}\)
