Teori Graf Dasar, Graf Eulerian, Hamiltonian & Teorema Hall

Teori graf menyediakan kerangka kerja visual dan matematis untuk mempelajari relasi antar objek. Sebuah graf dapat merepresentasikan jaringan, struktur molekul, hingga hubungan pertemanan.

1. Definisi dan Struktur Dasar Graf

Definisi (Graf)

Sebuah graf $G = (V, E)$ terdiri dari himpunan tak kosong $V$ yang berisi titik-titik (vertices) dan himpunan $E$ yang berisi sisi-sisi (edges), di mana setiap sisi menghubungkan dua titik di $V$ .

Lemma (Handshaking Lemma)

Untuk setiap graf $G = (V, E)$ , jumlah derajat semua titik adalah dua kali jumlah sisinya:

$\sum_{v \in V} d (v) = 2∣ E ∣$

Konsekuensi Direct: Dalam setiap graf, jumlah titik yang memiliki derajat ganjil haruslah genap.

2. Graf Eulerian dan Graf Hamiltonian

Graf Eulerian

Sebuah graf dikatakan memiliki lintasan Euler jika terdapat lintasan yang melalui setiap sisi tepat satu kali. Jika lintasan tersebut tertutup, disebut Sirkuit Euler.

Teorema (Teorema Euler)

Sebuah graf terhubung $G$ memiliki sirkuit Euler jika dan hanya jika setiap titik di $G$ memiliki derajat genap.

Graf terhubung $G$ memiliki lintasan Euler (tetapi bukan sirkuit) jika dan hanya jika $G$ memiliki tepat dua titik berderajat ganjil.

Graf Hamiltonian

Sebuah graf dikatakan memiliki lintasan Hamilton jika terdapat lintasan yang melalui setiap titik tepat satu kali. Jika tertutup, disebut Siklus Hamilton.

Teorema (Teorema Dirac)

Jika $G$ adalah graf sederhana dengan $n$ titik ( $n \geq 3$ ) dan setiap titik $v$ memenuhi $d (v) \geq n /2$ , maka $G$ memiliki siklus Hamilton.

3. Matching dan Marriage Theorem (Teorema Hall)

Definisi (Graf Bipartit & Matching)

Sebuah graf $G = (X \cup Y, E)$ dikatakan bipartit jika himpunan titik dapat dipartisi menjadi dua himpunan saling lepas $X$ dan $Y$ sedemikian sehingga setiap sisi menghubungkan satu titik di $X$ dengan satu titik di $Y$ .

Sebuah matching $M$ adalah subhimpunan dari sisi-sisi $E$ di mana tidak ada dua sisi yang berbagi titik yang sama.

Teorema (Teorema Hall (Marriage Theorem))

Misalkan $G = (X \cup Y, E)$ adalah graf bipartit. Terdapat complete matching yang menjenuhkan setiap titik di $X$ jika dan hanya jika untuk setiap subhimpunan $S \subseteq X$ , berlaku:

$∣ N (S) ∣ \geq ∣ S ∣$

di mana $N (S)$ adalah himpunan tetangga dari semua titik di $S$ (neighborhood set).

Contoh Soal & Pembahasan

Contoh (Aplikasi Handshaking Lemma)

Mungkinkah terdapat sebuah graf dengan 7 titik di mana masing-masing titik memiliki derajat tepat 3?

Contoh (Aplikasi Teorema Hall)

Sebuah perusahaan memiliki 5 lowongan pekerjaan berbeda ( $J_{1} \dots J_{5}$ ) dan 5 pelamar ( $P_{1} \dots P_{5}$ ).

$P_{1}, P_{2}, P_{3}$ : kualifikasi ${J_{1}, J_{2}}$
$P_{4}$ : kualifikasi ${J_{3}, J_{4}, J_{5}}$
$P_{5}$ : kualifikasi ${J_{2}, J_{5}}$

Mungkinkah setiap orang mendapatkan pekerjaan yang sesuai?

Latihan Soal

✏️ Latihan Soal 1 (Tiga Orang Saling Kenal (Teorema Ramsey R(3,3)))

Buktikan bahwa dalam sebuah kelompok berisi 6 orang, selalu terdapat setidaknya 3 orang yang saling kenal atau 3 orang yang saling tidak kenal satu sama lain.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Representasikan 6 orang sebagai 6 titik graf lengkap $K_{6}$ . Warnai sisi dengan merah (saling kenal) atau biru (tidak kenal). Pilih satu titik $V_{1}$ . Ada 5 sisi yang keluar dari $V_{1}$ . Berdasarkan Pigeonhole Principle ( $⌈ 5/2 ⌉ = 3$ ), setidaknya ada 3 sisi berwarna sama (misal merah) yang terhubung ke $V_{2}, V_{3}, V_{4}$ .

Jika salah satu sisi antara $V_{2}, V_{3}, V_{4}$ berwarna merah, terbentuk segitiga merah (3 orang saling kenal).
Jika ketiga sisi di antara $V_{2}, V_{3}, V_{4}$ berwarna biru, terbentuk segitiga biru (3 orang saling tidak kenal). $■$

✏️ Latihan Soal 2 (Jumlah Sisi Graf Lengkap K10)

Berapa jumlah seluruh derajat titik pada graf lengkap $K_{10}$ ?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Pada $K_{10}$ , terdapat 10 titik dan setiap titik memiliki derajat $10 - 1 = 9$ . Berdasarkan Handshaking Lemma, jumlah seluruh derajat titik adalah $10 \times 9 = 90$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Relasi Rekurensi
Sub-Topik Selanjutnya: Fungsi Pembangkit →

Teori Graf Dasar, Graf Eulerian, Hamiltonian & Teorema Hall

1. Definisi dan Struktur Dasar Graf

2. Graf Eulerian dan Graf Hamiltonian

Graf Eulerian

Graf Hamiltonian

3. Matching dan Marriage Theorem (Teorema Hall)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Fungsi Pembangkit Biasa & Eksponensial

Relasi Rekurensi & Persamaan Karakteristik

Diskusi & Tanya Jawab

Title