Bab 2: Derajat dan Handshaking Lemma
Pada Bab 1 kita telah membangun objek dasar graf sebagai
\[ G=(V,E), \]
dengan \(V\) sebagai himpunan simpul dan \(E\) sebagai himpunan sisi. Kita juga telah melihat bahwa graf adalah bahasa untuk mencatat relasi: simpul mewakili objek, sisi mewakili hubungan.
Bab ini memusatkan perhatian pada salah satu ukuran paling sederhana tetapi paling kuat dalam teori graf: derajat simpul. Dari derajat, kita akan memperoleh hukum dasar yang disebut Handshaking Lemma:
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Artinya, jika kita menjumlahkan derajat semua simpul dalam graf tak berarah, hasilnya selalu dua kali banyak sisi. Lemma ini adalah contoh pertama dari teknik pembuktian yang sangat penting dalam matematika diskret, yaitu penghitungan ganda: menghitung objek yang sama dengan dua cara berbeda.
Secara historis dan konseptual, lemma ini menjadi salah satu fakta paling awal yang muncul dalam hampir semua buku teori graf karena ia menghubungkan struktur lokal, yaitu derajat tiap simpul, dengan struktur global, yaitu jumlah sisi seluruh graf (Diestel, 2017; West, 2001). Dalam statistik jaringan, derajat juga menjadi ringkasan lokal paling dasar untuk memahami seberapa banyak koneksi yang dimiliki suatu unit pengamatan, misalnya jumlah teman, jumlah kolaborator, jumlah transaksi, atau jumlah dependensi langsung dalam suatu sistem (Newman, 2010).
2.1 Mengingat kembali insidensi dan derajat
Kita mulai dari graf tak berarah sederhana. “Tak berarah” berarti sisi tidak memiliki arah. Jika ada sisi antara \(u\) dan \(v\), maka hubungan \(u\) ke \(v\) sama dengan hubungan \(v\) ke \(u\). “Sederhana” berarti tidak ada gelang dan tidak ada sisi rangkap. Gelang adalah sisi dari suatu simpul ke dirinya sendiri, sedangkan sisi rangkap adalah lebih dari satu sisi yang menghubungkan pasangan simpul yang sama. Kelas-kelas graf ini akan dibahas lebih sistematis pada Bab 3.
Untuk saat ini, ambil graf sederhana tak berarah
\[ G=(V,E). \]
Jika \(e=\{u,v\}\in E\), maka kita mengatakan bahwa sisi \(e\) bersisian atau incident dengan simpul \(u\) dan juga bersisian dengan simpul \(v\). Dengan kata lain, \(u\) dan \(v\) adalah dua ujung dari sisi \(e\).
Dua simpul \(u\) dan \(v\) disebut bertetangga atau adjacent jika ada sisi yang menghubungkan keduanya, yaitu jika
\[ \{u,v\}\in E. \]
Sekarang kita dapat mendefinisikan derajat.
Derajat suatu simpul \(v\), ditulis \(\deg(v)\), adalah banyaknya sisi yang bersisian dengan \(v\).
Pada graf sederhana tak berarah, definisi ini sama dengan mengatakan bahwa \(\deg(v)\) adalah banyaknya tetangga dari \(v\).
Sebagai contoh, ambil graf
\[ V=\{A,B,C,D,E\} \]
dan
\[ E=\{\{A,B\},\{A,C\},\{B,D\},\{D,E\}\}. \]
Gambaran relasinya adalah:
- \(A\) terhubung dengan \(B\) dan \(C\);
- \(B\) terhubung dengan \(A\) dan \(D\);
- \(C\) hanya terhubung dengan \(A\);
- \(D\) terhubung dengan \(B\) dan \(E\);
- \(E\) hanya terhubung dengan \(D\).
Maka derajat masing-masing simpul adalah
\[ \deg(A)=2, \]
\[ \deg(B)=2, \]
\[ \deg(C)=1, \]
\[ \deg(D)=2, \]
\[ \deg(E)=1. \]
Jika kita jumlahkan semua derajat, kita mendapat
\[ \deg(A)+\deg(B)+\deg(C)+\deg(D)+\deg(E) =2+2+1+2+1=8. \]
Sementara itu, banyak sisi adalah
\[ |E|=4. \]
Jadi
\[ \sum_{v\in V}\deg(v)=8=2\cdot 4=2|E|. \]
Ini bukan kebetulan. Ini adalah bentuk pertama dari Handshaking Lemma.
2.2 Mengapa jumlah derajat menjadi dua kali jumlah sisi?
Intuisi paling penting adalah sebagai berikut: setiap sisi menyumbang tepat dua terhadap jumlah total derajat.
Misalnya, sisi \(\{A,B\}\) menyumbang:
- \(1\) kepada \(\deg(A)\);
- \(1\) kepada \(\deg(B)\).
Jadi sisi \(\{A,B\}\) menyumbang total \(2\) ketika kita menjumlahkan semua derajat.
Begitu pula sisi \(\{A,C\}\) menyumbang \(1\) ke \(A\) dan \(1\) ke \(C\). Sisi \(\{B,D\}\) menyumbang \(1\) ke \(B\) dan \(1\) ke \(D\). Sisi \(\{D,E\}\) menyumbang \(1\) ke \(D\) dan \(1\) ke \(E\).
Karena setiap sisi dalam graf sederhana tak berarah memiliki dua ujung, setiap sisi selalu dihitung dua kali dalam jumlah derajat: sekali dari ujung pertama, sekali dari ujung kedua.
Itulah alasan informal mengapa
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Dalam bahasa statistik jaringan, jika sisi menyatakan “dua orang pernah berkolaborasi”, maka setiap kolaborasi menambah satu koneksi pada orang pertama dan satu koneksi pada orang kedua. Karena itu, total “jumlah koneksi yang dilaporkan per orang” sama dengan dua kali jumlah pasangan kolaborasi. Prinsip ini sering menjadi pemeriksaan konsistensi sederhana pada data jaringan tak berarah (Newman, 2010).
2.3 Pernyataan formal Handshaking Lemma
Sekarang kita tulis lemma ini secara formal.
Handshaking Lemma.
Jika \(G=(V,E)\) adalah graf sederhana tak berarah berhingga, maka
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Kata “berhingga” penting karena kita sedang menjumlahkan derajat pada himpunan simpul yang jumlahnya berhingga. Dalam teori graf tak berhingga, pernyataan serupa perlu dirumuskan lebih hati-hati karena jumlah tak hingga memerlukan teori kardinalitas atau analisis yang berbeda.
Nama Handshaking Lemma berasal dari analogi jabat tangan. Jika beberapa orang berada dalam satu ruangan dan beberapa pasangan saling berjabat tangan, maka jumlah total “jabat tangan yang dihitung oleh tiap orang” adalah dua kali jumlah jabat tangan aktual. Setiap jabat tangan melibatkan dua orang.
Sebagai contoh, jika ada \(10\) jabat tangan di sebuah ruangan, maka total banyaknya jabat tangan yang dicatat dari sisi semua orang adalah
\[ 2\cdot 10=20. \]
Mungkin satu orang berjabat tangan dengan \(5\) orang, orang lain dengan \(2\), dan seterusnya. Tetapi jika semua angka per orang dijumlahkan, hasilnya pasti \(20\).
2.4 Pembuktian dengan penghitungan ganda
Kita sekarang membuktikan Handshaking Lemma secara matematis.
Teknik yang dipakai disebut penghitungan ganda. Ide dasarnya sederhana: kita memilih suatu himpunan objek, lalu menghitung banyak elemennya dengan dua cara berbeda. Karena objek yang dihitung sama, kedua hasil hitungan harus sama.
Untuk graf \(G=(V,E)\), definisikan himpunan
\[ I=\{(v,e): v\in V,\ e\in E,\ \text{dan } v \text{ bersisian dengan } e\}. \]
Himpunan \(I\) berisi pasangan \((v,e)\), yaitu simpul dan sisi yang saling bersisian.
Contoh kecil membantu. Untuk graf
\[ E=\{\{A,B\},\{A,C\},\{B,D\},\{D,E\}\}, \]
pasangan insidensi adalah
\[ (A,\{A,B\}),\quad (B,\{A,B\}), \]
\[ (A,\{A,C\}),\quad (C,\{A,C\}), \]
\[ (B,\{B,D\}),\quad (D,\{B,D\}), \]
\[ (D,\{D,E\}),\quad (E,\{D,E\}). \]
Ada \(8\) pasangan insidensi.
Sekarang hitung \(|I|\) dengan dua cara.
Pertama, hitung berdasarkan simpul. Untuk satu simpul \(v\), banyak sisi yang bersisian dengannya adalah \(\deg(v)\). Jadi total pasangan insidensi adalah
\[ |I|=\sum_{v\in V}\deg(v). \]
Kedua, hitung berdasarkan sisi. Dalam graf sederhana tak berarah, setiap sisi memiliki tepat dua ujung. Jadi setiap sisi menghasilkan tepat dua pasangan insidensi. Karena ada \(|E|\) sisi, kita mendapat
\[ |I|=2|E|. \]
Karena kedua perhitungan menghitung himpunan \(I\) yang sama, maka
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Ini membuktikan Handshaking Lemma.
Pembuktian ini merupakan pola yang akan sering muncul dalam teori graf. Banyak teorema graf yang tampak “ajaib” sebenarnya berasal dari memilih objek yang tepat untuk dihitung dua kali. Teknik penghitungan ganda adalah salah satu alat dasar dalam matematika diskret dan teori graf (West, 2001).
2.5 Simpul berderajat genap dan ganjil
Setelah mengetahui bahwa jumlah semua derajat adalah bilangan genap, kita memperoleh konsekuensi penting.
Sebuah simpul \(v\) disebut berderajat genap jika \(\deg(v)\) adalah bilangan genap, misalnya \(0,2,4,6\). Simpul \(v\) disebut berderajat ganjil jika \(\deg(v)\) adalah bilangan ganjil, misalnya \(1,3,5\).
Contoh:
- Jika \(\deg(A)=2\), maka \(A\) berderajat genap.
- Jika \(\deg(C)=1\), maka \(C\) berderajat ganjil.
- Jika \(\deg(F)=0\), maka \(F\) berderajat genap.
Perhatikan bahwa simpul terisolasi, yaitu simpul yang tidak memiliki sisi yang bersisian dengannya, memiliki derajat \(0\). Karena \(0\) adalah bilangan genap, simpul terisolasi termasuk simpul berderajat genap.
Pada graf contoh kita,
\[ \deg(A)=2,\quad \deg(B)=2,\quad \deg(C)=1,\quad \deg(D)=2,\quad \deg(E)=1. \]
Simpul berderajat ganjil adalah \(C\) dan \(E\). Jumlahnya \(2\), yaitu bilangan genap.
Ini juga bukan kebetulan.
2.6 Konsekuensi: jumlah simpul berderajat ganjil selalu genap
Teorema.
Dalam setiap graf sederhana tak berarah berhingga, jumlah simpul berderajat ganjil selalu genap.
Hasil ini adalah konsekuensi langsung dari Handshaking Lemma. Pernyataan ini sering dianggap bagian dari Handshaking Lemma itu sendiri dalam banyak pengantar teori graf (Diestel, 2017; West, 2001).
Mari kita buktikan.
Misalkan \(O\) adalah himpunan simpul berderajat ganjil, dan \(R\) adalah himpunan simpul berderajat genap. Maka \(V\) terbagi menjadi dua bagian:
\[ V=O\cup R, \]
dengan \(O\cap R=\varnothing\).
Jumlah semua derajat dapat ditulis sebagai
\[ \sum_{v\in V}\deg(v) = \sum_{v\in O}\deg(v) + \sum_{v\in R}\deg(v). \]
Dari Handshaking Lemma,
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Karena \(2|E|\) adalah bilangan genap, maka jumlah semua derajat adalah genap.
Sekarang perhatikan bagian kanan. Jumlah derajat simpul-simpul dalam \(R\) adalah jumlah bilangan-bilangan genap, sehingga hasilnya genap. Maka agar jumlah total tetap genap, jumlah derajat simpul-simpul dalam \(O\) juga harus genap.
Tetapi setiap simpul dalam \(O\) memiliki derajat ganjil. Jumlah dari beberapa bilangan ganjil akan genap jika dan hanya jika banyaknya bilangan ganjil yang dijumlahkan adalah genap. Jadi banyak simpul dalam \(O\) harus genap.
Dengan kata lain,
\[ |O| \text{ genap}. \]
Maka jumlah simpul berderajat ganjil selalu genap.
Contoh sederhana:
\[ (2,2,1,2,1) \]
adalah daftar derajat dari graf contoh sebelumnya. Bilangan ganjil muncul dua kali, yaitu \(1\) dan \(1\). Jumlah simpul berderajat ganjil adalah \(2\), genap.
Sebaliknya, daftar derajat
\[ (3,2,2,1,1) \]
tidak mungkin menjadi daftar derajat graf tak berarah mana pun, karena jumlah derajatnya
\[ 3+2+2+1+1=9, \]
yaitu ganjil. Ini melanggar Handshaking Lemma, sebab jumlah derajat seharusnya sama dengan \(2|E|\), yang pasti genap.
2.7 Derajat rata-rata
Handshaking Lemma juga memberi hubungan langsung antara banyak simpul, banyak sisi, dan derajat rata-rata.
Misalkan graf \(G=(V,E)\) memiliki
\[ |V|=n \]
simpul dan
\[ |E|=m \]
sisi. Derajat rata-rata didefinisikan sebagai
\[ \bar d = \frac{1}{n}\sum_{v\in V}\deg(v). \]
Dengan Handshaking Lemma,
\[ \sum_{v\in V}\deg(v)=2m. \]
Maka
\[ \bar d=\frac{2m}{n}. \]
Jadi derajat rata-rata suatu graf tak berarah sederhana adalah dua kali banyak sisi dibagi banyak simpul.
Contoh: jika suatu jaringan kolaborasi memiliki \(n=100\) peneliti dan \(m=250\) pasangan kolaborasi, maka derajat rata-ratanya adalah
\[ \bar d=\frac{2\cdot 250}{100}=5. \]
Artinya, rata-rata tiap peneliti memiliki \(5\) kolaborator dalam jaringan tersebut. Tentu saja ini tidak berarti semua peneliti memiliki tepat \(5\) kolaborator. Bisa saja ada peneliti dengan derajat \(20\), banyak peneliti dengan derajat \(1\), dan beberapa peneliti dengan derajat \(0\). Rata-rata hanya merangkum total koneksi per simpul.
Dalam statistik jaringan, derajat rata-rata adalah salah satu ringkasan global paling dasar. Namun interpretasinya harus hati-hati: dua graf dapat memiliki derajat rata-rata yang sama tetapi struktur yang sangat berbeda. Misalnya, satu jaringan dapat memiliki distribusi derajat yang relatif merata, sedangkan jaringan lain dapat memiliki beberapa simpul berderajat sangat tinggi dan banyak simpul berderajat rendah. Perbedaan ini menjadi penting dalam analisis jaringan sosial, epidemiologi jaringan, dan model graf acak (Newman, 2010).
2.8 Contoh: graf lengkap dan graf kosong
Dua keluarga graf dasar membantu memperkuat pemahaman kita tentang derajat.
Pertama, graf kosong pada \(n\) simpul adalah graf dengan \(n\) simpul dan tanpa sisi. Biasanya graf ini dapat ditulis sebagai
\[ E_n \]
atau cukup disebut graf tanpa sisi pada \(n\) simpul, bergantung konvensi notasi yang dipakai.
Jika tidak ada sisi, maka setiap simpul memiliki derajat \(0\). Jadi
\[ \sum_{v\in V}\deg(v)=0. \]
Karena
\[ |E|=0, \]
Handshaking Lemma memberi
\[ 2|E|=2\cdot 0=0. \]
Cocok.
Kedua, graf lengkap pada \(n\) simpul, ditulis \(K_n\), adalah graf sederhana yang setiap pasangan simpul berbeda dihubungkan oleh tepat satu sisi. Dalam \(K_n\), setiap simpul bertetangga dengan semua simpul lain. Karena ada \(n-1\) simpul lain, maka
\[ \deg(v)=n-1 \]
untuk setiap \(v\in V\).
Jumlah derajatnya adalah
\[ \sum_{v\in V}\deg(v)=n(n-1). \]
Di sisi lain, banyak sisi dalam \(K_n\) adalah banyak pasangan tak berurutan dari \(n\) simpul, yaitu
\[ |E|=\binom{n}{2}=\frac{n(n-1)}{2}. \]
Maka
\[ 2|E|=2\cdot \frac{n(n-1)}{2}=n(n-1). \]
Sekali lagi cocok dengan Handshaking Lemma.
Sebagai contoh, dalam \(K_5\), setiap simpul memiliki derajat \(4\). Jumlah derajat adalah
\[ 5\cdot 4=20. \]
Banyak sisi adalah
\[ \binom{5}{2}=10. \]
Maka
\[ 2|E|=20. \]
2.9 Daftar derajat dan pemeriksaan awal konsistensi
Dalam banyak aplikasi statistik, kita sering mulai bukan dari gambar graf, tetapi dari data. Misalnya, kita mempunyai daftar banyak kontak tiap orang, banyak kolaborator tiap peneliti, atau banyak wilayah tetangga tiap kabupaten.
Jika \(G\) memiliki simpul
\[ v_1,v_2,\ldots,v_n, \]
maka daftar derajat atau degree sequence adalah barisan
\[ (\deg(v_1),\deg(v_2),\ldots,\deg(v_n)). \]
Kadang daftar ini diurutkan dari terbesar ke terkecil agar lebih mudah dianalisis.
Handshaking Lemma memberi syarat perlu bagi suatu barisan bilangan bulat tak negatif untuk menjadi daftar derajat graf tak berarah: jumlah seluruh elemennya harus genap.
Contoh:
\[ (2,2,1,2,1) \]
memiliki jumlah
\[ 2+2+1+2+1=8. \]
Karena jumlahnya genap, barisan ini tidak langsung ditolak oleh Handshaking Lemma. Memang barisan ini berasal dari graf contoh kita.
Sebaliknya,
\[ (4,3,2,2,2) \]
memiliki jumlah
\[ 4+3+2+2+2=13. \]
Karena jumlahnya ganjil, barisan ini mustahil menjadi daftar derajat graf tak berarah sederhana. Alasannya, jika barisan itu benar berasal dari suatu graf, maka jumlahnya harus sama dengan \(2|E|\), yang pasti genap.
Namun perlu diperhatikan: jumlah genap belum cukup untuk menjamin bahwa suatu barisan adalah daftar derajat graf sederhana. Misalnya, barisan
\[ (3,3,3,1) \]
memiliki jumlah
\[ 10, \]
yang genap. Tetapi barisan ini tidak dapat direalisasikan sebagai graf sederhana pada \(4\) simpul. Jika tiga simpul memiliki derajat \(3\), maka masing-masing harus terhubung ke semua simpul lainnya, termasuk simpul keempat. Akibatnya simpul keempat juga harus memiliki derajat setidaknya \(3\), bukan \(1\). Jadi Handshaking Lemma memberi syarat perlu, bukan syarat cukup. Kriteria lengkap untuk menentukan apakah suatu barisan adalah daftar derajat graf sederhana akan berkaitan dengan hasil seperti algoritma Havel–Hakimi atau teorema Erdős–Gallai, yang berada di luar fokus bab ini dan akan lebih relevan ketika kita membahas algoritma dan graf acak.
Dalam praktik data, pemeriksaan paritas tetap sangat berguna. Jika seseorang memberikan data jaringan tak berarah dengan total derajat ganjil, maka pasti ada kesalahan: mungkin ada sisi yang hanya dicatat dari satu arah, ada duplikasi yang tidak konsisten, atau ada observasi yang hilang.
2.10 Catatan tentang gelang, multigraf, dan graf berarah
Bab ini berfokus pada graf sederhana tak berarah. Namun agar tidak terjadi kebingungan ketika nanti kita bertemu kelas graf lain, kita perlu memberi catatan singkat.
Pada multigraf, dua simpul boleh dihubungkan oleh lebih dari satu sisi. Pada graf dengan gelang, suatu sisi boleh menghubungkan simpul ke dirinya sendiri. Konvensi standar dalam teori graf tak berarah adalah: sebuah gelang menyumbang \(2\) terhadap derajat simpulnya, karena gelang memiliki dua ujung yang sama-sama berada pada simpul tersebut (Diestel, 2017; West, 2001).
Dengan konvensi ini, Handshaking Lemma tetap benar untuk multigraf tak berarah berhingga jika setiap gelang dihitung dua terhadap derajat.
Contoh: misalkan ada satu simpul \(A\) dengan satu gelang \(\{A,A\}\). Maka banyak sisi adalah
\[ |E|=1. \]
Gelang tersebut menyumbang \(2\) terhadap derajat \(A\), sehingga
\[ \deg(A)=2. \]
Maka
\[ \sum_{v\in V}\deg(v)=2=2|E|. \]
Untuk graf berarah atau digraf, setiap sisi memiliki arah, misalnya dari \(u\) ke \(v\). Dalam digraf, kita membedakan:
- derajat keluar \(d^+(v)\), yaitu banyak sisi yang keluar dari \(v\);
- derajat masuk \(d^-(v)\), yaitu banyak sisi yang masuk ke \(v\).
Pada digraf berhingga, jumlah seluruh derajat keluar sama dengan jumlah seluruh derajat masuk, dan keduanya sama dengan banyak sisi berarah:
\[ \sum_{v\in V} d^+(v)=|E|=\sum_{v\in V} d^-(v). \]
Alasannya mirip dengan Handshaking Lemma: setiap sisi berarah memiliki tepat satu pangkal dan tepat satu tujuan. Maka setiap sisi menyumbang \(1\) ke total derajat keluar dan \(1\) ke total derajat masuk. Struktur graf berarah akan dibahas lebih lengkap pada Bab 8.
2.11 Handshaking Lemma sebagai alat pembuktian
Handshaking Lemma bukan hanya rumus untuk menghitung. Ia adalah alat pembuktian.
Sebagai contoh, kita dapat membuktikan klaim berikut.
Klaim. Tidak ada graf sederhana tak berarah dengan tepat satu simpul berderajat ganjil.
Bukti.
Dari konsekuensi Handshaking Lemma, jumlah simpul berderajat ganjil dalam graf tak berarah berhingga harus genap. Angka \(1\) bukan genap. Jadi graf seperti itu tidak mungkin ada.
Contoh lain:
Klaim. Jika sebuah graf memiliki \(7\) simpul dan \(11\) sisi, maka derajat rata-ratanya adalah \(\frac{22}{7}\).
Bukti.
Dengan Handshaking Lemma,
\[ \sum_{v\in V}\deg(v)=2|E|=2\cdot 11=22. \]
Karena ada \(7\) simpul, derajat rata-rata adalah
\[ \bar d=\frac{22}{7}. \]
Klaim ini sederhana, tetapi pola pikirnya penting: kita tidak perlu mengetahui bentuk graf secara lengkap untuk mengetahui total derajatnya. Informasi global \(|E|\) sudah cukup untuk menentukan jumlah semua derajat.
Dalam konteks statistik, ini berguna ketika data jaringan disimpan sebagai edge list. Jika kita mengetahui jumlah sisi, kita langsung mengetahui total derajat. Sebaliknya, jika data disimpan sebagai daftar derajat, kita dapat memperoleh jumlah sisi dengan
\[ |E|=\frac{1}{2}\sum_{v\in V}\deg(v), \]
selama grafnya tak berarah dan setiap sisi dihitung dengan benar.
2.12 Kesalahan umum
Ada beberapa kesalahan yang sering muncul saat pertama kali mempelajari derajat dan Handshaking Lemma.
Pertama, mengira bahwa jumlah derajat sama dengan jumlah sisi. Ini keliru. Pada graf tak berarah, setiap sisi menyentuh dua simpul, sehingga setiap sisi dihitung dua kali dalam jumlah derajat. Yang benar adalah
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Kedua, melupakan simpul berderajat nol. Jika suatu simpul tidak memiliki sisi, derajatnya adalah \(0\), bukan “tidak terdefinisi”. Simpul tersebut tetap anggota \(V\), sehingga tetap masuk dalam perhitungan jumlah derajat.
Ketiga, mengira bahwa jumlah derajat genap cukup untuk menjamin sebuah daftar derajat dapat membentuk graf sederhana. Seperti kita lihat pada contoh \((3,3,3,1)\), jumlah genap hanya syarat perlu.
Keempat, mencampur graf tak berarah dan graf berarah. Pada graf tak berarah, kita memakai derajat \(\deg(v)\). Pada graf berarah, kita perlu membedakan derajat masuk dan derajat keluar. Rumusnya berbeda, meskipun idenya sama-sama berasal dari menghitung kontribusi sisi.
2.13 Ringkasan bab
Bab ini membangun salah satu fondasi terpenting teori graf.
Untuk graf sederhana tak berarah berhingga \(G=(V,E)\), derajat simpul \(v\), yaitu \(\deg(v)\), adalah banyaknya sisi yang bersisian dengan \(v\). Jumlah seluruh derajat selalu sama dengan dua kali banyak sisi:
\[ \sum_{v\in V}\deg(v)=2|E|. \]
Inilah Handshaking Lemma.
Bukti utamanya memakai penghitungan ganda. Kita menghitung pasangan insidensi \((v,e)\) dengan dua cara: berdasarkan simpul dan berdasarkan sisi. Berdasarkan simpul, banyaknya adalah \(\sum_{v\in V}\deg(v)\). Berdasarkan sisi, banyaknya adalah \(2|E|\). Karena keduanya menghitung objek yang sama, keduanya sama.
Konsekuensi paling penting adalah: jumlah simpul berderajat ganjil selalu genap. Hasil ini sering menjadi alat cepat untuk membuktikan kemustahilan suatu graf atau memeriksa konsistensi data jaringan.
Derajat rata-rata juga langsung mengikuti:
\[ \bar d=\frac{2|E|}{|V|}. \]
Rumus ini akan muncul kembali dalam pembahasan graf acak, statistik jaringan, distribusi derajat, dan model jaringan.
2.14 Latihan
- Diberikan graf dengan
\[ V=\{1,2,3,4,5,6\} \]
dan
\[ E=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{4,5\}\}. \]
Hitung derajat setiap simpul, jumlah semua derajat, dan periksa Handshaking Lemma.
- Apakah mungkin ada graf tak berarah sederhana dengan daftar derajat
\[ (4,4,3,2,1)? \]
Jelaskan menggunakan Handshaking Lemma.
-
Apakah mungkin ada graf tak berarah dengan tepat \(9\) simpul berderajat ganjil? Buktikan jawaban Anda.
-
Suatu jaringan kolaborasi memiliki \(75\) peneliti dan \(180\) pasangan kolaborasi. Berapa derajat rata-ratanya?
-
Sebuah data jaringan tak berarah mencatat derajat simpul sebagai berikut:
\[ (5,4,4,3,2,2,1). \]
Apakah data ini dapat langsung dianggap konsisten dengan graf tak berarah? Jika tidak, apa masalahnya?
- Buktikan dengan penghitungan ganda bahwa dalam graf berarah berhingga,
\[ \sum_{v\in V} d^+(v)=\sum_{v\in V} d^-(v). \]
-
Berikan contoh dua graf berbeda yang memiliki jumlah simpul sama, jumlah sisi sama, dan derajat rata-rata sama, tetapi bentuk relasinya berbeda.
-
Misalkan suatu graf sederhana memiliki \(n\) simpul dan setiap simpul berderajat \(k\). Graf seperti ini disebut \(k\)-regular. Gunakan Handshaking Lemma untuk menunjukkan bahwa \(nk\) harus genap.
References
Diestel, R. (2017). Graph Theory (5th ed.). Springer.
Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.