Berikut adalah contoh soal graf bipartit beserta jawabannya, cocok untuk materi matematika diskrit atau teori graf:

1. Soal Identifikasi Graf Bipartit

Soal: Diberikan graf $G$G dengan himpunan simpul $V = \{A, B, C, D, E, F\}$V={A,B,C,D,E,F} dan himpunan sisi $E = \{\{A, D\}, \{A, E\}, \{B, D\}, \{C, F\}\}$E={{A,D},{A,E},{B,D},{C,F}}. Apakah graf ini merupakan graf bipartit?
A. Ya
B. Tidak

Jawaban: A
Penjelasan: Graf bipartit dapat dibagi menjadi dua himpunan simpul sehingga setiap sisi menghubungkan simpul dari himpunan berbeda.

• Himpunan 1: $\{A, B, C\}${A,B,C}
• Himpunan 2: $\{D, E, F\}${D,E,F}
  Setiap sisi menghubungkan simpul dari himpunan berbeda → graf ini bipartit.

2. Soal Mewarnai Graf

Soal: Tentukan apakah graf di bawah ini bipartit, dan berikan pembagian himpunan simpulnya:

• Simpul: $V = \{1,2,3,4,5,6\}$V={1,2,3,4,5,6}
• Sisi: $\{ \{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,6\}, \{6,1\} \}${{1,2},{2,3},{3,4},{4,5},{5,6},{6,1}}

Jawaban: Tidak
Penjelasan: Graf ini membentuk siklus genap dengan 6 simpul, biasanya siklus genap bipartit, tapi perlu dicek:

• Coba membagi himpunan: {1,3,5} dan {2,4,6} → Semua sisi menghubungkan simpul berbeda himpunan.
• Ternyata semua sisi menghubungkan himpunan berbeda → graf bipartit.

Catatan: Semua siklus genap merupakan graf bipartit.

🔖 Baca juga:

Soal Data Cross Section dan Cara Menyelesaikannya dengan Cepat

Baca juga:Rahasia Gaji Quantum Hardware Engineer: Raih

3. Soal Aplikasi Graf Bipartit

Soal: Dalam sebuah perusahaan, ada 3 pegawai $P = \{P1, P2, P3\}$P={P1,P2,P3} dan 3 proyek $Q = \{Q1, Q2, Q3\}$Q={Q1,Q2,Q3}. Pegawai yang dapat mengerjakan proyek:

• P1 → Q1, Q2
• P2 → Q2, Q3
• P3 → Q1

Buat graf bipartit yang mewakili hubungan ini.

Jawaban:

• Himpunan 1: Pegawai {P1, P2, P3}
• Himpunan 2: Proyek {Q1, Q2, Q3}
• Sisi: {P1-Q1, P1-Q2, P2-Q2, P2-Q3, P3-Q1}

Graf ini jelas bipartit karena sisi hanya menghubungkan pegawai ke proyek.

Baca juga:BEM UNIVERSITAS TEKNOKRAT INDONESIA Implementasikan Teknologi Smart Cow Farming di Lampung Selatan

4. Soal Teori Graf Bipartit

Soal: Apakah graf berikut bipartit? Jelaskan alasannya.

• Simpul: $V = \{A, B, C, D\}$V={A,B,C,D}
• Sisi: $\{\{A,B\}, \{B,C\}, \{C,A\}, \{C,D\}\}${{A,B},{B,C},{C,A},{C,D}}

Jawaban: Tidak
Penjelasan: Graf ini memiliki siklus segitiga (A-B-C-A), yaitu siklus ganjil. Graf yang memiliki siklus ganjil tidak bisa bipartit.

Penulis:okta