2014 Pengajar: Hilda Assiyatun

MA3051 Pengantar Teori Graf Semester 1 2013/2014 Pengajar: Hilda Assiyatun

Bab 1: Graf dan subgraf Graf 𝐺 : tripel terurut 𝑉𝐺 , 𝐸 𝐺 , 𝜓𝐺 ) 𝑉 𝐺 ≠ ∅ himpunan titik (vertex) 𝐸 𝐺 himpunan sisi (edge) 𝜓𝐺 fungsi keterkaitan antara himpunan sisi dan pasangan tak terurut titik (boleh sama) • Jika 𝑒 sisi dan 𝑢 dan 𝑣 titik sehingga 𝜓𝐺 𝑒 = 𝑢𝑣, maka dikatakan 𝑒 menghubungkan 𝑢 dan 𝑣. Titik 𝑢 dan 𝑣 disebut ujung dari 𝑒. • • • •

Contoh 1: • 𝐺 = 𝑉(𝐺 , 𝐸 𝐺 , 𝜓𝐺 ) dimana 𝑉 𝐺 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 𝐸 𝐺 = *𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 , 𝑒7 + 𝜓𝐺 didefinisikan sbb 𝜓𝐺 𝑒1 = 𝑣1 𝑣3 , 𝜓𝐺 𝑒2 = 𝑣1 𝑣3 , 𝜓𝐺 𝑒3 = 𝑣2 𝑣3 , 𝜓𝐺 𝑒4 = 𝑣3 𝑣3 , 𝜓𝐺 𝑒5 = 𝑣4 𝑣3 , 𝜓𝐺 𝑒6 = 𝑣2 𝑣4 , 𝜓𝐺 𝑒7 = 𝑣1 𝑣4 • Penamaan ‘GRAF” karena 𝐺 dapat digambarkan secara grafis dengan diagram (lihat gambar di papan). • Penggambaran diagram ini tidak tunggal. TUGAS BACA: cari dan pahami definisi: terkait (incident), bertetangga (adjacent), loop, link, graf berhingga, graf trivial, graf sederhana (simple).

Bab 1 Graf dan subgraf

• Banyaknya titik di 𝐺 disebut order dari 𝐺. Banyaknya sisi di 𝐺 disebut ukuran dari 𝐺. • Notasi: |𝑉 𝐺 | = 𝜈(𝐺) dan |𝐸 𝐺 | = 𝜀(𝐺). • Graf 𝐺 dan 𝐻 identik (ditulis 𝐺 = 𝐻) jika 𝑉 𝐺 = 𝑉 𝐻 , 𝐸 𝐺 = 𝐸 𝐻 , dan 𝜓𝐺 = 𝜓𝐻 . Jelas bahwa dua graf yang identik dapat mempunyai diagram yang sama. • Tetapi dua graf yang tidak identik mungkin saja dapat mempunyai diagram yang pada dasarnya sama. Dalam hal ini kita katakan bahwa kedua graf isomorfik (ditulis 𝐺 ≅ 𝐻). • 𝐺 ≅ 𝐻 jika terdapat bijeksi 𝜃: 𝑉 𝐺 → 𝑉 𝐻 dan 𝜙: 𝐸 𝐺 → 𝐸 𝐻 sehingga 𝜓𝐺 (𝑒) = 𝑢𝑣 ⟺ 𝜓𝐻 (𝜙(𝑒)) = 𝜃(𝑢)𝜃(𝑣). • Pasangan 𝜃, 𝜙 disebut isomorfisme antara 𝐺 dan 𝐻.


Contoh 2: • Misalkan 𝐺 = 𝑉(𝐺 , 𝐸 𝐺 , 𝜓𝐺 ) dimana 𝑉 𝐺 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 𝐸 𝐺 = *𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 + 𝜓𝐺 didefinisikan sbb 𝜓𝐺 𝑒1 = 𝑣1 𝑣3 , 𝜓𝐺 𝑒2 = 𝑣1 𝑣3 , 𝜓𝐺 𝑒3 = 𝑣2 𝑣3 , 𝜓𝐺 𝑒4 = 𝑣3 𝑣3 , 𝜓𝐺 𝑒5 = 𝑣4 𝑣3 . • Misalkan 𝐻 = 𝑉(𝐻 , 𝐸 𝐻 , 𝜓𝐻 ) dimana 𝑉 𝐻 = 𝑢, 𝑣, 𝑥, 𝑦 𝐸 𝐻 = *𝑎, 𝑏, 𝑐, 𝑑, 𝑒+ 𝜓𝐻 didefinisikan sbb 𝜓𝐻 𝑎 = 𝑢𝑥, 𝜓𝐻 𝑏 = 𝑢𝑥, 𝜓𝐻 𝑐 = 𝑣𝑥, 𝜓𝐻 𝑑 = 𝑥𝑥, 𝜓𝐻 𝑒 = 𝑦𝑥. • Maka pemetaan 𝜃, 𝜙 dimana 𝜃 𝑣1 = 𝑢, 𝜃 𝑣2 = 𝑣, 𝜃 𝑣3 = 𝑥, 𝜃 𝑣4 = 𝑦, dan 𝜙 𝑒1 = 𝑎, 𝜙 𝑒2 = 𝑏, 𝜙 𝑒3 = 𝑐, 𝜙 𝑒4 = 𝑑, 𝜙 𝑒5 = 𝑒, adalah isomorfime antara 𝐺 dan 𝐻.


• Beberapa kelas graf istimewa: Graf lengkap, 𝐾𝑛 , adalah graf sederhana dengan 𝑛 titik dimana setiap dua titik berbeda bertetangga. Graf bipartit adalah graf dimana himpunan titiknya dapat dipartisi menjadi dua subset 𝑋 dan 𝑌 sehingga setiap sisi mempunyai satu ujung di 𝑋 dan satu ujung di 𝑌. • TUGAS BACA: cari dan pahami definisi: graf kosong, graf bipartit lengkap 𝐾𝑚,𝑛 .


• Graf juga dapat direpresentasikan melalui matriks. • Misalkan graf 𝐺 dengan barisan titik 𝑣1 , 𝑣2 , … , 𝑣𝜈 , dan barisan sisi 𝑒1 , 𝑒2 , … , 𝑒𝜀 . • Matriks keterkaitan dari 𝐺 adalah matriks 𝑀 𝐺 = 𝑚𝑖𝑗 berukuran 𝜈 × 𝜀 dimana 𝑚𝑖𝑗 (nilainya 0, 1, atau 2) menyatakan frekuensi titik 𝑣𝑖 terkait dengan sisi 𝑒𝑗 . • Matriks ketetanggaan dari 𝐺 adalah matriks A 𝐺 = 𝑎𝑖𝑗 berukuran 𝜈 × 𝜈 dimana 𝑎𝑖𝑗 menyatakan banyaknya sisi yang menghubungkan titik 𝑣𝑖 dan titik 𝑣𝑗 . • DISKUSI: 1. Mana diantara kedua matriks yang bersifat simetris? 2. Selidiki jumlah baris dan jumlah kolom dari kedua matriks. Informasi apa yang termuat disana?


• Graf 𝐻 subgraf dari 𝐺, ditulis 𝐻 ⊆ 𝐺, jika V 𝐻 ⊆ 𝑉 𝐺 , E(𝐻) ⊆ 𝐸(𝐺), dan 𝜓𝐻 adalah pembatasan 𝜓𝐺 pada 𝐸 𝐻 . • Jika 𝐻 ⊆ 𝐺 dan 𝐻 ≠ 𝐺, ditulis 𝐻 ⊂ 𝐺, maka dikatakan 𝐻 subgraf sejati dari 𝐺. • Jika 𝐻 subgraf dari 𝐺 maka 𝐺 adalah supergraf dari 𝐻. • Subgraf pembangun (supergraf pembangun) dari 𝐺 adalah subgraf (supergraf) 𝐻 dimana 𝑉 𝐻 = 𝑉 𝐺 . • Misalkan 𝑉′ adalah subset tak hampa dari 𝑉(𝐺). Subgraf dari 𝐺 yang diinduksi oleh 𝑉′ , ditulis 𝐺 𝑉 ′ , adalah subgraf dengan himpunan titik 𝑉′ dan himpunan sisi terdiri dari semua sisi yang mempunyai kedua ujung di 𝑉 ′ .


• TUGAS BACA: cari dan pahami definisi: 1. 𝐺 − 𝑉 ′ , 2. 𝐺,𝐸 ′ -, 𝐸′ ⊆ 𝐸(𝐺) 3. 𝐺1 ∪ 𝐺2 , 𝐺1 + 𝐺2 , 𝐺1 ∩ 𝐺2


• Derajat titik 𝑣 di 𝐺, ditulis 𝑑𝐺 𝑣 , adalah banyaknya sisi yang terkait dengan 𝑣. • Derajat minimum dan derajat maksimum dari titik-tik di 𝐺 dinotasikan dengan 𝛿(𝐺) dan ∆ 𝐺 . Teorema 1.1. 𝑑 𝑣 = 2𝜀. 𝑣∈𝑉

Bukti: Gunakan matriks 𝑀 𝐺 . Hasil tambah semua jumlah baris harus sama dengan hasil tambah semua jumlah kolom.


Akibat 1.1. Dalam sebarang graf, banyaknya titik berderajat ganjil haruslah genap. Bukti: Misalkan 𝑉1 dan 𝑉2 adalah himpunan titik berderajat ganjil dan berderajat genap. Perhatikan bahwa persamaan 𝑑 𝑣 + 𝑣∈𝑉1

𝑑 𝑣 = 𝑣∈𝑉2

𝑑(𝑣) 𝑣∈𝑉

bernilai genap, sedangkan jumlah kedua di ruas kiri juga genap. • Graf 𝐺 disebut 𝑘-regular jika 𝑑 𝑣 = 𝑘, ∀𝑣 ∈ 𝑉. • DISKUSI: cari contoh graf regular.


• Jalan (walk) adalah barisan tak kosong 𝑊 = 𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 … 𝑒𝑘 𝑣𝑘 dimana untuk 1 ≤ 𝑖 ≤ 𝑘, 𝑒𝑖 = 𝑣𝑖−1 𝑣𝑖 . Titik 𝑣0 dan 𝑣𝑘 disebut pangkal dan ekor dari 𝑊, titik lainnya disebut titik internal. Panjang 𝑊 adalah 𝑘. Biasa dituliskan 𝑊 adalah jalan− 𝑣0 , 𝑣𝑘 . • Jika semua sisi berbeda, maka 𝑊 disebut trail, dan jika semua titik juga berbeda maka 𝑊 disebut lintasan (path). • Dua titik 𝑢 dan 𝑣 disebut terhubung jika terdapat lintasan − 𝑣0 , 𝑣𝑘 • Jarak antara titik 𝑢 dan 𝑣, ditulis 𝑑 𝑢, 𝑣 , adalah panjang lintasan − 𝑢, 𝑣 terpendek.


• Keterhubungan ini adalah sebuah relasi ekivalen pada himpunan titik 𝑉 (buktikan!). Akibatnya terdapat partisi dari 𝑉 menjadi kelas-kelas 𝑉1 , 𝑉2 , … , 𝑉𝜔 dimana 𝑢 dan 𝑣 terhubung jika dan hanya jika 𝑢 dan 𝑣 masuk ke dalam kelas yang sama. • 𝐺,𝑉1 -, 𝐺,𝑉2 -, … , 𝐺,𝑉𝜔 - disebut komponen-komponen dari 𝐺. • Jika 𝐺 hanya memiliki tepat satu komponen maka 𝐺 disebut terhubung. Jika tidak demikian, 𝐺 disebut tak terhubung. • 𝜔(𝐺) menyatakan banyaknya komponen dari 𝐺.


• Jalan disebut tertutup jika mempunyai panjang positif ,dan pangkal dan ekornya sama. • Trail tertutup yang semua titik internalnya berbeda disebut siklus. Teorema 1.2. 𝐺 bipartit ⟺ 𝐺 tidak memuat siklus ganjil. Bukti: ⇒ Ambil sebarang siklus 𝐶 = 𝑣0 𝑣1 … 𝑣𝑘 𝑣0 , tunjukkan 𝑘 ganjil. ⇐ Buktikan untuk 𝐺 terhubung saja. Misalkan 𝐺 tidak memuat siklus ganjil, dan 𝑢 sebarang titik di 𝐺. Perhatikan 𝑋 = 𝑥 ∈ 𝑉 𝑑 𝑢, 𝑥 genap+ 𝑌 = 𝑦 ∈ 𝑉 𝑑 𝑢, 𝑦 ganjil+. Tunjukkan bahwa (𝑋, 𝑌) adalah bipartisi di 𝐺.


LATIHAN 𝜈 1. Misalkan 𝐺 sederhana. Tunjukkan bahwa 𝜀 = jika dan 2 hanya jika 𝐺 lengkap. 2. Tunjukkan terdapat 11 graf sederhana non-isomorfik berorder 4. 3. Komplemen dari graf sederhana 𝐺, ditulis 𝐺 𝑐 , adalah graf sederhana dengan 𝑉 𝐺 = 𝑉 𝐺 𝑐 dan 𝑒 ∈ 𝐸 𝐺 𝑐 jika dan hanya jika 𝑒 ∉ 𝐸 𝐺 . Deskripsikan graf 𝐾𝑛 𝑐 dan 𝐾𝑚.𝑛 𝑐 . 4. Misalkan graf bipartit 𝑘-regular mempunyai partisi (𝑋, 𝑌). Tunjukkan bahwa 𝑋 = 𝑌 . 5. Misalkan 𝐺 sederhana dan 𝛿 ≥ 𝑘. Tunjukkan bahwa 𝐺 mempunyai lintasan dengan panjang 𝑘.


2014 Pengajar: Hilda Assiyatun

Recommend Documents