Secara informal, graf (graph) adalah struktur diskret yang disusun dari himpunan simpul dan himpunan sisi. Sebagai bagian dari “keluarga besar” matematika diskret, graf memiliki peran sentral dalam kemajuan teknologi meskipun baru ditemukan pada abad ke-18, diawali oleh masalah Tujuh Jembatan Königsberg. Leonhard Euler (1707–1783) menyelesaikan masalah tersebut dengan menggunakan model yang selanjutnya dikenal sebagai graf.
Artikel tentang Graf
Berikut ini merupakan beberapa artikel yang tersedia, berkaitan dengan materi graf.
Materi, Soal, dan Pembahasan – Operasi pada Graf dan Konsep Subgraf
Materi, Soal, dan Pembahasan – Representasi Graf dan Isomorfisme Graf
Definisi: Graf
Beberapa penulis mendefinisikan graf boleh memuat himpunan simpul yang kosong, begitu juga sisinya. Dengan kata lain, $V = \emptyset$ dan $E = \emptyset.$ Karena ada perbedaan definisi seperti itu, sebaiknya kita mencermati dengan baik bagaimana suatu terminologi didefinisikan pada literatur yang digunakan.
Catat bahwa $V$ dari graf $G$ bisa jadi memuat takhingga banyaknya simpul. Graf yang simpulnya sebanyak takhingga dinamakan graf takhingga (infinite graph). Sebaliknya, jika simpulnya berhingga, graf itu disebut sebagai graf hingga (finite graph).
Simpul pada graf biasanya ditandai dengan huruf $a, b, c, \cdots$ (dengan/tanpa melibatkan indeks, seperti $v_1, v_2, \cdots$) atau bilangan $1, 2, 3, \cdots$ atau keduanya. Sisi yang menghubungkan simpul $a$ dan $b$ umumnya dituliskan dalam notasi himpunan $\{a, b\}.$ Beberapa literatur menuliskannya sebagai $ab$ atau $(a, b).$ Lebih lanjut, jika $e_1$ merupakan sisi yang menghubungkan simpul $a$ dan $b,$ beberapa literatur menuliskannya sebagai $e = (a, b).$ Simpul $a$ dan $b$ berturut-turut disebut sebagai simpul awal (initial vertex) dan simpul akhir (terminal vertex) dari sisi $e.$
Berikut ini merupakan contoh graf yang memuat $7$ simpul (berordo $7$) dan $7$ sisi (berukuran $7$) yang dimodelkan seperti berikut.
Graf dikelompokkan menjadi berbagai jenis tergantung sudut pandang pengelompokannya, misalnya dari ada tidaknya sisi ganda atau gelang, banyak simpul, ada tidaknya arah pada sisi, dan lain-lain. Kita akan memberikan terminologi terkait graf dan jenis-jenis graf sebagai berikut.
- Sisi rangkap atau sisi ganda (multiple edge, parallel edge, atau multi-edge) adalah dua atau lebih sisi yang menghubungkan dua simpul yang sama.
- Gelang atau kalang (loop) adalah sisi yang menghubungkan satu simpul saja.
- Graf sederhana (simple graph) adalah graf yang tidak memuat sisi rangkap maupun gelang.
- Graf taksederhana (unsimple graph) adalah graf yang memuat sisi rangkap atau gelang.
- Multigraf (multigraph) adalah graf taksederhana yang diperbolehkan memuat sisi rangkap, tetapi tidak boleh memuat gelang.
- Graf semu (pseudograph) adalah graf taksederhana yang diperbolehkan memuat sisi rangkap maupun gelang.
- Graf berarah (directed graph atau digraph) adalah graf yang sisinya memiliki arah (orientasi).
- Graf tak-berarah (undirected graph) adalah graf yang sisinya tidak memiliki arah (orientasi).
- Graf berarah sederhana (simple directed graph) adalah graf sederhana yang sisinya memiliki arah (orientasi).
- Multigraf berarah (directed multigraph) adalah graf semu yang sisinya memiliki arah (orientasi).
- Graf campuran (mixed graph) adalah graf semu yang sisinya boleh berarah ataupun tidak.
- Graf trivial (trivial graph) adalah graf yang hanya memuat satu simpul tunggal tanpa ada sisi.
- Graf kosong (null/empty graph) adalah graf yang hanya memuat satu atau lebih simpul tanpa ada sisi.
Berikut merupakan contoh model graf berarah.
Jenis-jenis graf berdasarkan ada tidaknya sisi berarah, sisi rangkap, dan gelang dirangkum dalam tabel berikut.
Banyak terminologi yang muncul ketika berbicara tentang graf. Berikut ini merupakan terminologi yang mendeskripsikan simpul dan sisi pada graf tak-berarah.
Definisi: Bertetangga dan Bersisian
Definisi: Lingkungan
Berdasarkan model graf di atas, diketahui $N(v_1) = \{v_2, v_5\},$ artinya $v_1$ bertetangga dengan $v_2$ dan $v_5.$ Dapat dilihat bahwa setiap simpul pada graf tersebut memiliki tepat $2$ tetangga. Misalkan $A = \{v_1, v_5\} \subseteq V.$ Ini berarti $$N(A) = N(v_1) \cup N(v_5) = \{v_1, v_2, v_4, v_5\}.$$Definisi: Derajat Simpul pada Graf Tak-berarah
Sebagai contoh, perhatikan model graf berikut.
Berdasarkan graf di atas, diketahui derajat dari masing-masing simpul adalah sebagai berikut.
$$\begin{aligned} \text{deg}(v_1) & = 2 \\ \text{deg}(v_2) & = 4 \\ \text{deg}(v_3) & = 2 \\ \text{deg}(v_4) & = 2 \\ \text{deg}(v_5) & = 4 \end{aligned}$$
Berkaitan dengan besar derajat, ada dua terminologi lain yang sering dipakai. Pertama, simpul terpencil (isolated vertex), yaitu simpul yang derajatnya nol. Kedua, anting-anting (pendant), adalah simpul yang derajatnya satu. Pada model graf di bawah, $v_6$ dan $v_7$ merupakan simpul terpencil, sedangkan $v_1$ merupakan contoh anting-anting.
Definisi: Derajat Simpul pada Graf Berarah
Sebagai contoh, perhatikan model graf berikut.
Derajat masuk dan derajat keluar dari setiap simpul pada graf berarah di atas diberikan sebagai berikut. $$\begin{array}{cc} \text{deg}_\text{in}(v_1) = 1 & \text{deg}_\text{out}(v_1) = 2 \\ \text{deg}_\text{in}(v_2) = 1 & \text{deg}_\text{out}(v_2) = 2 \\ \text{deg}_\text{in}(v_3) = 2 & \text{deg}_\text{out}(v_3) = 1 \\ \text{deg}_\text{in}(v_4) = 2 & \text{deg}_\text{out}(v_1) = 2 \end{array}$$
Apa yang akan kita peroleh jika menjumlahkan derajat dari semua simpul pada suatu graf? Karena setiap sisi menghubungkan tepat dua simpul, masing-masing menyumbang dua derajat. Ini berarti jumlah derajat dari semua simpul akan sama dengan dua kali banyak sisinya. Hal ini dinyatakan dalam lema jabat tangan (kadang disebut sebagai teorema jabat tangan, atau handshaking theorem) karena jumlah derajat dan sisinya dapat dianalogikan sebagai jabat tangan.
Lema Jabat Tangan
$$2e = \displaystyle \sum_{v \in V} \text{deg}(v).$$Catatan: Lema ini berlaku meskipun graf mengandung sisi rangkap dan gelang.
Misalkan $G = (V, E)$ merupakan graf tak-berarah dengan $e$ sisi. Misalkan juga $V = \{v_1,v_2, v_3, \cdots, v_n\}.$ Setiap sisi menghubungkan dua simpul sehingga memberi satu derajat pada masing-masing simpul graf tersebut. Khusus untuk gelang, kontribusinya pada derajat simpul sebesar dua. Dengan kata lain, jika ada $e$ sisi, jumlah derajat simpulnya adalah $2e.$ Dengan demikian, ditulis
$$\begin{aligned} 2e & = \text{deg}(v_1) + \text{deg}(v_2) + \cdots + \text{deg}(v_n) \\ & = \displaystyle \sum_{v \in V} \text{deg}(v). \end{aligned}$$Jadi, lema jabat tangan terbukti benar. $\blacksquare$
Akibat: Lema Jabat Tangan
Ambil sembarang graf $G = (V, E).$ Misalkan $V_1$ dan $V_2$ berturut-turut merupakan himpunan simpul berderajat ganjil dan genap pada $G.$ Dengan menggunakan lema jabat tangan, diperoleh
$$\color{blue}{2e} = \displaystyle \color{red}{\sum_{v \in V_1} \text{deg}(v)} + \color{purple}{\sum_{v \in V_2} \text{deg}(v)}.$$Karena $\text{deg}(v)$ genap untuk setiap $v \in V_2,$ nilai dari $\displaystyle \color{purple}{\sum_{v \in V_2}\text{deg}(v)}$ pastilah berupa bilangan genap. Di sisi lain, $\color{blue}{2e}$ juga genap karena memuat faktor $2.$ Akibatnya, nilai dari $\displaystyle \color{red}{\sum_{v \in V_1} \text{deg}(v)}$ haruslah berupa bilangan genap juga sebagaimana genap = genap + genap. Karena $\text{deg}(v)$ ganjil untuk setiap $v \in V_1,$ banyaknya simpul $v$ di $V_2$ harus genap agar jumlah seluruh derajatnya genap.
Dari sini, disimpulkan bahwa banyaknya simpul yang berderajat ganjil selalu genap. $\blacksquare$
Ada beberapa graf khusus yang diberi nama. Kita akan membahasnya satu persatu dimulai dari graf lengkap.
Definisi: Graf Lengkap
Berdasarkan definisi di atas, setiap simpul pada $K_n$ pasti berderajat $(n-1).$ Model graf $K_i$ untuk $1 \le i \le 5$ diberikan sebagai berikut.
Definisi: Graf Beraturan
Sebaliknya, graf yang tidak semua simpulnya memiliki derajat yang sama disebut sebagai graf tak-beraturan (irregular graph). Namun, graf tak-beraturan cenderung tidak menarik untuk dibahas karena hanya ada satu graf yang memenuhi kriteria, yaitu graf trivial (graf dengan satu simpul tanpa ada satu sisi pun).
Contoh model graf beraturan berderajat $0, 1,$ dan $2$ diberikan sebagai berikut.
Definisi: Siklus dan Graf Siklus (Graf Lingkaran)
Contoh model graf siklus diberikan sebagai berikut.
Model graf berikut bukan termasuk graf siklus karena memuat lebih dari satu siklus. Lebih lanjut, siklus terpendek (siklus dengan sisi paling sedikit) yang termuat dalam suatu graf disebut sebagai lilitan (girth). Graf yang tidak memuat siklus disebut sebagai graf asiklik (acyclic graph).
Definisi: Roda dan Graf Roda
Contoh model graf roda diberikan sebagai berikut.
Definisi: Hiperkubus Dimensional
Berikut ini merupakan model graf untuk $Q_1, Q_2,$ dan $Q_3.$
Kadang-kadang graf memiliki sejumlah simpul yang dapat dipartisi menjadi dua himpunan simpul yang saling lepas dan takkosong sehingga setiap sisi pada graf tersebut menghubungkan satu simpul pada himpunan pertama dengan satu simpul pada himpunan kedua. Hal ini dapat dianalogikan sebagai sejumlah orang di suatu desa yang dibagi menjadi dua kelompok: pria dan wanita (minimal ada satu orang dalam masing-masing kelompok). Jika masing-masing orang dianggap sebagai simpul dan pernikahan (relasi “menikah dengan”) dianggap sebagai sisi pada graf, kita telah melakukan partisi yang diinginkan karena sisi yang terbentuk pasti menghubungkan satu simpul pada himpunan pertama (kelompok pria) dengan satu simpul pada himpunan kedua (kelompok wanita).
Kita akan mendefinisikan secara formal dengan menghadirkan terminologi baru.
Definisi: Graf Bipartit
Sebagai contoh, perhatikan model graf berikut.
Graf di atas terdiri dari $5$ simpul dan $5$ sisi. Graf tersebut bipartit karena kita dapat mempartisi simpulnya menjadi dua himpunan $V_1 = \{v_2, v_5\}$ dan $V_2 = \{v_1, v_3, v_4\}$ sehingga setiap sisinya menghubungkan satu simpul di $V_1$ dengan satu simpul di $V_2.$
Bagaimana dengan model graf berikut?
Graf di atas tidak bipartit. Bagaimana pun caranya, partisi yang diinginkan sesuai definisi tidak akan bisa dilakukan. Selain itu, graf trivial (graf dengan tepat satu simpul tanpa ada sisi) bukan graf bipartit karena partisi himpunan simpul tidak bisa dilakukan. Lebih lanjut, graf kosong (graf yang memuat simpul tanpa sisi) yang simpulnya lebih dari satu merupakan graf bipartit.
Definisi: Pemadanan
Berdasarkan definisi di atas, pemadanan merupakan subhimpunan sisi graf sehingga jika $\{s, t\}$ dan $\{u, v\}$ merupakan sisi berbeda dari pemadanan itu, maka $s, t, u,$ dan $v$ keempatnya merupakan simpul yang berbeda pula. Simpul yang bersisian dengan sisi dari pemadanan $M$ dikatakan terpadankan (matched) di $M.$ Sebaliknya, simpul yang tidak demikian dikatakan takterpadankan (unmatched). Pemadanan maksimum (maximum matching) merupakan pemadanan dengan banyak sisi maksimum. Kita katakan pemadanan $M$ dalam graf bipartit $G = (V, E)$ dengan bipartisi $(V_1, V_2)$ merupakan pemadanan lengkap (complete matching) dari $V_1$ ke $V_2$ jika setiap simpul di $V_1$ merupakan simpul ujung dari suatu sisi dalam pemadanan tersebut, atau ekuivalen dengan $|M| = |V_1|.$
Definisi: Graf Bipartit Lengkap
Dari definisi tersebut, banyak sisi pada graf bipartit lengkap adalah $m \cdot n.$ Sebagai contoh, perhatikan model graf bipartit lengkap $K_{2, 3}$ berikut. Graf ini memiliki $2 \cdot 3 = 6$ sisi.
Definisi: Barisan Derajat
Sebagai contoh, perhatikan model graf berikut.
Tinjau derajat dari tujuh simpul pada graf tersebut.
$$\begin{aligned} \text{deg}(1) & = 2 \\ \text{deg}(2) & = 2 \\ \text{deg}(3) & = 2 \\ \text{deg}(4) & = 0 \\ \text{deg}(5) & = 1 \\ \text{deg}(6) & = 1 \\ \text{deg}(7) & = 2 \end{aligned}$$Dengan demikian, barisan derajat graf tersebut dinyatakan oleh $(2, 2, 2, 2, 1, 1, 0).$
Setiap graf memiliki barisan derajat yang tunggal seperti yang dicontohkan di atas. Perhatikan bahwa barisan derajat tidak selalu merepresentasikan graf yang sama secara struktur. Dengan kata lain, graf yang direpresentasikan oleh barisan derajat tertentu tidak tunggal, bisa macam-macam, seperti contoh berikut.
Angka di setiap simpul menyatakan derajat simpul tersebut. Tampak bahwa $G$ dan $H$ memiliki struktur yang berbeda, tetapi keduanya memiliki derajat yang sama, yaitu $(3, 3, 2, 2, 2, 1, 1).$
Di bawah ini telah disediakan sejumlah soal dan pembahasan tentang dasar-dasar graf dan terminologinya. Sebagian soal dibuat oleh penulis sendiri dan sebagian lainnya diadaptasi dari literatur.
Baca: Istilah Lengkap dalam Teori Graf
Artikel ini ditulis berdasarkan beberapa sumber. Salah satu sumber berbahasa Indonesia yang digunakan adalah buku “Matematika Diskrit” karya Rinaldi Munir. Untuk sumber berbahasa Inggris, salah satu yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.
$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Graf} & \text{Graph} \\ 2. & \text{Simpul (Titik)} & \text{Vertex (Node)} \\ 3. & \text{Sisi} & \text{Edge} \\ 4. & \text{Kardinalitas Graf} & \text{Graph Cardinality} \\ 5. & \text{Ordo Graf} & \text{Graph Order} \\ 6. & \text{Ukuran Graf} & \text{Graph Size} \\ 7. & \text{Menghubungkan} & \text{Connect} \\ 8. & \text{Graf Hingga} & \text{Finite Graph} \\ 9. & \text{Graf Takhingga} & \text{Infinite Graph} \\ 10. & \text{Graf Sederhana} & \text{Simple Graph} \\ 11. & \text{Graf Taksederhana} & \text{Unsimple Graph} \\ 12. & \text{Multigraf} & \text{Multigraph} \\ 13. & \text{Sisi Rangkap} & \text{Multiple Edge} \\ 14. & \text{Graf Semu} & \text{Pseudograph} \\ 15. & \text{Gelang} & \text{Loop} \\ 16. & \text{Graf Tak-berarah} & \text{Undirected Graph} \\ 17. & \text{Graf Berarah} & \text{Directed Graph (Digraph)} \\ 18. & \text{Graf Berarah Sederhana} & \text{Simple Directed Graph} \\ 19. & \text{Sisi Berarah Rangkap} & \text{Multiple Directed Edge} \\ 20. & \text{Multigraf Berarah} & \text{Directed Multigraph} \\ 21. & \text{Simpul Awal} & \text{Initial Vertex} \\ 22. & \text{Simpul Akhir} & \text{Terminal Vertex} \\ 23. & \text{Derajat Masuk} & \text{In-degree} \\ 24. & \text{Derajat Keluar} & \text{Out-degree} \\ 25. & \text{Sisi Berarah (Busur)} & \text{Directed Edge (Arc)} \\ 26. & \text{Graf Trivial} & \text{Trivial Graph} \\ 27. & \text{Graf Kosong} & \text{Null (Empty) Graph} \\ 28. & \text{Graf Campuran} & \text{Mixed Graph} \\ 29. & \text{Bertetangga (Bersampingan)} & \text{Neighbor (Adjacent)} \\ 30. & \text{Bersisian (Terkait)} & \text{Incident} \\ 31. & \text{Lingkungan} & \text{Neighborhood} \\ 32. & \text{Derajat} & \text{Degree} \\ 33. & \text{Simpul Terpencil} & \text{Isolated Vertex} \\ 34. & \text{Anting-anting} & \text{Pendant} \\ 35. & \text{Lema Jabat Tangan} & \text{Handshaking Lemma} \\ 36. & \text{Graf Lengkap} & \text{Complete Graph} \\ 37. & \text{Graf Beraturan} & \text{Regular Graph} \\ 38. & \text{Graf Tak-beraturan} & \text{Irregular Graph} \\ 39. & \text{Siklus} & \text{Cycle} \\ 40. & \text{Lilitan} & \text{Girth} \\ 41. & \text{Graf Siklus (Graf Lingkaran)} & \text{Cycle Graph} \\ 42. & \text{Graf Asiklik} & \text{Acyclic Graph} \\ 43. & \text{Roda} & \text{Wheel} \\ 44. & \text{Graf Roda} & \text{Wheel Graph} \\ 45. & \text{Graf Bipartit} & \text{Bipartite Graph} \\ 46. & \text{Bipartisi} & \text{Bipartition} \\ 47. & \text{Graf Bipartit Lengkap} & \text{Complete Bipartite Graph} \\ 48. & \text{Barisan Derajat} & \text{Degree Sequence} \\ 49. & \text{Grafikal} & \text{Graphical (Graphic)} \\ \hline \end{array}$$
Quote by Francis of Assisi
Bagian Pilihan Ganda
Soal Nomor 1
Contoh model graf sederhana yang memuat simpul berderajat $1$ adalah $\cdots \cdot$
Cek opsi A:
Model graf yang ditunjukkan pada opsi A merupakan graf sederhana dengan $6$ simpul dan setiap simpul pinggirnya berderajat $3,$ sedangkan simpul tengahnya berderajat $5.$ Model graf ini tidak memenuhi kriteria yang diinginkan karena tidak memuat simpul berderajat $1.$
Cek opsi B:
Model graf yang ditunjukkan pada opsi B bukan graf sederhana karena memuat gelang.
Cek opsi C:
Model graf yang ditunjukkan pada opsi C merupakan graf sederhana dengan $4$ simpul. Dua simpul di antaranya berderajat $1,$ sedangkan dua simpul lainnya berderajat $2.$ Jadi, model graf ini memenuhi kriteria yang diinginkan.
Cek opsi D:
Model graf yang ditunjukkan pada opsi D bukan graf sederhana karena memuat gelang.
Cek opsi E:
Model graf yang ditunjukkan pada opsi E bukan graf sederhana karena memuat sisi rangkap.
(Jawaban C)
Soal Nomor 2
Berdasarkan model graf berikut, simpul yang memiliki derajat tertinggi adalah $\cdots \cdot$
A. simpul $b$ D. simpul $g$
B. simpul $d$ E. simpul $h$
C. simpul $e$
Graf yang dimodelkan seperti gambar merupakan multigraf dengan $8$ simpul dan $9$ sisi. Derajat masing-masing simpul dapat dilihat dari banyaknya sisi yang bersisian dengannya. Sebagai contoh, derajat dari simpul $a$ adalah $2$ karena ada dua sisi yang bersisian dengannya. Secara matematis, ditulis $\text{deg}(a) = 2.$ Untuk simpul yang lain, diperoleh
$$\begin{aligned} \text{deg}(b) & = 3 \\ \text{deg}(c) & = 2 \\ \text{deg}(d) & = 3 \\ \text{deg}(e) & = 4 \\ \text{deg}(f) & = 1 \\ \text{deg}(g) & = 2 \\ \text{deg}(h) & = 1. \end{aligned}$$Jadi, simpul dengan derajat tertinggi adalah simpul $e.$
(Jawaban C)
Soal Nomor 3
Perhatikan model graf berikut.
Misalkan $m$ dan $n$ berturut-turut menyatakan banyak simpul dan sisi pada graf di atas. Nilai dari $2m + n = \cdots \cdot$
A. $12$ C. $16$ E. $18$
B. $13$ D. $17$
Cermati model graf yang diberikan dengan seksama. Banyak simpul pada graf tersebut adalah $m = 5,$ yaitu $v_1, v_2, v_3, v_4,$ dan $v_5.$ Sisinya meliputi $$\{v_1, v_2\}, \{v_1, v_2\}, \{v_2, v_3\}, \{v_2, v_5\}, \{v_3, v_4\}, \{v_4, v_5\},~\text{dan}~\{v_5, v_5\}.$$Dengan kata lain, ada $n = 7$ sisi pada graf tersebut. Jadi, nilai dari $\boxed{2m + n = 2(5) + 7 = 17}$
(Jawaban D)
Soal Nomor 4
Perhatikan model graf berikut.
Pernyataan yang benar terkait graf di atas adalah $\cdots \cdot$
- Simpul $v_1$ bertetangga dengan $v_2$
- Simpul $v_4$ bertetangga dengan $v_2$ dan $v_5$
- Simpul $v_2$ merupakan simpul terpencil
- Graf tersebut bukan graf sederhana
- Derajat dari $v_5$ adalah $\text{deg}(v_5) = 2$
Cermati model graf yang diberikan dengan seksama.
Cek opsi A:
Simpul $v_1$ bertetangga dengan $v_5,$ bukan $v_2.$
Cek opsi B:
Benar bahwa simpul $v_4$ bertetangga dengan $v_2$ dan $v_5.$
Cek opsi C:
Simpul $v_2$ bukan simpul terpencil karena ada setidaknya satu sisi yang menghubungkannya dengan simpul lain.
Cek opsi D:
Graf tersebut seharusnya graf sederhana karena tidak memuat sisi rangkap maupun gelang.
Cek opsi E:
Karena ada tiga sisi yang menghubungkan $v_5$ ke simpul yang lain, derajat dari $v_5$ adalah $\text{deg}(v_5) = 3.$
(Jawaban B)
Soal Nomor 5
Misalkan simpul dari suatu graf merepresentasikan kota, sedangkan sisinya merepresentasikan jalur perjalanan yang menghubungkan kota yang satu ke kota yang lain. Jika dimodelkan dalam graf, pernyataan berikut yang tepat adalah $\cdots \cdot$
- Graf yang dibuat merupakan graf sederhana
- Graf yang dibuat memuat gelang
- Graf yang dibuat merupakan multigraf
- Graf yang dibuat pasti memuat simpul terpencil
- Sisi pada graf yang dibuat tidak harus berarah
Misalkan simpul dari suatu graf merepresentasikan kota, sedangkan sisinya merepresentasikan jalur perjalanan yang menghubungkan dua kota berbeda.
Cek opsi A:
Graf yang dibuat boleh memiliki sisi rangkap, artinya ada lebih dari satu jalur yang dapat ditempuh untuk berangkat dari satu kota tertentu ke kota yang lain. Jadi, graf yang dibuat belum tentu sederhana.
Cek opsi B:
Ada kemungkinan suatu kota memiliki jalur tertentu yang rutenya akan balik ke kota semula (biasanya digunakan untuk keperluan wisata/jalan-jalan). Namun, hal ini bukan berarti graf yang merepresentasikannya memuat gelang karena jalur seperti itu bersifat opsional (boleh ada, boleh tidak).
Cek opsi C:
Graf yang dibuat boleh memiliki sisi rangkap. Jika demikian, graf seperti itu disebut multigraf. Namun, tidak ada keharusan untuk memuat sisi rangkap dalam kasus ini. Dengan kata lain, ada kemungkinan terdapat satu rute saja yang menghubungkan setiap kota tertentu ke kota yang lain.
Cek opsi D:
Ketika graf yang dibuat memuat simpul terpencil, itu artinya ada kota yang terisolasi (tidak bisa dikunjungi dengan jalur perjalanan apa pun). Hal ini memang mungkin saja terjadi, misalnya karena kebijakan karantina untuk pencegahan penyebaran penyakit. Namun, tidak ada keharusan hal itu terjadi.
Cek opsi E:
Sisi pada graf yang dibuat tidak harus berarah. Pernyataan ini benar. Dengan kata lain, sisi pada graf boleh berarah atau tidak. Jika sisinya berarah, jalur perjalanan yang menghubungkan suatu kota $A$ ke $B$ berbeda dengan jalur perjalanan dari arah sebaliknya. Namun, jika sisinya tidak berarah, jalur perjalanan dapat dilalui, baik dari suatu kota $A$ maupun dari kota yang lain.
(Jawaban E)
Soal Nomor 6
Kondisi berikut yang tidak mungkin terjadi terkait dengan banyak simpul dan derajatnya adalah $\cdots \cdot$
- Graf $A$ memiliki $7$ simpul yang setiap simpulnya berderajat $3$
- Graf $B$ memiliki $11$ simpul yang setiap simpulnya berderajat $2$
- Graf $C$ memiliki $10$ simpul yang setiap simpulnya berderajat $5$
- Jumlah derajat dari graf $D$ adalah $0$
- Banyak simpul dari graf $E$ adalah $5$
Berdasarkan akibat lema jabat tangan, jumlah derajat dari simpul pada setiap graf haruslah berupa bilangan genap. Oleh karena itu, graf $A$ tidak mungkin ada karena jumlah derajatnya adalah $7 \times 3 = 21$ (ganjil). Graf $B$ dan $C$ dapat dibuat karena jumlah derajatnya berturut-turut adalah $22$ dan $50$ (genap). Karena jumlah derajatnya $0,$ graf $D$ merupakan graf trivial atau graf kosong (hanya memuat simpul). Graf $E$ jelas dapat dibuat.
(Jawaban A)
Soal Nomor 7
Misalkan graf $G$ memiliki $n \ge 2$ simpul yang semua simpulnya berderajat $0.$ Dari pernyataan tersebut, dapat kita katakan bahwa $G$ merupakan $\cdots \cdot$
A. graf trivial
B. graf bipartit lengkap
C. graf taksederhana
D. graf lengkap
E. graf beraturan
Misalkan graf $G$ memiliki $n \ge 2$ simpul yang semua simpulnya berderajat $0.$ Dari sini, kita tahu bahwa $G$ tidak memiliki sisi sama sekali.
Cek opsi A:
Graf trivial hanya terdiri dari $1$ simpul tanpa ada sisi. $G$ bukan graf trivial karena memuat setidaknya $2$ simpul.
Cek opsi B:
Jika $G$ merupakan graf bipartit lengkap, setiap simpul dari himpunan partisi pertama dari $G$ harus bertetangga dengan setiap simpul pada himpunan partisi yang lain dari $G.$ Faktanya, $G$ tidak memiliki sisi sama sekali sehingga jelas bukan graf bipartit lengkap.
Cek opsi C:
Graf taksederhana harus memuat setidaknya satu sisi rangkap atau satu gelang. Faktanya, $G$ tidak memiliki sisi sama sekali sehingga jelas bukan graf taksederhana.
Cek opsi D:
Setiap simpul pada graf lengkap harus saling bertetangga satu sama lain. Dengan kata lain, graf lengkap harus memiliki sisi. Faktanya, $G$ tidak memiliki sisi sama sekali sehingga jelas bukan graf lengkap.
Cek opsi E:
Graf beraturan adalah graf yang setiap simpulnya berderajat sama. Karena setiap simpul pada graf $G$ berderajat $0,$ disimpulkan bahwa $G$ merupakan graf beraturan.
(Jawaban E)
Soal Nomor 8
Suatu graf sederhana akan dibentuk dari $25$ sisi. Tidak ada simpul terpencil pada graf tersebut. Jika $n$ menyatakan banyak simpul pada graf tersebut, maka nilai maksimum dari $n$ adalah $\cdots \cdot$
A. $1$ C. $26$ E. $51$
B. $25$ D. $50$
Misalkan $G$ merupakan graf sederhana dengan $25$ sisi dan tidak memuat simpul terpencil. Agar diperoleh simpul sebanyak mungkin, satu simpul tertentu harus bertetangga dengan $25$ simpul lainnya dengan menggunakan $25$ sisi tersebut. Secara matematis, jika $v_1, v_2, \cdots, v_{26}$ merupakan simpul-simpul pada graf $G,$ maka sisinya adalah $\{v_1, v_2\},$ $\{v_1, v_3\},$ $\cdots,$ dan $\{v_1, v_{26}\}.$ Jadi, paling banyak ada $\boxed{26}$ simpul pada graf tersebut.
(Jawaban C)
Soal Nomor 9
Sebanyak $n$ unit komputer akan dihubungkan dengan sejumlah potongan kabel, baik secara langsung ataupun terhubung melalui komputer lainnya. Banyak potongan kabel minimum yang dibutuhkan adalah $\cdots$ potongan.
A. $n-1$ D. $2n$
B. $n$ E. $n^2$
C. $n+1$
Misalkan $G = (V, E)$ merupakan graf sehingga simpulnya merepresentasikan komputer dan sisinya merepresentasikan keterhubungan komputer. Agar potongan kabel sesedikit mungkin dan semua komputer terhubung, graf yang dibuat harus berupa $$G = (v_1 \mid v_1v_2 \mid v_2 \mid v_2v_3 \mid v_3 \mid \cdots \mid v_{n-1} \mid v_{n-1}v_n \mid v_n)$$dengan $v_i \in V$ dan $v_{i-1}v_i \in E$ untuk $1 \le i \le n.$ Ini berarti komputer pertama $(v_1)$ dihubungkan secara langsung dengan komputer kedua $(v_2),$ kemudian komputer kedua $(v_2)$ dihubungkan secara langsung dengan $(v_3),$ dan seterusnya sampai komputer kedua terakhir $(v_{n-1})$ dihubungkan secara langsung dengan komputer terakhir $(v_n).$
Dengan demikian, potongan kabel minimum yang dibutuhkan adalah $\boxed{n-1}$ potongan.
(Jawaban A)
Soal Nomor 10
Banyak sisi pada graf bipartit lengkap $K_{10, 15}$ adalah $\cdots \cdot$
A. $15$ C. $75$ E. $300$
B. $25$ D. $150$
Graf bipartit lengkap $K_{10, 15}$ merupakan graf bipartit yang simpulnya dipartisi dalam dua himpunan saling lepas, $V_1$ dan $V_2,$ yang masing-masing memuat $10$ simpul dan $15$ simpul serta setiap simpul di $V_1$ bertetangga dengan setiap simpul di $V_2$. Dengan kata lain, simpul pertama di $V_1$ bertetangga dengan $10$ simpul di $V_2$ sehingga $10$ sisi terbentuk. Simpul kedua di $V_1$ juga demikian sehingga $10$ sisi lain terbentuk. Jika diteruskan, akan ada $\boxed{15 \times 10 = 150}$ sisi yang terbentuk dari graf bipartit lengkap $K_{10, 15}.$
(Jawaban D)
Soal Nomor 11
Banyak simpul maksimum dan minimum pada graf sederhana yang mempunyai $16$ sisi dan setiap simpulnya berderajat sama dan $\ge 4$ berturut-turut adalah $\cdots \cdot$
A. $12$ dan $6$
B. $12$ dan $8$
C. $10$ dan $8$
D. $8$ dan $8$
E. $8$ dan $2$
Karena setiap simpul berderajat sama, graf sederhana tersebut merupakan graf beraturan. Misalkan $n$ dan $e$ berturut-turut menyatakan banyak simpul dan sisi pada graf tersebut. Dengan menggunakan lema jabat tangan, banyak sisi graf beraturan berderajat $r$ adalah
$$\begin{aligned} 2e & = \underbrace{r + r + \cdots + r}_{\text{sebanyak}~n} \\ 2e & = nr \\ n & = \dfrac{2e}{r}. \end{aligned}$$Karena diketahui banyak sisi graf tersebut adalah $e = 16,$ diperoleh $n = \dfrac{32}{r}.$ Sekarang periksa nilai-nilai $r$ sehingga $n$ bulat.
- Agar diperoleh nilai $n$ yang sebesar mungkin, nilai $r$ harus dibuat kecil. Namun, karena derajatnya $\ge 4,$ kita ambil $r = 4$ sehingga diperoleh $n = 8$ sebagai banyak simpul maksimum.
- Untuk $r = 8,$ diperoleh $n = \dfrac{32}{8}=4.$ Namun, graf tidak akan sederhana karena pasti memuat sisi rangkap/gelang.
- Untuk $r = 16,$ diperoleh $n = \dfrac{32}{16}=2.$ Namun, graf tidak akan sederhana karena pasti memuat sisi rangkap/gelang.
- Untuk $r = 32,$ diperoleh $n = \dfrac{32}{32} = 1.$ Jelas ini tidak mungkin terjadi ketika graf hanya memiliki $1$ simpul dengan derajat $32.$
Jadi, tidak ada kemungkinan banyak simpul yang lain. Ini berarti banyak simpul minimum pada graf juga $8.$
(Jawaban D)
Soal Nomor 12
Misalkan $G= (V, E)$ merupakan graf bipartit dengan $|V| = 2m + 1$ untuk suatu bilangan asli $m.$ Banyak sisi maksimum yang dapat dimiliki oleh $G$ adalah $\cdots \cdot$
A. $2m + 1$
B. $m^2-m$
C. $m^2$
D. $m^2 + m$
E. $m^2 + m + 1$
Misalkan $G= (V, E)$ merupakan graf bipartit dengan $|V| = 2m + 1$ untuk suatu bilangan asli $m.$ Agar sisi $G$ sebanyak mungkin, dua himpunan partisi dari $V(G),$ yaitu $V_1$ dan $V_2,$ harus memiliki selisih banyak elemen sekecil mungkin. Karena $|V| = 2m+1$ merupakan bilangan ganjil, kita tidak bisa membagi rata simpulnya sama banyak. Namun, tanpa mengurangi keumuman, kita dapat memisalkan $|V_1| = m+1$ dan $|V_2| = m$ sehingga selisih banyak elemennya hanya satu. Untuk memperoleh sisi sebanyak mungkin, setiap simpul di $V_1$ harus bertetangga dengan setiap simpul di $V_2$ (membentuk graf bipartit lengkap).
Akibatnya, akan ada $$\underbrace{m + m + \cdots + m}_{\text{sebanyak}~m+1} = (m+1)m = m^2 + m$$sisi yang dapat dibuat. Dengan kata lain, banyak sisi maksimum yang dapat dimiliki oleh $G$ adalah $\boxed{m^2 + m}$
(Jawaban D)
Soal Nomor 13
Banyaknya sisi dari graf sederhana dengan barisan derajat $(5, 2, 2, 2, 2, 1)$ adalah $\cdots \cdot$
A. $4$ C. $7$ E. $13$
B. $5$ D. $8$
Diketahui graf sederhana dengan barisan derajat $(5, 2, 2, 2, 2, 1).$
Berdasarkan lema jabat tangan, untuk setiap graf, 2 kali banyak sisi sama dengan jumlah derajat simpul. Misalkan $|E|$ menyatakan banyaknya sisi dari graf tersebut. Dengan demikian, diperoleh
$$\begin{aligned} 2|E| & = 5+2+2+2+2+1 \\ 2|E| & = 14 \\ |E| & = 7 \end{aligned}$$Jadi, graf tersebut memiliki $\boxed{7}$ sisi. Lebih lanjut, berikut diberikan model graf dengan barisan derajat $(5, 2, 2, 2, 2, 1).$
(Jawaban C)
Soal Nomor 14
Barisan derajat berikut yang termasuk grafikal adalah $\cdots \cdot$
A. $(5, 4, 3, 2, 1, 0)$
B. $(3, 3, 3, 2, 2, 2)$
C. $(5, 3, 3, 3, 3, 3)$
D. $(6, 5, 4, 3, 2, 1)$
E. $(5, 5, 4, 3, 2, 1)$
Grafikal adalah barisan derajat yang dapat direpresentasikan dengan menggunakan suatu graf sederhana.
Cek opsi A:
Barisan derajat $(5, 4, 3, 2, 1, 0)$ bukan barisan derajat dari graf apa pun. Simpul yang berderajat $5$ pasti bertetangga dengan $5$ simpul lainnya termasuk dengan simpul yang berderajat $0.$ Hal itu tidak mungkin terjadi. Selain itu, simpul berderajat ganjil $(5, 3, 1)$ ada sebanyak $3$ (ganjil). Kondisi ini melanggar akibat dari lema jabat tangan yang menegaskan bahwa simpul berderajat ganjil seharusnya muncul sebanyak genap.
Cek opsi B:
Barisan derajat $(3, 3, 3, 2, 2, 2)$ bukan barisan derajat dari graf apa pun. Perhatikan bahwa simpul berderajat ganjil $(3, 3, 3)$ ada sebanyak $3$ (ganjil). Kondisi ini melanggar akibat dari lema jabat tangan yang menegaskan bahwa simpul berderajat ganjil pasti muncul sebanyak genap.
Cek opsi C:
Barisan derajat $(5, 3, 3, 3, 3, 3)$ merupakan grafikal. Kita dapat membuat graf sederhana dengan barisan derajat tersebut seperti berikut. Angka di setiap simpul menyatakan derajat dari simpul tersebut.
Cek opsi D:
Barisan derajat $(6, 5, 4, 3, 2, 1)$ bukan barisan derajat dari graf apa pun. Perhatikan bahwa simpul berderajat ganjil $(5, 3, 1)$ ada sebanyak $3$ (ganjil). Kondisi ini melanggar akibat dari lema jabat tangan yang menegaskan bahwa simpul berderajat ganjil pasti muncul sebanyak genap.
Cek opsi E:
Barisan derajat $(5, 5, 4, 3, 2, 1)$ bukan grafikal. Kita punya dua simpul berderajat $5.$ Ini berarti dua simpul tersebut bertetangga dengan $5$ simpul lainnya, termasuk dengan simpul berderajat $1.$ Hal itu tidak mungkin terjadi karena simpul-simpul yang tidak berderajat $5$ memiliki setidaknya $2$ tetangga. Dengan kata lain, derajat minimumnya adalah $2.$
(Jawaban C)
Soal Nomor 15
Misalkan $n$ merupakan bilangan bulat positif. Barisan derajat dari graf lengkap $K_n$ adalah $\cdots \cdot$
A. $(\underbrace{n+1, n+1, \cdots, n+1}_{\text{sebanyak}~n})$
B. $(\underbrace{n-1, n-1, \cdots, n-1}_{\text{sebanyak}~n})$
C. $(\underbrace{n, n, \cdots, n}_{\text{sebanyak}~n-1})$
D. $(\underbrace{n, n, \cdots, n}_{\text{sebanyak}~n})$
E. $(\underbrace{n-1, n-1, \cdots, n-1}_{\text{sebanyak}~n+1})$
Graf lengkap $K_n$ memiliki $n$ simpul yang setiap simpulnya saling bertetangga satu sama lain. Dengan kata lain, masing-masing simpul tersebut bertetangga dengan $n-1$ simpul lainnya. Ini berarti setiap simpul berderajat $n-1$ sehingga barisan derajat dari graf lengkap $K_n$ adalah $(\underbrace{n-1, n-1, \cdots, n-1}_{\text{sebanyak}~n}).$
(Jawaban B)
Soal Nomor 16
Misalkan $m$ dan $n$ merupakan bilangan bulat positif dengan $m \ge n.$ Barisan derajat dari graf bipartit lengkap $K_{m, n}$ adalah $\cdots \cdot$
- $(\underbrace{m, m, \cdots, m}_{\text{sebanyak}~n}, \underbrace{n, n, \cdots n}_{\text{sebanyak}~m})$
- $(\underbrace{m, m, \cdots, m}_{\text{sebanyak}~m}, \underbrace{n, n, \cdots n}_{\text{sebanyak}~n})$
- $(\underbrace{m, m, \cdots, m}_{\text{sebanyak}~n}, \underbrace{n, n, \cdots n}_{\text{sebanyak}~n})$
- $(\underbrace{m, m, \cdots, m}_{\text{sebanyak}~m}, \underbrace{n, n, \cdots n}_{\text{sebanyak}~m})$
- $(m, n)$
Misalkan $m$ dan $n$ merupakan bilangan bulat positif dengan $m \ge n.$ Misalkan juga himpunan partisi dari simpul pada $K_{m, n}$ adalah $V_1$ dan $V_2$ dengan $|V_1| = m$ dan $|V_2| = n.$ Karena $K_{m, n}$ merupakan graf bipartit lengkap, setiap simpul di $V_1$ bertetangga dengan setiap simpul di $V_2.$ Akibatnya, setiap simpul di $V_1$ akan berderajat $n,$ sedangkan setiap simpul di $V_2$ akan berderajat $m.$ Jadi, barisan derajat dari graf bipartit lengkap $K_{m, n}$ adalah
$$(\underbrace{m, m, \cdots, m}_{\text{sebanyak}~n}, \underbrace{n, n, \cdots n}_{\text{sebanyak}~m}).$$(Jawaban A)
Bagian Uraian
Soal Nomor 1
Dalam suatu pesta, enam orang saling berjabat tangan. Setiap orang hanya berjabat tangan satu kali dengan orang lainnya. Modelkan kasus ini dalam graf dan hitung banyak jabat tangan yang terjadi.
Misalkan graf $G = (V, E)$ merupakan representasi graf untuk kasus tersebut. Himpunan simpul $V$ merepresentasikan orang, sedangkan himpunan sisi $E$ merepresentasikan jabat tangan. Karena setiap orang berjabat tangan satu kali dengan orang lainnya, graf yang dibuat merupakan graf lengkap dengan $6$ simpul, dinotasikan $K_6,$ seperti yang tampak pada gambar berikut.
Banyak jabat tangan yang terjadi sama dengan banyak sisi pada graf tersebut, yaitu $5+4+3+2+1=15.$
Catatan: Secara umum, banyak sisi pada graf beraturan dengan $n$ simpul adalah $\dfrac{n(n-1)}{2}.$
Soal Nomor 2
Buktikan bahwa tidak ada graf beraturan berderajat $3$ dengan $7$ simpul.
Dengan menggunakan metode kontradiksi, andaikan terdapat graf beraturan berderajat $3$ dengan $7$ simpul. Ini berarti jumlah derajat simpulnya adalah $7 \times 3 = 21.$ Hal ini kontradiktif dengan lema jabat tangan yang menjamin bahwa jumlah derajat dari sembarang graf merupakan bilangan genap, padahal $21$ merupakan bilangan ganjil. Jadi, pengandaian salah. Disimpulkan bahwa tidak ada graf beraturan berderajat $3$ dengan $7$ simpul.
Soal Nomor 3
Berapa banyak sisi pada graf berikut?
- Graf lengkap dengan $n$ simpul, dinotasikan oleh $K_n.$
- Siklus dengan $n$ simpul, dinotasikan dengan $C_n.$
- Roda dengan $(n+1)$ simpul, dinotasikan dengan $W_n.$
- Graf bipartit lengkap dengan himpunan partisi beranggotakan $m$ simpul dan $n$ simpul, dinotasikan dengan $K_{m, n}.$
- Graf kubus $Q_n.$
Jawaban a)
$K_n$ memiliki $n$ simpul. Karena setiap simpulnya saling bertetangga, banyak sisi yang terbentuk sama dengan banyak cara memilih $2$ dari $n$ simpul, yaitu $\displaystyle \binom{n}{2} = \dfrac{n(n-1)}{2}.$
Jawaban b)
$C_n$ memiliki $n$ simpul. Berdasarkan definisi siklus, banyak sisi $C_n$ sama dengan banyak simpulnya, yaitu $n.$
Jawaban c)
$W_n$ memiliki $(n+1)$ simpul. Berdasarkan definisi roda, $n$ simpul pembentuk siklus $C_n$ memiliki $n$ sisi. Satu simpul tambahan bertetangga dengan $n$ simpul tersebut. Ini berarti banyak sisinya adalah $n + n = 2n.$
Jawaban d)
$K_{m, n}$ memiliki $(m+n)$ simpul. Karena masing-masing simpul pada himpunan pertama bertetangga dengan $n$ simpul lainnya pada himpunan kedua, banyak sisi yang terbentuk adalah $\underbrace{n + n + \cdots + n}_{\text{sebanyak}~m} = mn.$
Jawaban e)
Karena simpul $Q_n$ merupakan untaian bit dengan panjang $n,$ banyak simpulnya adalah $2^n.$ Setiap simpul berderajat $n$ karena ada $n$ untaian bit yang memiliki tepat satu bit berbeda $($misalnya, $100,$ bertetangga dengan $000, 110,$ dan $101).$ Dengan demikian, jumlah derajat simpulnya adalah $n2^n.$ Berdasarkan lema jabat tangan, jumlah derajat simpul harus sama dengan dua kali banyak sisi. Dengan kata lain, banyak sisi $Q_n$ adalah $\dfrac{n2^n}{2} = n2^{n-1}.$
Rangkuman banyak simpul dan banyak sisi pada lima graf tersebut diberikan dalam tabel berikut.
Soal Nomor 4
Misalkan $G=(V, E)$ merupakan graf sederhana. Tunjukkan bahwa relasi $R$ pada himpunan simpul $V$ sehingga $(u, v) \in R$ dengan $u, v \in V$ jika ada suatu sisi yang menghubungkannya merupakan relasi simetris dan irefleksif pada $G.$
Misalkan $G=(V, E)$ merupakan graf sederhana. Karena sederhana, sisi $G$ tidak berarah. Untuk menunjukkan $R$ simetris, harus ditunjukkan bahwa jika $(u, v) \in R,$ maka $(v, u) \in R.$ Jika $(u, v) \in R,$ terdapat suatu sisi yang dinyatakan oleh $\{u, v\}.$ Namun, $\{u, v\} = \{v, u\}$ sehingga $(v, u) \in R.$ Jadi, $R$ simetris. Selanjutnya, graf sederhana tidak memuat gelang. Ini berarti setiap sisi menghubungkan dua simpul $\{u, v\}$ dengan syarat $u \neq v.$ Oleh karena itu, $(u, v) \notin R$ untuk setiap $u, v \in V.$ Menurut definisi, $R$ irefleksif. $\blacksquare$
Soal Nomor 5
Misalkan $G = (V, E)$ merupakan graf sederhana. Tunjukkan bahwa relasi $R$ pada himpunan simpul $G$ sehingga $(u, v) \in R$ dengan $u, v \in V$ jika ada suatu sisi yang menghubungkannya merupakan relasi simetris dan irefleksif pada $G.$
Misalkan $G = (V, E)$ merupakan graf sederhana. Karena sederhana, sisi $G$ tidak berarah. Untuk menunjukkan $R$ simetris, harus ditunjukkan bahwa jika $(u, v) \in R,$ maka $(v, u) \in R.$ Jika $(u, v) \in R,$ terdapat suatu sisi yang dinyatakan oleh $\{u, v\}.$ Namun, $\{u, v\} = \{v, u\}$ sehingga $(v, u) \in R.$ Jadi, $R$ simetris. Selanjutnya, graf sederhana tidak memuat gelang. Ini berarti setiap sisi menghubungkan dua simpul $\{u, v\}$ dengan syarat $u \neq v.$ Oleh karena itu, $(u, v) \notin R$ untuk setiap $u, v \in V.$ Menurut definisi, $R$ irefleksif.
Soal Nomor 6
Buktikan bahwa jika $G = (V, E)$ merupakan graf sederhana yang memuat $n \ge 2$ simpul, maka $G$ memuat setidaknya dua simpul dengan derajat yang sama.
Misalkan $G = (V, E)$ merupakan graf sederhana yang memuat $n \ge 2$ simpul. Misalkan juga $V = \{v_1, v_2, \cdots, v_n\}.$ Dengan menggunakan metode kontradiksi, andaikan $G$ memuat simpul yang derajatnya berbeda semua. Ini berarti
$$\{\text{deg}(v_1), \text{deg}(v_2), \cdots, \text{deg}(v_n)\} = \{0, 1, 2, \cdots, n-1\}$$karena pada graf sederhana, simpul paling besar berderajat $(n-1).$ Namun, hal ini kontradiksi karena tidak mungkin ada simpul yang berderajat $(n-1)$ dan simpul yang berderajat $0$ sekaligus pada graf sederhana dengan $n$ simpul. Dengan demikian, pengandaian salah. Disimpulkan bahwa $G$ memuat setidaknya dua simpul dengan derajat yang sama.
Jadi, proposisi tersebut terbukti benar. $\blacksquare$
Soal Nomor 7
Misalkan $G$ merupakan graf dengan $n$ simpul dan $e$ sisi. Misalkan juga $m$ merupakan bilangan bulat positif terkecil sehingga $m \ge \dfrac{2e}{n}.$ Buktikan bahwa $G$ memiliki suatu simpul yang berderajat tidak kurang dari $m.$
Klaim bahwa lema terkait rata-rata berikut berlaku.
Lema: Jika $S$ merupakan himpunan hingga dari bilangan bulat, maka $\text{maks}(S) \ge \text{rata}(S)$ dengan $\text{maks}(S)$ dan $\text{rata}(S)$ berturut-turut menyatakan nilai terbesar dari $S$ dan nilai rata-rata dari $S.$
Bukti. Misalkan $S = \{s_i\}_{i=1}^n$ merupakan himpunan hingga dari bilangan bulat. Akibatnya, diperoleh
$$\begin{aligned} \text{maks}(S) & = \dfrac{\overbrace{\text{maks}(S) + \text{maks}(S) + \cdots + \text{maks}(S)}^{n~\text{kali}}}{n} \\ & \ge \dfrac{s_1 + s_2 + \cdots + s_n}{n} && (s_i \le \text{maks}(S)) \\ & = \text{rata}(S). \end{aligned}$$Jadi, lema terbukti.
Sekarang misalkan $G$ merupakan graf dengan $n$ simpul dan $e$ sisi. Misalkan juga $m$ merupakan bilangan bulat positif terkecil sehingga $m \ge \dfrac{2e}{n}.$ Konstruksi $m$ sebagai derajat maksimum dari simpul $G.$
Dengan menggunakan lema di atas dan lema jabat tangan, diperoleh
$$\begin{aligned} m & \ge \dfrac{\text{deg}(v_1) + \text{deg}(v_2) + \cdots + \text{deg}(v_n)}{n} \\ & = \dfrac{2e}{n}. \end{aligned}$$Dari sini, pasti dijamin bahwa ada simpul yang berderajat tidak kurang dari $m,$ salah satunya adalah simpul dengan derajat tertinggi.
Soal Nomor 8
Buktikan bahwa setiap graf bipartit tidak memuat siklus ganjil.
Ambil sembarang graf bipartit $G = (V, E).$ Berdasarkan definisi graf bipartit, simpul graf dapat dipartisi menjadi dua himpunan, $X$ dan $Y,$ sehingga masing-masing sisi pada graf menghubungkan satu simpul di $X$ dengan satu simpul di $Y.$
Dengan menggunakan metode kontradiksi, andaikan $G$ memuat siklus ganjil, katakanlah $C = (v_1, v_2, v_3, \cdots, v_n, v_1)$ untuk suatu bilangan ganjil positif $n.$
Tanpa mengurangi keumuman, misalkan $v_1 \in X.$ Berdasarkan definisi siklus, $v_2 \in Y,$ $v_3 \in X,$ dan seterusnya. Dari sini, diketahui bahwa $v_i \in X$ jika $i$ ganjil. Karena $n$ ganjil, $v_n \in X.$ Namun, $v_n$ dan $v_1$ bertetangga, padahal keduanya berada di $V.$ Hal ini kontradiktif dengan definisi graf bipartit karena seharusnya sisi tidak boleh menghubungkan dua simpul pada himpunan partisi yang sama. Jadi, pengandaian salah. Disimpulkan bahwa setiap graf bipartit tidak memuat siklus ganjil. $\blacksquare$
Soal Nomor 9
Tunjukkan bahwa setiap graf bipartit sederhana dengan $n$ simpul tidak memiliki lebih dari $\dfrac{n^2}{4}$ sisi.
Misalkan $G = (V, E)$ merupakan graf bipartit sederhana sembarang dengan $n$ simpul. Untuk menunjukkan bahwa $G$ tidak memiliki lebih dari $\dfrac{n^2}{4}$ sisi, kita perlu membuktikan bahwa banyak sisi maksimum dari $G$ adalah $\dfrac{n^2}{4}.$
Tanpa mengurangi keumuman, misalkan $V$ dipartisi menjadi dua himpunan, $V_1$ dan $V_2,$ sehingga $V_1$ memuat $i$ simpul dan $V_2$ memuat $(n-i)$ simpul dengan $0 < i < n.$ Agar diperoleh sisi sebanyak mungkin, setiap simpul di $V_1$ harus dihubungkan oleh sisi dengan setiap simpul di $V_2.$ Akibatnya, ada $i(n-i)$ sisi yang terbentuk.
Pandang fungsi $$f(i) = i(n-i) = -i^2+ni$$sebagai fungsi kuadrat dengan variabel $i.$ Fungsi ini akan maksimum saat $i = -\dfrac{n}{2(-1)} =\dfrac{n}{2}$ dengan nilai maksimum $$f\left(\dfrac{n}{2}\right) = \dfrac{n}{2}\left(n-\dfrac{n}{2}\right) = \dfrac{n^2}{4}.$$Jadi, terbukti bahwa banyak sisi maksimum dari $G$ adalah $\dfrac{n^2}{4}.$ Dengan kata lain, terbukti bahwa setiap graf bipartit sederhana dengan $n$ simpul tidak memiliki lebih dari $\dfrac{n^2}{4}$ sisi. $\blacksquare$
Baca: Soal dan Pembahasan – Struktur Pohon dalam Teori Graf
Soal Nomor 10
Misalkan Aurelia $(A),$ Bobby $(B),$ Calista $(C),$ Dinda $(D),$ dan Erminus $(E)$ merupakan lima pegawai yang ditugaskan untuk mempelajari lima jenis aplikasi. Aurelia dan Erminus diminta untuk mempelajari aplikasi $1;$ Bobby, Calista, dan Erminus mempelajari aplikasi $2;$ David mempelajari aplikasi $3;$ Calista dan Erminus mempelajari aplikasi $4;$ dan Erminus mempelajari aplikasi $5.$ Buatlah graf untuk memodelkan masalah ini, kemudian tentukan apakah ada pemadanan yang mungkin.
Misalkan $G = (V, \mathbb{E})$ merupakan graf dengan $V$ sebagai himpunan simpul yang merepresentasikan orang dan aplikasi, dan $\mathbb{E}$ sebagai himpunan sisi yang merepresentasikan hubungan “mempelajari”. Dari sini, graf bipartit-lah yang dapat menjadi model masalah di atas. Dengan menggunakan $10$ simpul, bipartisi $(V_1, V_2)$ masing-masing memuat $5$ simpul dengan $V_1$ mewakili orang dan $V_2$ mewakili aplikasi. Simpul $x$ di $V_1$ dan simpul $y$ di $V_2$ bertetangga jika $x$ mempelajari aplikasi $y.$
Mencari pemadanan berarti mencari subhimpunan sisi $\mathbb{E}$ sehingga setiap simpul di $V_1$ bertetangga dengan simpul lain di $V_2$ oleh satu sisi saja. Ada pemadanan yang mungkin terbentuk seperti yang ditandai dengan sisi berwarna biru pada model graf di atas. Dalam kasus ini, aplikasi $5$ hanya dapat dipelajari oleh $E$ sehingga sisi $\{E, 5\}$ ditandai. Kemudian, aplikasi $4$ berarti hanya dapat dipelajari oleh $C$ karena $E$ sudah mempelajari aplikasi lain. Sisi $\{C, 4\}$ ditandai. Aplikasi $3$ jelas hanya dapat dipelajari oleh $D$ sehingga sisi $\{D, 3\}$ ditandai. Selanjutnya, aplikasi $1$ hanya dapat dipelajari oleh $A$ karena $C$ sudah mempelajari aplikasi lain. Sisi $\{A, 1\}$ ditandai. Terakhir, $B$ mempelajari aplikasi $2$ sehingga sisi $\{B, 2\}$ ditandai. Jadi, pemadanan yang dimaksud adalah $$\{\{A, 1\}, \{B, 2\}, \{C, 4\}, \{D, 3\}, \{E, 5\}\}.$$
Soal Nomor 11
Berapa banyak graf sederhana berbeda yang dapat dibangun dari himpunan simpul $\{1, 2, \cdots, n\}?$
Misalkan $G = (V, E)$ merupakan graf sederhana dengan himpunan simpul $V(G) = \{1, 2, \cdots, n\}.$ Agar memperoleh graf yang berbeda-beda, kita hanya perlu memilih apakah setiap dua simpul yang ada pada graf itu bertetangga atau tidak. Dengan kata lain, pertanyakan apakah ada sisi yang menghubungkan dua simpul berbeda pada graf tersebut.
Karena sisi menghubungkan dua simpul, banyaknya cara memilih $2$ dari $n$ simpul adalah $C(n, 2).$ Ini berarti banyak sisi maksimum pada $G$ adalah $C(n, 2).$ Dari $C(n, 2)$ sisi tersebut, kita punya dua pilihan: munculkan atau hilangkan. Sebagai contoh, jika $C(n, 2)$ sisi tersebut semuanya dimunculkan, kita akan memperoleh graf lengkap. Jika $C(n, 2)$ sisi tersebut semuanya dihilangkan, kita akan memperoleh graf kosong yang memuat $n$ simpul tanpa ada satu sisi pun.
Oleh karena itu, banyak graf sederhana berbeda yang dapat dibentuk adalah $\boxed{\underbrace{2 \times 2 \times 2 \times \cdots \times 2}_{\text{sebanyak}~C(n, 2)} = 2^{C(n, 2)}}$
Soal Nomor 12
Tentukan barisan derajat dari setiap graf berikut.
- Graf lengkap dengan $4$ simpul, dinotasikan oleh $K_4.$
- Siklus dengan $4$ simpul, dinotasikan dengan $C_4.$
- Roda dengan $5$ simpul, dinotasikan dengan $W_4.$
- Graf bipartit lengkap dengan himpunan partisi beranggotakan $2$ simpul dan $3$ simpul, dinotasikan dengan $K_{2, 3}.$
- Graf kubus $Q_3.$
Jawaban a)
Graf lengkap $K_4$ merupakan graf sederhana yang keempat simpulnya saling bertetangga satu sama lain. Dengan demikian, masing-masing simpulnya akan berderajat $3.$
Jadi, barisan derajat dari $K_4$ adalah $(3, 3, 3, 3).$
Jawaban b)
Graf siklus $C_4$ merupakan graf sederhana yang membentuk siklus dengan $4$ simpul (dapat dibentuk sehingga menjadi berbentuk persegi). Dengan demikian, masing-masing simpulnya akan berderajat $2.$
Jadi, barisan derajat dari $C_4$ adalah $(2, 2, 2, 2).$
Jawaban c)
Graf roda $W_4$ merupakan graf siklus $C_4$ yang ditambahkan dengan simpul kelima sehingga setiap simpul dari $C_4$ bertetangga dengan simpul kelima ini. Dengan demikian, masing-masing simpul dari $C_4$ akan berderajat $3+1 = 4$ dan simpul kelima itu akan berderajat $4$ karena bertetangga dengan $4$ simpul pembentuk $C_4.$
Jadi, barisan derajat dari $K_4$ adalah $(4, 4, 4, 4, 4).$
Jawaban d)
Graf bipartit lengkap $K_{2, 3}$ merupakan graf bipartit yang himpunan partisinya terdiri dari $2$ simpul dan $3$ simpul serta setiap simpul pada himpunan partisi pertama bertetangga dengan setiap simpul pada himpunan partisi yang lain. Dengan demikian, akan ada $2$ simpul yang berderajat $3$ dan $3$ simpul yang berderajat $2.$
Jadi, barisan derajat dari $K_{2, 3}$ adalah $(3, 3, 2, 2, 2).$
Jawaban e)
Graf kubus $Q_3$ dimodelkan seperti kubus (tiga dimensi) dengan titik sudut sebagai simpul graf dan rusuk kubus sebagai sisi graf. Simpul $Q_3$ ada sebanyak $2^3 = 8.$ Setiap simpul akan bertetangga dengan $3$ simpul lainnya. Dengan demikian, masing-masing simpulnya akan berderajat $3.$
Jadi, barisan derajat dari $Q_3$ adalah $(3, 3, 3, 3, 3, 3, 3, 3).$