Definisi dan Struktur Dasar Graf (Handshaking Lemma)

Teori graf menyediakan kerangka kerja visual dan matematis untuk mempelajari relasi antar objek.

1. Definisi Graf dan Derajat Titik

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$ .

2. Handshaking Lemma

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.

3. Lintasan dan Konektivitas

Walk: Urutan selang-seling titik dan sisi $v_{0}, e_{1}, v_{1}, e_{2}, \dots, v_{n}$ .
Path (Lintasan): Walk di mana semua titik yang dikunjungi berbeda.
Cycle (Siklus): Lintasan tertutup di mana titik awal sama dengan titik akhir ( $v_{0} = v_{n}$ ).
Connected (Terhubung): Sebuah graf disebut terhubung jika untuk setiap dua titik di $V$ , terdapat lintasan yang menghubungkan keduanya.

Contoh Soal & Pembahasan

Contoh (Eksistensi Graf 7 Titik Berderajat 3)

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

Latihan Soal

✏️ Latihan Soal 1 (Titik Berderajat Sama)

Buktikan bahwa setiap graf sederhana dengan $n$ titik ( $n \geq 2$ ) memiliki setidaknya dua titik dengan derajat yang sama.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Derajat titik yang mungkin untuk $n$ titik adalah ${0, 1, \dots, n - 1}$ .

Jika ada titik berderajat 0, tidak ada titik berderajat $n - 1$ . Kemungkinan derajat: ${0, 1, \dots, n - 2}$ (ada $n - 1$ pilihan).
Jika tidak ada titik berderajat 0, kemungkinan derajat: ${1, 2, \dots, n - 1}$ (ada $n - 1$ pilihan). Karena ada $n$ titik dan $n - 1$ kemungkinan nilai derajat, berdasarkan Pigeonhole Principle, pasti ada 2 titik berderajat sama. $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Rekurensi Linier Homogen
Sub-Topik Selanjutnya: Graf Eulerian dan Graf Hamiltonian →

Definisi dan Struktur Dasar Graf (Handshaking Lemma)

1. Definisi Graf dan Derajat Titik

2. Handshaking Lemma

3. Lintasan dan Konektivitas

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Graf Eulerian dan Graf Hamiltonian

Rekurensi Linier Homogen dan Persamaan Karakteristik

Diskusi & Tanya Jawab

Title