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 dan merupakan graf sederhana. Gabungan (union) dari dan dinotasikan merupakan graf dengan himpunan simpul dan himpunan sisi Secara matematis, ditulis
Berikut ini merupakan dua contoh graf dan 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 dan merupakan graf sederhana. Irisan (intersection) dari dan dinotasikan merupakan graf dengan himpunan simpul dan himpunan sisi Secara matematis, ditulis
Berikut ini merupakan dua contoh graf dan serta irisannya.

Definisi: Graf Komplemen
Graf komplemen (complementary graph) dari suatu graf sederhana merupakan graf yang himpunan simpulnya sama dengan tetapi dua simpul di bertetangga jika dua simpul tersebut di tidak bertetangga, begitu juga sebaliknya.
Berikut ini merupakan dua contoh graf dan komplemennya.
Beberapa fakta penting yang berkenaan dengan graf komplemen diberikan sebagai berikut.
- Komplemen dari setiap graf trivial adalah graf trivial itu sendiri.
- Komplemen dari setiap graf kosong dengan simpul adalah graf lengkap dengan simpul.
- Gabungan dari suatu graf dengan graf komplemennya menghasilkan graf lengkap dengan simpul.
- Irisan dari suatu graf dengan graf komplemennya menghasilkan graf kosong dengan simpul.
Subgraf didefinisikan dengan menggunakan konsep subhimpunan pada simpul dan sisinya.
Definisi: Subgraf
Graf dikatakan sebagai subgraf (subgraph) dari graf jika dan
Perhatikan model graf berikut.

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

Definisi: Subgraf Merentang
Graf dikatakan sebagai subgraf merentang (spanning subgraph) dari graf jika dan
Dari definisi di atas, kita tahu bahwa semua subgraf merentang merupakan subgraf, tetapi tidak semua subgraf merupakan subgraf merentang. Perhatikan model graf berikut.
Graf dan ketiganya merupakan subgraf dari Secara spesifik, graf dan merupakan subgraf merentang dari karena simpulnya tidak dihilangkan sama sekali dari Namun, graf bukan subgraf merentang karena ada satu simpul yang dihilangkan.
Definisi: Subgraf Terinduksi Simpul
Graf dikatakan subgraf terinduksi simpul (vertex-induced subgraph) dari graf jika graf dibangun dari subhimpunan simpul dari 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 dibangun dari simpul notasi yang digunakan untuk menyatakan subgraf terinduksi simpul tersebut adalah
Sebagai contoh, perhatikan empat model graf berikut.

dan ketiganya merupakan subgraf dari Lebih lanjut, dan keduanya merupakan subgraf terinduksi simpul dari karena setiap dua simpul yang termuat di masing-masing graf tersebut, ada sisi yang menghubungkannya sebagaimana mereka juga bertetangga di graf Namun, bukan subgraf terinduksi simpul dari karena tidak ada sisi yang menghubungkan dua simpul yang ditandai dengan warna biru, padahal di graf dua simpul ini bertetangga.
Contoh lain diberikan sebagai berikut.
Graf dan keduanya merupakan subgraf terinduksi simpul dari 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 di atas merupakan klik dari Namun, bukan klik dari karena tidak memenuhi definisi graf lengkap (harus berupa graf sederhana; tidak boleh memuat sisi rangkap).
Definisi: Subgraf Terinduksi Sisi
Graf dikatakan subgraf terinduksi sisi (edge-induced subgraph) dari graf jika graf dibangun dari subhimpunan sisi dari dan harus memuat simpul ujung sisi tersebut. Secara matematis, jika subgraf terinduksi sisi dari suatu graf dibangun dari sisi notasi yang digunakan untuk menyatakan subgraf terinduksi sisi tersebut adalah
Sebagai contoh, perhatikan tiga model graf berikut.
Graf dan keduanya merupakan subgraf terinduksi sisi dari Lebih lanjut, juga merupakan subgraf terinduksi simpul dari tetapi bukan karena ada dua simpul yang tidak bertetangga, padahal dua simpul ini bertetangga di
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_Soal. Folder 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.
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 ?
A. Graf D. Graf
B. Graf E. Graf
C. Graf
Pembahasan
Graf dan keempatnya merupakan subgraf dari karena setiap simpul dan setiap sisinya termuat di sesuai definisi subgraf. Sebaliknya, graf bukan subgraf dari karena graf memuat satu sisi tambahan (yang posisinya vertikal), padahal sisi itu tidak dimuat di
(Jawaban C)
[collapse]
Soal Nomor 2
Banyak subgraf yang memuat setidaknya satu simpul dari graf lengkap adalah
A. C. E.
B. D.
Pembahasan
Graf lengkap memiliki dua simpul dan satu sisi yang menghubungkan dua simpul tersebut. Tinjau dua kasus terkait banyak simpul yang dimiliki oleh subgrafnya.
- Jika banyak simpul subgraf dari sama dengan jelas hanya ada subgraf berbeda yang dapat dibuat, masing-masing merupakan graf trivial dengan menggunakan dua simpul yang berbeda.
- Jika banyak simpul subgraf dari sama dengan ada 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 subgraf yang memuat setidaknya satu simpul dari graf lengkap
(Jawaban C)
[collapse]
Soal Nomor 3
Banyak subgraf yang memuat setidaknya satu simpul dari graf lengkap adalah
A. C. E.
B. D.
Pembahasan
Graf lengkap memiliki tiga simpul yang saling bertetangga. Tinjau tiga kasus terkait banyak simpul yang dimiliki oleh subgrafnya.
- Jika banyak simpul subgraf dari sama dengan jelas hanya ada subgraf berbeda yang dapat dibuat, masing-masing merupakan graf trivial dengan menggunakan tiga simpul yang berbeda.
- Jika banyak simpul subgraf dari sama dengan terdapat cara memilih dari simpulnya dan ada cara untuk memilih apakah dua simpul itu terhubung oleh sisi atau tidak. Jadi, ada subgraf yang dapat dibuat.
- Jika banyak simpul subgraf dari sama dengan terdapat cara untuk memilih apakah setiap dua simpul terhubung oleh sisi atau tidak. Jadi, ada subgraf yang dapat dibuat.
Jadi, secara keseluruhan, ada subgraf yang memuat setidaknya satu simpul dari graf lengkap
(Jawaban C)
[collapse]
Soal Nomor 4
Banyak subgraf yang memuat setidaknya satu simpul dari graf sederhana berikut adalah
A. C. E.
B. D.
Pembahasan
Dari model graf sederhana di atas, dapat ditinjau dua kasus berikut: (1) simpul dihilangkan dan (2) simpul tetap ada.
- Jika simpul dihilangkan, semua sisi graf tersebut juga akan dihilangkan. Akibatnya, kita sekarang hanya memiliki tiga simpul untuk membuat subgraf. Banyak subgraf yang dapat dibuat dengan dan simpul berturut-turut adalah dan
- Jika simpul tetap ada, maka untuk setiap simpul kita dapat melakukan tiga tindakan berikut.
-
- Simpul dan sisi tetap ada.
- Simpul tetap ada, tetapi sisi dihilangkan.
- Simpul dan sisi dihilangkan.
Ini berarti ada subgraf yang dapat dibuat.
Jadi, secara keseluruhan, ada subgraf yang memuat setidaknya satu simpul dari graf sederhana tersebut.
(Jawaban C)
[collapse]
Soal Nomor 5
Banyak subgraf merentang berbeda dari graf berikut adalah
A. D.
B. E.
C.
Pembahasan
Subgraf merentang dari graf adalah subgraf yang memuat semua simpul dari 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 sisi pada graf akan ada kemungkinan terkait ada tidaknya sisi penghubung simpul. Dengan kata lain, ada subgraf merentang berbeda dari graf
(Jawaban D)
[collapse]
Soal Nomor 6
Jika merupakan graf sederhana dengan sisi dan memiliki sisi, maka banyak simpul pada adalah
A. C. E.
B. D.
Pembahasan
Gabungan dari graf sederhana dan komplemennya, adalah graf lengkap.
Karena memiliki sisi dan memiliki sisi, gabungan kedua graf ini merupakan graf lengkap dengan sisi. Pada graf lengkap, hubungan banyak simpul dan sisinya dinyatakan oleh Karena diperoleh Jadi, banyak simpul pada (begitu juga dengan adalah
(Jawaban D)
[collapse]
Soal Nomor 7
Jika graf sederhana memiliki simpul dan sisi, maka memiliki sisi sebanyak
A.
B.
C.
D.
E.
Pembahasan
Misalkan graf sederhana memiliki simpul dan sisi. Misalkan juga memiliki sisi. Jika dua graf tersebut digabungkan, diperoleh graf lengkap dengan simpul dan sisi. Hubungan banyak simpul dan banyak sisinya dinyatakan oleh Ini berarti Jadi, banyak sisi pada adalah
(Jawaban B)
[collapse]
Soal Nomor 8
Perhatikan model graf berikut.
Model graf di atas merepresentasikan subgraf (yang diberi warna hitam tebal) dari suatu graf Agar subgraf tersebut menjadi subgraf terinduksi simpul simpul atau sisi yang harus ditambahkan adalah
- simpul dan simpul
- sisi dan sisi
- sisi
- simpul simpul sisi dan sisi
- sisi dan simpul
Pembahasan
Subgraf terinduksi simpul dibangun dari sejumlah simpul dari suatu graf beserta sisi penghubung simpul-simpul tersebut. Perhatikan bahwa subgraf dari pada gambar di atas bukan subgraf terinduksi simpul karena tidak ada sisi penghubung simpul dan Jadi, agar diperoleh subgraf terinduksi simpul yang dibangun oleh simpul dan dinotasikan sisi yang perlu ditambahkan adalah sisi
(Jawaban C)
[collapse]
Soal Nomor 9
Perhatikan model graf berikut.
Subgraf terinduksi simpul dari yang membentuk klik adalah
A.
B.
C.
D.
E.
Pembahasan
Subgraf terinduksi simpul dari dibangun dari beberapa simpul 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 yang dibangun oleh tiga simpul dan (membentuk seperti bangun segitiga) merupakan klik karena berupa graf lengkap dengan 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 tidak membentuk klik karena dan tidak bertetangga, begitu juga dengan dan
(Jawaban A)
[collapse]
Soal Nomor 10
Suatu graf sederhana memiliki barisan derajat Barisan derajat dari graf komplemennya, adalah
A.
B.
C.
D.
E.
Pembahasan
merupakan graf sederhana yang memiliki simpul. Oleh karena itu, derajat maksimum yang dapat dicapai oleh suatu simpul adalah yaitu ketika simpul tersebut bertetangga dengan setiap simpul lainnya. Tinjau simpul berderajat di yang artinya simpul tersebut bertetangga dengan dari simpul yang ada (selain dirinya sendiri). Berdasarkan definisi graf komplemen, simpul tersebut hanya akan bertetangga dengan simpul yang tidak bertetangga dengannya di Dengan cara yang serupa, kita akan memperoleh derajat simpul yang lain di yaitu tiga simpul berderajat dan satu simpul berderajat Dengan demikian, barisan derajat dari (urutkan dari yang paling tinggi) adalah
(Jawaban A)
[collapse]
Bagian Uraian
Soal Nomor 1
Buktikan bahwa jika merupakan graf sederhana dengan simpul, maka gabungan dan adalah (graf lengkap dengan simpul).
Pembahasan
Misalkan merupakan graf sederhana dengan simpul. Tinjau graf Himpunan simpulnya sama dengan himpunan simpul sesuai dengan definisi graf komplemen. Jika dan merupakan dua simpul berbeda sembarang dari maka sisi penghubung dan berada di atau berdasarkan definisi graf komplemen, di Berdasarkan definisi gabungan himpunan, sisinya pasti di Oleh karena itu, setiap simpul terhubung satu sama lain oleh sisi. Dengan demikian, graf merupakan graf lengkap Jadi, proposisi tersebut terbukti benar.
[collapse]
Soal Nomor 2
Buktikan bahwa jika merupakan graf sederhana dengan simpul, maka irisan dan adalah graf kosong dengan simpul.
Pembahasan
Misalkan merupakan graf sederhana dengan simpul. Tinjau graf Himpunan simpulnya sama dengan himpunan simpul sesuai dengan definisi graf komplemen. Jika dan merupakan dua simpul berbeda sembarang dari maka sisi penghubung dan harus berada di dan sekaligus. Namun, hal itu tidak mungkin terjadi karena bertentangan dengan definisi graf komplemen. Akibatnya, tidak ada satu pun sisi yang menghubungkan dua simpul di Dengan kata lain, hanya memuat simpul tanpa ada sisi sehingga tergolong sebagai graf kosong.
Jadi, proposisi tersebut terbukti benar.
[collapse]
Soal Nomor 3
Graf komplemen dari graf sederhana memiliki simpul yang sama dengan Dua simpul bertetangga di jika keduanya tidak bertetangga di begitu juga sebaliknya. Deskripsikan masing-masing graf berikut.
a.
b.
c.
d.
Pembahasan
Jawaban a)
merupakan grup lengkap dengan simpul. Setiap simpul memiliki sisi pada setiap simpul lainnya. Akibatnya, setiap simpul di tidak bertetangga dengan simpul apa pun. Ini berarti graf merupakan graf kosong dengan simpul, yaitu graf yang hanya memuat simpul tanpa ada sisi sama sekali. Sebagai contoh, berikut diberikan model graf dan komplemennya.
Jawaban b)
merupakan graf bipartit lengkap yang himpunan simpulnya masing-masing memuat dan 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 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 dan komplemennya.
Jawaban c)
merupakan siklus dengan simpul. Misalkan merupakan simpul pembentuk siklus tersebut. Ini berarti yang menyatakan bahwa simpul yang berdekatan berarti bertetangga. Pada graf komplemennya, setiap sisi menghubungkan simpul dan dengan atau untuk Sebagai contoh, berikut diberikan model graf dan komplemennya.
Jawaban d)
merupakan graf kubus dengan simpul. Dua simpul di akan bertetangga jika untaian bit yang diwakilinya hanya berbeda satu bit pada posisi yang bersesuaian. Oleh karena itu, pada graf komplemennya, dinotasikan dua simpul akan bertetangga jika untaian bit yang diwakilinya berbeda lebih dari satu bit pada posisi yang bersesuaian.
[collapse]
Soal Nomor 4
Jika barisan derajat dari graf sederhana adalah tentukan barisan derajat dari
Pembahasan
Misalkan barisan derajat dari graf sederhana adalah Karena memiliki simpul, derajat maksimum yang dapat dicapai adalah yaitu ketika suatu simpul bertetangga dengan setiap simpul lainnya. Dengan demikian, derajat dari suatu simpul di sama dengan dikurangi derajat simpul di sebagai akibat dari definisi graf komplemen. Perhatikan bahwa jika haruslah berlaku Oleh karena itu, urutan barisan derajat tersebut harus dibalik dari belakang ke depan. Jadi, barisan derajat dari adalah Catatan: Tanda | dipakai sebagai pengganti tanda koma untuk mempermudah pembacaan notasi.
[collapse]