Download - MA3051 Pengantar Teori Graf · •Jika sisi dan dan titik sehingga ... loop, link, graf berhingga ... Selidiki jumlah baris dan jumlah kolom dari kedua matriks

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

Bab 1 Graf dan subgraf

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


• 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

𝑑 𝑣 + 𝑑 𝑣 = 𝑑(𝑣)

𝑣∈𝑉𝑣∈𝑉2𝑣∈𝑉1

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 휀 =𝜈2

jika dan

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

Download - MA3051 Pengantar Teori Graf · •Jika sisi dan dan titik sehingga ... loop, link, graf berhingga ... Selidiki jumlah baris dan jumlah kolom dari kedua matriks

Top Related