2. TINJAUAN PUSTAKA
2.1 Konsep Dasar Graf
Pada bagian ini akan diberikan konsep dasar graf yang diambil dari buku Chartrand dan Zhang (2005) yaitu sebagai berikut: Suatu Graf πΊ adalah suatu pasangan himpunan (π, πΈ) dimana π(πΊ) adalah himpunan tak kosong dan berhingga dari objek-objek yang disebut titik (vertex), dan πΈ(πΊ) adalah himpunan dari pasangan tak terurut dari titik-titik berbeda di π yang disebut sisi (edge).
Sebuah sisi yang menghubungkan pasangan titik yang sama atau bisa disebut juga sebuah sisi yang berawal dan berakhir dengan pada titik yang sama disebut dengan gelang (loop). Dua atau lebih sisi yang mempunyai titik-titik ujung yang sama disebut dengan sisi paralel. Jika sebuah graf πΊ yang di dalamnya tidak terdapat gelang dan sisi paralel disebut graf sederhana. Pada Gambar 1 contoh loop adalah π1 dan sisi paralel adalah π3 , π5 .
4
Gambar 1. Graf dengan titik terasing, gelang dan sisi paralel.
Suatu jalan (walk) dalam graf πΊ adalah suatu barisan berhingga dari titik dan sisi secara bergantian yang dimulai dan diakhiri dengan titik sehingga setiap sisi yang menempel dengan titik sebelum dan sesudahnya, dimana sebuah sisi hanya dilalui satu kali. Di dalam suatu jalan pada sebuah graf dapat terjadi bahwa satu titik dilalui lebih dari satu kali. Pada umumnya penulisan barisan jalan biasanya mengikutsertakan sisinya, tetapi boleh juga tidak. Dapat juga sebuah jalan dimulai dan diakhiri oleh titik yang sama, jalan yang demikian disebut dengan jalan tertutup (close walk). Sebaliknya sebuah jalan yang tidak tertutup disebut jalan terbuka (open walk). Pada Gambar 1 contoh jalan terbuka adalah π£1 , π2 , π£2 , π3 , π£3 , π3 , π£2 , π2 dan jalan tertutup adalah π£1 , π2 , π£2 , π3 , π£3 , π3 , π£2 , π2 , π£1 . Sebuah jalan terbuka yang di dalamnya tidak ada titik yang muncul lebih dari sekali disebut dengan lintasan (path). Pada Gambar 1 lintasan yaitu π£1 , π2 , π£2 , π4 , π£3 , π6 , π£4 , π8 . Jalan yang semua sisi di dalam setiap barisan harus berbeda disebut jejak (trail). jejak tertutup adalah suatu trail dengan titik awal dan titik akhir yang sama.
5
Pada Gambar 1 contoh jejak yaitu π£1 , π2 , π£2 , π7 , π£4 , π8 . Sebuah lintasan yang tertutup disebut sirkuit. Pada Gambar 1 sirkuit yaitu π£2 , π4 , π£3 , π6 , π£4 , π7 , π£2 . Dua buah titik pada graf tak berarah πΊ dikatakan bertetangga (adjacent) bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, π£π bertetangga dengan π£π jika (π£π , π£π ) adalah sebuah sisi dari graf. Untuk sebarang sisi π = (π£π , π£π ), sisi π dikatakan menempel (incident) dengan titik π£π dan π£π . Pada Gambar 1 π£1 bertetangga dengan π£4 , π6 menempel pada π£3 dan π£4 . Titik yang tidak memiliki sisi yang menempel dengannya atau tidak bertetangga dengan titik lainnya disebut dengan titik terasing. Pada Gambar 1 titik terasing yaitu π£5 . Derajat (degree) dari sebuah titik π£π dalam graf πΊ adalah banyaknya sisi yang menempel pada π£π , dengan gelang dihitung dua kali. Bila jumlah sisi yang menempel dengan jumlah titik π£π adalah π maka derajat dari π£π adalah π sehingga π(π£π ) = π. Pada Gambar 1 derajat dari titik π£4 yaitu tiga. Jumlah derajat semua titik pada suatu graf adalah genap, yaitu dua kali banyaknya sisi pada graf tersebut. Dengan kata lain, jika πΊ = (π, πΈ), maka βπ£βπ π(π£) = 2|πΈ|.
2.2 Kelas-kelas Graf
Pada bagian ini akan diberikan kelas-kelas graf yang diambil dari buku Aldous dan Wilson (2000) yaitu sebagai berikut:
6
Graf lengkap ialah graf sederhana yang setiap titiknya bertetangga dengan semua titik lainnya. Graf lengkap dengan π titik dilambangkan dengan πΎπ . Jumlah sisi pada graf lengkap yang terdiri dari π titik adalah
π(πβ1) 2
.
Gambar 2. Graf lengkap K1 , K 2 , K 3 , K 4 , K 5 dan K 6 .
Graf lingkaran adalah graf sederhana yang setiap titiknya berderajat dua. Graf lingkaran dengan π titik dilambangkan dengan πΆπ .
Gambar 3. Graf lingkaran C1 , C2 , C3 dan C4 .
Graf lintasan ialah graf yang terdiri dari satu lintasan. Graf lintasan dengan π titik dinotasikan dengan ππ . Graf πΊ yang himpunan titiknya dapat dipisah menjadi dua himpunan bagian π1 dan π2, sedemikian sehingga setiap sisi pada πΊ menghubungkan sebuah
7
titik di π1 ke sebuah titik di π2 disebut graf bipartit dan dinyatakan sebagai πΊ = (π1 , π2 ). Apabila πΊ graf sederhana dan bipartit dengan partisi π1 , π2 sedemikian sehingga setiap titik di π1 bertetangga dengan setiap titik di π2 maka πΊ disebut graf bipartit lengkap.
Graf pohon ialah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka graf pohon selalu terdapat jalur yang menghubungkan setiap dua titik. Salah satu contoh dari graf pohon yaitu graf bintang. Graf bintang adalah graf pohon dengan satu titik pusat yang terhubung dengan π daun. Graf bintang dinotasikan dengan πΎ1,π . 2.3 Dimensi Metrik
Dimensi Metrik adalah kardinalitas minimum himpunan pemisah (resolving set) pada πΊ. Misalkan π’ dan π£ adalah titik-titik dalam graf terhubung πΊ maka jarak π(π’, π£) adalah panjang lintasan terpendek antara π’ dan π£ pada πΊ. Untuk himpunan terurut π = {π€1 , π€2 , π€3 , β¦ , π€π } dari titik-titik dalam graf terhubung πΊ dan titik π£ β π(πΊ), representasi dari π£ terhadap π adalah πvektor (pasangan π-tuple) π(π£|π) = (π(π£, π€1 ), π(π£, π€2 ), β¦ , π(π£, π€π )). Jika π(π£|π) untuk setiap titik π£ β π(πΊ) berbeda, maka π disebut himpunan pemisah dari π(πΊ). Himpunan pemisah dengan kardinalitas minimum (basis metrik), dan kardinalitas dari basis metrik tersebut dinamakan dimensi metrik dari πΊ dinotasikan πππ(πΊ) (Chartrand, dkk, 1999).
8
Berikut ini akan diberikan contoh dimensi metrik pada suatu graf
Gambar 4. Graf dengan 4 titik dan 5 sisi.
Ambil π = {π£1 }, representasi titiknya adalah π(π£1 |π) = (0),
π(π£3 |π) = (2),
π(π£2 |π) = (1),
π(π£4 |π) = (1).
Karena ada representasi titik yang sama untuk π = {π£1 }, maka π = {π£1 } bukan himpunan pemisah dan juga bukan merupakan basis metrik. Sehingga banyaknya anggota π = {π£1 } tidak dapat dikatakan sebagai dimensi metrik. Oleh karena itu, ambil π yang lain. Ambil π = {π£1 , π£2 }, representasi titiknya adalah π(π£1 |π) = (0,1),
π(π£3 |π) = (2,1),
π(π£2 |π) = (1,0),
π(π£4 |π) = (1,1).
Karena representasi semua titik berbeda untuk π = {π£1 , π£2 }, maka π = {π£1 , π£2 } merupakan himpunan pemisah dari basis metrik. Selain itu, banyaknya anggota basis ini merupakan yang paling minimum sehingga banyaknya anggota π = {π£1 , π£2 } dapat dinyatakan sebagai dimensi metrik dari graf tersebut (Chartrand, dkk, 2000).
9
