Materi, Soal, dan Pembahasan – Operasi pada Graf dan Konsep Subgraf

Graf merupakan struktur diskrit yang disusun dari himpunan simpul dan himpunan sisi. Karena dibangun dari dua himpunan, graf juga dapat dipandang sebagai himpunan. Oleh karena itu, sejumlah operasi himpunan juga didefinisikan sebagai operasi pada graf, antara lain operasi gabungan, irisan, dan komplemen.  Kemudian, graf yang memuat beberapa simpul dan beberapa sisi dari graf lain dinamakan subgraf, yang notaebene juga merupakan konsep himpunan. Meskipun ada kemiripan, ada beberapa karakteristik unik yang dimiliki oleh graf ketika kita menelaahnya lebih jauh. 

Pertama, kita definisikan terlebih dahulu operasi gabungan, irisan, dan komplemen pada graf.

Definisi: Operasi Gabungan dari Graf

Misalkan $G = (V(G), E(G))$ dan $H = ((V(H), E(H))$ merupakan graf sederhana. Gabungan (union) dari $G$ dan $H,$ dinotasikan $G \cup H,$ merupakan graf dengan himpunan simpul $V(G) \cup V(H)$ dan himpunan sisi $E(G) \cup E(H).$ Secara matematis, ditulis $$G \cup H = (V(G) \cup V(H), E(G) \cup E(H)).$$

Berikut ini merupakan dua contoh graf $G$ dan $H$ serta gabungannya.

Lebih lanjut, jika simpul dan sisi pada dua graf berbeda tidak diberi label, kita asumsikan himpunan simpul dan himpunan sisi dari dua graf tersebut saling lepas (disjoint). Akibatnya, hasil operasi gabungan dua graf tersebut berupa graf baru yang memuat semua simpul dan sisi yang ada, seperti contoh berikut.

Definisi: Operasi Irisan dari Graf

Misalkan $G = (V(G), E(G))$ dan $H = ((V(H), E(H))$ merupakan graf sederhana. Irisan (intersection) dari $G$ dan $H,$ dinotasikan $G \cap H,$ merupakan graf dengan himpunan simpul $V(G) \cap V(H)$ dan himpunan sisi $E(G) \cap E(H).$ Secara matematis, ditulis $$G \cap H = (V(G) \cap V(H), E(G) \cap E(H)).$$

Berikut ini merupakan dua contoh graf $G$ dan $H$ serta irisannya.

Definisi: Graf Komplemen

Graf komplemen (complementary graph) $\overline{G} = (V, \overline{E})$ dari suatu graf sederhana $G = (V, E)$ merupakan graf yang himpunan simpulnya sama dengan $V(G),$ tetapi dua simpul di $\overline{G}$ bertetangga jika dua simpul tersebut di $G$ tidak bertetangga, begitu juga sebaliknya.

Berikut ini merupakan dua contoh graf dan komplemennya.
Beberapa fakta penting yang berkenaan dengan graf komplemen diberikan sebagai berikut.

  1. Komplemen dari setiap graf trivial adalah graf trivial itu sendiri.
  2. Komplemen dari setiap graf kosong dengan $n \ge 2$ simpul adalah graf lengkap dengan $n$ simpul.
  3. Gabungan dari suatu graf dengan graf komplemennya menghasilkan graf lengkap dengan $n$ simpul.
  4. Irisan dari suatu graf dengan graf komplemennya menghasilkan graf kosong dengan $n$ simpul.

Subgraf didefinisikan dengan menggunakan konsep subhimpunan pada simpul dan sisinya.

Definisi: Subgraf

Graf $H = (V(H), E(H))$ dikatakan sebagai subgraf (subgraph) dari graf $G = (V(G), E(G))$ jika $V(H) \subseteq V(G)$ dan $E(H) \subseteq E(G).$

Perhatikan model graf berikut.

Graf $H$ merupakan subgraf dari $G.$ Hal ini bisa dilihat dari himpunan simpulnya yang merupakan subhimpunan dari himpunan simpul di $G,$ begitu juga dengan himpunan sisinya. Dapat dikatakan bahwa graf $H$ didapat dengan cara menghilangkan simpul $e$ dan sisi yang bersisian dengannya serta menghilangkan salah satu sisi penghubung $a$ dan $b.$ Sebaliknya, graf $L$ berikut bukan subgraf dari $G$ karena ada simpul baru $z$ dan sisi $dz$ yang tidak dimuat di $G.$

Definisi: Subgraf Merentang

Graf $H = (V(H), E(H))$ dikatakan sebagai subgraf merentang (spanning subgraph) dari graf $G = (V(G), E(G))$ jika $V(H) = V(G)$ dan $E(H) \subseteq E(G).$

Dari definisi di atas, kita tahu bahwa semua subgraf merentang merupakan subgraf, tetapi tidak semua subgraf merupakan subgraf merentang. Perhatikan model graf berikut.
Graf $H, I,$ dan $J$ ketiganya merupakan subgraf dari $G.$ Secara spesifik, graf $H$ dan $J$ merupakan subgraf merentang dari $G$ karena simpulnya tidak dihilangkan sama sekali dari $G.$ Namun, graf $J$ bukan subgraf merentang karena ada satu simpul yang dihilangkan.

Definisi: Subgraf Terinduksi Simpul

Graf $H$ dikatakan subgraf terinduksi simpul (vertex-induced subgraph) dari graf $G$ jika graf $H$ dibangun dari subhimpunan simpul dari $G$ serta sisi yang menghubungkannya. Subgraf terinduksi simpul kadang juga disebut lebih singkat sebagai subgraf terinduksi (induced subgraph). Secara matematis, jika subgraf terinduksi simpul dari suatu graf $G$ dibangun dari simpul $\{v_1, v_2, \cdots, v_i\},$ notasi yang digunakan untuk menyatakan subgraf terinduksi simpul tersebut adalah $G[\{v_1, v_2, \cdots, v_i\}].$

Sebagai contoh, perhatikan empat model graf berikut.

$G_2, G_3,$ dan $G_4$ ketiganya merupakan subgraf dari $G_1.$ Lebih lanjut, $G_2$ dan $G_3$ keduanya merupakan subgraf terinduksi simpul dari $G_1$ karena setiap dua simpul yang termuat di masing-masing graf tersebut, ada sisi yang menghubungkannya sebagaimana mereka juga bertetangga di graf $G_1.$ Namun, $G_4$ bukan subgraf terinduksi simpul dari $G_1$ karena tidak ada sisi yang menghubungkan dua simpul yang ditandai dengan warna biru, padahal di graf $G_1,$ dua simpul ini bertetangga.

Contoh lain diberikan sebagai berikut.
Graf $H_2$ dan $H_3$ keduanya merupakan subgraf terinduksi simpul dari $G_1.$ Lebih lanjut, subgraf terinduksi simpul yang membentuk graf lengkap disebut sebagai klik (clique). Graf lengkap adalah graf sederhana yang setiap simpulnya bertetangga dengan simpul lainnya. Graf $H_2$ di atas merupakan klik dari $H_1.$ Namun, $H_3$ bukan klik dari $H_1$ karena tidak memenuhi definisi graf lengkap (harus berupa graf sederhana; tidak boleh memuat sisi rangkap).

Definisi: Subgraf Terinduksi Sisi

Graf $H$ dikatakan subgraf terinduksi sisi (edge-induced subgraph) dari graf $G$ jika graf $H$ dibangun dari subhimpunan sisi dari $G$ dan harus memuat simpul ujung sisi tersebut. Secara matematis, jika subgraf terinduksi sisi dari suatu graf $G$ dibangun dari sisi $\{e_1, e_2, \cdots, e_i\},$ notasi yang digunakan untuk menyatakan subgraf terinduksi sisi tersebut adalah $G[\{e_1, e_2, \cdots, e_i\}].$

Sebagai contoh, perhatikan tiga model graf berikut.
Graf $K_2$ dan $K_3$ keduanya merupakan subgraf terinduksi sisi dari $K_1.$ Lebih lanjut, $K_2$ juga merupakan subgraf terinduksi simpul dari $K_1,$ tetapi $K_3$ bukan karena ada dua simpul yang tidak bertetangga, padahal dua simpul ini bertetangga di $K_1.$

Di bawah ini telah disediakan sejumlah soal dan pembahasan tentang operasi graf dan konsep subgraf. Sebagian soal dibuat oleh penulis sendiri dan sebagian lainnya diadaptasi dari literatur.


Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber 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 Komplemen} & \text{Complementary Graph} \\ 2. & \text{Subgraf} & \text{Subgraph} \\ 3. & \text{Subgraf Merentang} & \text{Spanning Subgraph} \\ 4. & \text{Subgraf Terinduksi Simpul} & \text{Vertex-Induced Subgraph} \\ 5. & \text{Subgraf Terinduksi Sisi} & \text{Edge-Induced Subgraph} \\ 6. & \text{Klik} & \text{Clique} \\ \hline \end{array}$$


Today Quote

Bergebulah dan berapi-apilah di masa mudamu. Kobarkan semangat membara bak sang pahlawan. Masa muda adalah masa yang tidak boleh dilewatkan dengan malas-malasan.

Baca: Istilah Lengkap dalam Teori Graf

Bagian Pilihan Ganda

Soal Nomor 1

Manakah dari graf berikut yang bukan subgraf dari graf $G$?
A. Graf $A.$                         D. Graf $D.$
B. Graf $B.$                         E. Graf $E.$
C. Graf $C.$

Pembahasan

Graf $A, B, D,$ dan $E$ keempatnya merupakan subgraf dari $G$ karena setiap simpul dan setiap sisinya termuat di $G$ sesuai definisi subgraf.  Sebaliknya, graf $C$ bukan subgraf dari $G$ karena graf $C$ memuat satu sisi tambahan (yang posisinya vertikal), padahal sisi itu tidak dimuat di $G.$
(Jawaban C)

[collapse]

Soal Nomor 2

Banyak subgraf yang memuat setidaknya satu simpul dari graf lengkap $K_2$ adalah $\cdots \cdot$
A. $2$                      C. $4$                    E. $8$
B. $3$                      D. $6$

Pembahasan

Graf lengkap $K_2$ memiliki dua simpul dan satu sisi yang menghubungkan dua simpul tersebut. Tinjau dua kasus terkait banyak simpul yang dimiliki oleh subgrafnya.

  1. Jika banyak simpul subgraf dari $K_2$ sama dengan $1,$ jelas hanya ada $2$ subgraf berbeda yang dapat dibuat, masing-masing merupakan graf trivial dengan menggunakan dua simpul yang berbeda.
  2. Jika banyak simpul subgraf dari $K_2$ sama dengan $2,$ ada $2$ subgraf berbeda yang dapat dibuat, yaitu graf yang memuat dua simpul bertetangga dan graf yang memuat dua simpul yang sama, tetapi takbertetangga.

Jadi, secara keseluruhan, ada $\boxed{4}$ subgraf yang memuat setidaknya satu simpul dari graf lengkap $K_2.$
(Jawaban C)

[collapse]

Soal Nomor 3

Banyak subgraf yang memuat setidaknya satu simpul dari graf lengkap $K_3$ adalah $\cdots \cdot$
A. $14$                     C. $17$                     E. $23$
B. $16$                     D. $21$

Pembahasan

Graf lengkap $K_3$ memiliki tiga simpul yang saling bertetangga. Tinjau tiga kasus terkait banyak simpul yang dimiliki oleh subgrafnya.

  1. Jika banyak simpul subgraf dari $K_3$ sama dengan $1,$ jelas hanya ada $3$ subgraf berbeda yang dapat dibuat, masing-masing merupakan graf trivial dengan menggunakan tiga simpul yang berbeda.
  2. Jika banyak simpul subgraf dari $K_3$ sama dengan $2,$ terdapat $C(3, 2) = \color{red}{3}$ cara memilih $2$ dari $3$ simpulnya dan ada $\color{red}{2}$ cara untuk memilih apakah dua simpul itu terhubung oleh sisi atau tidak. Jadi, ada $3 \times 2 = 6$ subgraf yang dapat dibuat.
  3. Jika banyak simpul subgraf dari $K_3$ sama dengan $3,$ terdapat $2^3 = 8$ cara untuk memilih apakah setiap dua simpul terhubung oleh sisi atau tidak. Jadi, ada $8$ subgraf yang dapat dibuat.

Jadi, secara keseluruhan, ada $\boxed{3+6+8=17}$ subgraf yang memuat setidaknya satu simpul dari graf lengkap $K_3.$
(Jawaban C)

[collapse]

Soal Nomor 4

Banyak subgraf yang memuat setidaknya satu simpul dari graf sederhana berikut adalah $\cdots \cdot$
A. $40$                    C. $34$                    E. $22$
B. $35$                     D. $28$

Pembahasan

Dari model graf sederhana di atas, dapat ditinjau dua kasus berikut: (1) simpul $a$ dihilangkan dan (2) simpul $a$ tetap ada.

  1. Jika simpul $a$ dihilangkan, semua sisi graf tersebut juga akan dihilangkan. Akibatnya, kita sekarang hanya memiliki tiga simpul untuk membuat subgraf. Banyak subgraf yang dapat dibuat dengan $1, 2,$ dan $3$ simpul berturut-turut adalah $3, 3,$ dan $1.$
  2. Jika simpul $a$ tetap ada, maka untuk setiap simpul $x \in \{b, c, d\},$ kita dapat melakukan tiga tindakan berikut.

      1. Simpul $x$ dan sisi $\{a, x\}$ tetap ada.
      2. Simpul $x$ tetap ada, tetapi sisi $\{a, x\}$ dihilangkan.
      3. Simpul $x$ dan sisi $\{a, x\}$ dihilangkan.

    Ini berarti ada $3^3 = 27$ subgraf yang dapat dibuat.

Jadi, secara keseluruhan, ada $\boxed{7 + 27 = 34}$ subgraf yang memuat setidaknya satu simpul dari graf sederhana tersebut.
(Jawaban C)

[collapse]

Soal Nomor 5

Banyak subgraf merentang berbeda dari graf $Z$ berikut adalah $\cdots \cdot$
A. $8$                               D. $512$
B. $64$                             E. $1.024$
C. $196$

Pembahasan

Subgraf merentang dari graf $Z$ adalah subgraf yang memuat semua simpul dari $Z.$ Ini berarti yang menentukan beda subgraf yang satu dengan subgraf yang lain adalah eksistensi sisinya. Kita punya dua pilihan pada masing-masing sisi, yaitu sisi itu tetap ada dalam subgraf atau dihilangkan. Karena ada $9$ sisi pada graf $Z,$ akan ada $2^{9} = 512$ kemungkinan terkait ada tidaknya sisi penghubung simpul. Dengan kata lain, ada $\boxed{512}$ subgraf merentang berbeda dari graf $Z.$
(Jawaban D)

[collapse]

Soal Nomor 6

Jika $G$ merupakan graf sederhana dengan $15$ sisi dan $\overline{G}$ memiliki $13$ sisi, maka banyak simpul pada $G$ adalah $\cdots \cdot$
A. $2$                       C. $6$                     E. $12$
B. $4$                       D. $8$

Pembahasan

Gabungan dari graf sederhana $G$ dan komplemennya, $\overline{G},$ adalah graf lengkap.
Karena $G$ memiliki $15$ sisi dan $\overline{G}$ memiliki $13$ sisi, gabungan kedua graf ini merupakan graf lengkap dengan $15+13 = 28$ sisi. Pada graf lengkap, hubungan banyak simpul $(v)$ dan sisinya $(e)$ dinyatakan oleh $e = \dfrac{v(v-1)}{2}.$ Karena $e = 28,$ diperoleh $v = 8.$ Jadi, banyak simpul pada $G$ (begitu juga dengan $\overline{G})$ adalah $\boxed{8}$
(Jawaban D)

[collapse]

Soal Nomor 7

Jika graf sederhana $G$ memiliki $v$ simpul dan $e$ sisi, maka $\overline{G}$ memiliki sisi sebanyak $\cdots \cdot$
A. $e-\dfrac{v(v-1)}{2}$                  D. $\dfrac{e(e-1)}{2}-v$
B. $\dfrac{v(v-1)}{2}-e$                  E. $\dfrac{e(e-1)}{2}+v$
C. $\dfrac{v(v-1)}{2}+e$

Pembahasan

Misalkan graf sederhana $G$ memiliki $v$ simpul dan $e$ sisi. Misalkan juga $\overline{G}$ memiliki $f$ sisi. Jika dua graf tersebut digabungkan, diperoleh graf lengkap dengan $v$ simpul dan $(e + f)$ sisi. Hubungan banyak simpul $(v)$ dan banyak sisinya $(e + f)$ dinyatakan oleh $$e + f = \dfrac{v(v-1)}{2}.$$Ini berarti $$f = \dfrac{v(v-1)}{2}-e.$$Jadi, banyak sisi pada $\overline{G}$ adalah $\boxed{\dfrac{v(v-1)}{2}-e}$
(Jawaban B)

[collapse]

Soal Nomor 8

Perhatikan model graf berikut.
Model graf di atas merepresentasikan subgraf (yang diberi warna hitam tebal) dari suatu graf $G.$ Agar subgraf tersebut menjadi subgraf terinduksi simpul $G[\{v_1, v_2, v_3, v_4, v_5\}],$ simpul atau sisi yang harus ditambahkan adalah $\cdots \cdot$

  1. simpul $v_6$ dan simpul $v_7$
  2. sisi $v_1v_3$ dan sisi $v_1v_4$
  3. sisi $v_4v_5$
  4. simpul $v_6,$ simpul $v_7,$ sisi $v_5v_6,$ dan sisi $v_4v_7$
  5. sisi $v_4v_5$ dan simpul $v_6$

Pembahasan

Subgraf terinduksi simpul dibangun dari sejumlah simpul dari suatu graf beserta sisi penghubung simpul-simpul tersebut. Perhatikan bahwa subgraf dari $G$ pada gambar di atas bukan subgraf terinduksi simpul karena tidak ada sisi penghubung simpul $v_4$ dan $v_5.$  Jadi, agar diperoleh subgraf terinduksi simpul yang dibangun oleh simpul $v_1, v_2,$ $v_3, v_4,$ dan $v_5,$ dinotasikan $G[\{v_1, v_2, v_3, v_4, v_5\}],$ sisi yang perlu ditambahkan adalah sisi $v_4v_5.$
(Jawaban C)

[collapse]

Soal Nomor 9

Perhatikan model graf $G$ berikut.
Subgraf terinduksi simpul dari $G$ yang membentuk klik adalah $\cdots \cdot$
A. $G[\{v_1, v_2, v_6\}]$
B. $G[\{v_1, v_3, v_5\}]$
C. $G[\{v_2, v_3, v_5, v_6\}]$
D. $G[\{v_2, v_4, v_6\}]$
E. $G[\{v_1, v_2, v_3, v_4, v_5, v_6\}]$

Pembahasan

Subgraf terinduksi simpul dari $G$ dibangun dari beberapa simpul $G$ dan sisi yang bersisian dengan setiap dua simpul tersebut. Klik adalah subgraf terinduksi simpul yang berupa graf lengkap, yaitu graf sederhana yang setiap simpulnya saling bertetangga. Perhatikan bahwa subgraf terinduksi simpul dari $G$ yang dibangun oleh tiga simpul $v_1, v_2,$ dan $v_6$ (membentuk seperti bangun segitiga) merupakan klik karena berupa graf lengkap dengan $3$ simpul. Subgraf terinduksi simpul yang diberikan pada opsi B, C, D, dan E tidak membentuk klik karena setidaknya ada dua simpul pembangunnya yang tidak bertetangga. Sebagai contoh, subgraf terinduksi simpul $G[\{v_1, v_3, v_5\}]$ tidak membentuk klik karena $v_1$ dan $v_3$ tidak bertetangga, begitu juga dengan $v_1$ dan $v_5.$
(Jawaban A)

[collapse]

Bagian Uraian

Soal Nomor 1

Buktikan bahwa jika $G$ merupakan graf sederhana dengan $n$ simpul, maka gabungan $G$ dan $\overline{G}$ adalah $K_n$ (graf lengkap dengan $n$ simpul).

Pembahasan

Misalkan $G$ merupakan graf sederhana dengan $n$ simpul. Tinjau graf $G \cup \overline{G}.$ Himpunan simpulnya sama dengan himpunan simpul $G$ sesuai dengan definisi graf komplemen. Jika $u$ dan $v$ merupakan dua simpul berbeda sembarang dari $G \cup \overline{G},$ maka sisi penghubung $u$ dan $v$ berada di $G$ atau berdasarkan definisi graf komplemen, di $\overline{G}.$ Berdasarkan definisi gabungan himpunan, sisinya pasti di $G \cup \overline{G}.$ Oleh karena itu, setiap simpul terhubung satu sama lain oleh sisi. Dengan demikian, graf $G \cup \overline{G}$ merupakan graf lengkap $K_n.$ Jadi, proposisi tersebut terbukti benar. $\blacksquare$

[collapse]

Soal Nomor 2

Buktikan bahwa jika $G$ merupakan graf sederhana dengan $n$ simpul, maka irisan $G$ dan $\overline{G}$ adalah graf kosong dengan $n$ simpul.

Pembahasan

Misalkan $G$ merupakan graf sederhana dengan $n$ simpul. Tinjau graf $G \cap \overline{G}.$ Himpunan simpulnya sama dengan himpunan simpul $G$ sesuai dengan definisi graf komplemen. Jika $u$ dan $v$ merupakan dua simpul berbeda sembarang dari $G \cap \overline{G}.$ maka sisi penghubung $u$ dan $v$ harus berada di $G$ dan $\overline{G}$ sekaligus. Namun, hal itu tidak mungkin terjadi karena bertentangan dengan definisi graf komplemen. Akibatnya, tidak ada satu pun sisi yang menghubungkan dua simpul di $G \cap \overline{G}.$ Dengan kata lain, $G \cap \overline{G}$ hanya memuat $n$ simpul tanpa ada sisi sehingga tergolong sebagai graf kosong.
Jadi, proposisi tersebut terbukti benar. $\blacksquare$

[collapse]

Soal Nomor 3

Graf komplemen $\overline{G}$ dari graf sederhana $G$ memiliki simpul yang sama dengan $G.$ Dua simpul bertetangga di $\overline{G}$ jika keduanya tidak bertetangga di $G,$ begitu juga sebaliknya. Deskripsikan masing-masing graf berikut.
a. $\overline{K_n}$
b. $\overline{K_{m, n}}$
c. $\overline{C_n}$
d. $\overline{Q_n}$

Pembahasan

Jawaban a)
$K_n$ merupakan grup lengkap dengan $n$ simpul. Setiap simpul memiliki sisi pada setiap simpul lainnya. Akibatnya, setiap simpul di $\overline{G}$ tidak bertetangga dengan simpul apa pun. Ini berarti graf $\overline{G}$ merupakan graf kosong dengan $n$ simpul, yaitu graf yang hanya memuat $n$ simpul tanpa ada sisi sama sekali. Sebagai contoh, berikut diberikan model graf $K_6$ dan komplemennya.
Jawaban b)
$K_{m, n}$ merupakan graf bipartit lengkap yang himpunan simpulnya masing-masing memuat $m$ dan $n$ simpul. Setiap simpul pada satu himpunan bertetangga dengan setiap simpul pada himpunan lainnya dan tidak bertetangga dengan simpul pada himpunan yang sama. Akibatnya, simpul di $\overline{G}$ memiliki kriteria berikut: (1) setiap simpul pada himpunan yang sama saling bertetangga; (2) Tidak ada sisi yang menghubungkan simpul pada himpunan pertama ke simpul pada himpunan kedua. Sebagai contoh, berikut diberikan model graf $K_{2, 3}$ dan komplemennya.
Jawaban c)
$C_n$ merupakan siklus dengan $n$ simpul. Misalkan $v_1, v_2, \cdots, v_n$ merupakan simpul pembentuk siklus tersebut. Ini berarti $C_n = (v_1, v_2, \cdots, v_n, v_1)$ yang menyatakan bahwa simpul yang berdekatan berarti bertetangga. Pada graf komplemennya, setiap sisi menghubungkan simpul $v_i$ dan $v_j$ dengan $i \neq j + 1$ atau $i \ neq j-1$ untuk $1 \le i < j \le n.$ Sebagai contoh, berikut diberikan model graf $K_{2, 3}$ dan komplemennya.
Jawaban d)
$Q_n$ merupakan graf kubus dengan $2^n$ simpul. Dua simpul di $Q_n$ akan bertetangga jika untaian bit yang diwakilinya hanya berbeda satu bit pada posisi yang bersesuaian. Oleh karena itu, pada graf komplemennya, dinotasikan $\overline{Q_n},$ dua simpul akan bertetangga jika untaian bit yang diwakilinya berbeda lebih dari satu bit pada posisi yang bersesuaian.

[collapse]

0 0 votes
Article Rating

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini jika ada kesalahan pengetikan sekecil apa pun, seperti kesalahan pengetikan, kode LaTeX yang tidak berjalan, atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Subscribe
Notify of
guest

1 Comment
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
Fani Rahmawati Husna

Sangat membantu

1
0
Would love your thoughts, please comment.x
()
x