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

Operasi pada graf dan konsep subgraf

Graf merupakan struktur diskret 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. 

Artikel tentang Graf

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 GH, merupakan graf dengan himpunan simpul V(G)V(H) dan himpunan sisi E(G)E(H). Secara matematis, ditulis GH=(V(G)V(H),E(G)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 GH, merupakan graf dengan himpunan simpul V(G)V(H) dan himpunan sisi E(G)E(H). Secara matematis, ditulis GH=(V(G)V(H),E(G)E(H)).

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

Definisi: Graf Komplemen

Graf komplemen (complementary graph) G=(V,E) dari suatu graf sederhana G=(V,E) merupakan graf yang himpunan simpulnya sama dengan V(G), tetapi dua simpul di 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 n2 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)V(G) dan E(H)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)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 {v1,v2,,vi}, notasi yang digunakan untuk menyatakan subgraf terinduksi simpul tersebut adalah G[{v1,v2,,vi}].

Sebagai contoh, perhatikan empat model graf berikut.

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

Contoh lain diberikan sebagai berikut.
Graf H2 dan H3 keduanya merupakan subgraf terinduksi simpul dari G1. 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 H2 di atas merupakan klik dari H1. Namun, H3 bukan klik dari H1 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 {e1,e2,,ei}, notasi yang digunakan untuk menyatakan subgraf terinduksi sisi tersebut adalah G[{e1,e2,,ei}].

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

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.

Jika Anda ingin mencari soal latihan yang lebih banyak, Anda dapat mengakses ke folder soal mathcyber1997.com dengan mendaftar di bit.ly/Akses_SoalFolder soal tersebut berisi soal UTBK-SNBT, soal persiapan CPNS-PPPK, soal psikotes, soal TPA, soal ujian masuk perguruan tinggi (termasuk STAN), soal kompetensi matematika (termasuk OSN dan ON MIPA), dan masih banyak lagi.


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.

No.Bahasa IndonesiaBahasa Inggris1.Graf KomplemenComplementary Graph2.SubgrafSubgraph3.Subgraf MerentangSpanning Subgraph4.Subgraf Terinduksi SimpulVertex-Induced Subgraph5.Subgraf Terinduksi SisiEdge-Induced Subgraph6.KlikClique


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

Soal Nomor 2

Banyak subgraf yang memuat setidaknya satu simpul dari graf lengkap K2 adalah
A. 2                      C. 4                    E. 8
B. 3                      D. 6

Pembahasan

Soal Nomor 3

Banyak subgraf yang memuat setidaknya satu simpul dari graf lengkap K3 adalah
A. 14                     C. 17                     E. 23
B. 16                     D. 21

Pembahasan

Soal Nomor 4

Banyak subgraf yang memuat setidaknya satu simpul dari graf sederhana berikut adalah
A. 40                       C. 34                    E. 22

B. 35                     D. 28

Pembahasan

Soal Nomor 5

Banyak subgraf merentang berbeda dari graf Z berikut adalah
A. 8                               D. 512

B. 64                             E. 1.024
C. 196

Pembahasan

Soal Nomor 6

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

Pembahasan

Soal Nomor 7

Jika graf sederhana G memiliki v simpul dan e sisi, maka G memiliki sisi sebanyak
A. ev(v1)2                
B. v(v1)2e                
C. v(v1)2+e
D. e(e1)2v
E. e(e1)2+v

Pembahasan

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[{v1,v2,v3,v4,v5}], simpul atau sisi yang harus ditambahkan adalah

  1. simpul v6 dan simpul v7
  2. sisi v1v3 dan sisi v1v4
  3. sisi v4v5
  4. simpul v6, simpul v7, sisi v5v6, dan sisi v4v7
  5. sisi v4v5 dan simpul v6

Pembahasan

Soal Nomor 9

Perhatikan model graf G berikut.
Subgraf terinduksi simpul dari G yang membentuk klik adalah
A. G[{v1,v2,v6}]
B. G[{v1,v3,v5}]
C. G[{v2,v3,v5,v6}]
D. G[{v2,v4,v6}]
E. G[{v1,v2,v3,v4,v5,v6}]

Pembahasan

Soal Nomor 10

Suatu graf sederhana G memiliki barisan derajat (3,2,2,2,1). Barisan derajat dari graf komplemennya, G, adalah
A. (3,2,2,2,1)
B. (4,3,3,3,2)
C. (2,1,1,1,0)
D. (3,2,2,1,1)
E. (3,2,1,1,1)

Pembahasan

Bagian Uraian

Soal Nomor 1

Buktikan bahwa jika G merupakan graf sederhana dengan n simpul, maka gabungan G dan G adalah Kn (graf lengkap dengan n simpul).

Pembahasan

Soal Nomor 2

Buktikan bahwa jika G merupakan graf sederhana dengan n simpul, maka irisan G dan G adalah graf kosong dengan n simpul.

Pembahasan

Soal Nomor 3

Graf komplemen G dari graf sederhana G memiliki simpul yang sama dengan G. Dua simpul bertetangga di G jika keduanya tidak bertetangga di G, begitu juga sebaliknya. Deskripsikan masing-masing graf berikut.
a. Kn
b. Km,n
c. Cn
d. Qn

Pembahasan

Soal Nomor 4

Jika barisan derajat dari graf sederhana G adalah (d1,d2,,dn), tentukan barisan derajat dari G.

Pembahasan