Suatu graf G adalah pasangan himpunan (V, E), dimana V adalah himpunan titik

BAB II Dasar Teori

BAB II DASAR TEORI

2.1

Teori Dasar Graf

2.1.1 Graf dan Graf Sederhana Suatu graf G adalah pasangan himpunan (V, E), dimana V adalah himpunan titik yang tak kosong dan E adalah himpunan sisi. Untuk selanjutnya, himpunan titik di G dinotasikan sebagai V(G) dan himpunan sisi di G dinotasikan sebagai E(G). Sebagai contoh, graf G = (V(G), E(G)) dengan V(G) = {v1, v2, v3, v4, v5} dan E(G) = {v1v4, v2v5, v2v3, v2v3, v3v4, v5v5}.

Jika u, v ∈ V(G) dan uv ∈ E(G), maka u dan v disebut ujung-ujung dari uv. Dengan demikian, pada graf G di atas, sisi v1v4 mempunyai ujung v1 dan v4, sisi v2v3 mempunyai ujung v2 dan v3 dan seterusnya.

Titik u ∈ V(G) dikatakan bertetangga dengan titik v ∈ V(G), apabila terdapat sebuah sisi diantara u dan v. Pada graf G di atas, v1 bertetangga dengan v4, v2 bertetangga dengan v3 dan v5, dan seterusnya. Tetangga dari titik u ∈ V(G) adalah himpunan titik {v ∈ V(G) | uv ∈ E(G)} atau biasa disebut ketetanggaan dari u, yang dinotasikan NG(u) atau N(u). Titik v ∈ V(G) dikatakan terkait oleh sisi e ∈ E(G) jika v merupakan salah satu ujung dari sisi e. Dua sisi, e1, e2 ∈ E(G) dikatakan saling Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

4

BAB II Dasar Teori

terkait jika e1 dan e2 memiliki salah satu ujung yang sama. Loop adalah sisi yang mempunyai ujung yang sama. Pada graf G diatas, sisi v5v5 adalah loop. Derajat sebuah titik adalah banyaknya sisi yang terkait dengan titik tersebut. Graf sederhana adalah graf yang tidak mempunyai loop dan tidak ada dua sisi yang memiliki kedua ujung yang sama. Untuk selanjutnya, graf yang dibahas adalah graf sederhana.

Graf dapat direpresentasikan secara grafis. Untuk graf G, setiap u ∈ V(G) digambarkan dengan titik dan setiap uv ∈ E(G), digambarkan dengan garis yang menghubungkan titik u dengan titik v. Tidak ada cara unik dalam menggambarkan graf. Posisi titik dan garis dapat digambar secara bebas. Sebagai contoh, graf G diatas dapat digambar sebagai berikut :

Gambar 1 Suatu graf G

2.1.2 Isomorphic Misalkan terdapat dua buah graf G = (V(G), E(G)) dan G′ = (V(G)′, E(G)′). Graf G dikatakan isomorphic terhadap G′ (dinotasikan G ≅ G′), jika terdapat pemetaan satusatu dan pada θ : V(G) → V(G′) dan φ : E(G) → E(G′) dimana xy ∈ E(G) jika dan hanya jika φ (x)φ (y) ∈ E(G′) untuk setiap x, y ∈ V(G). Pemetaan (θ , φ ) disebut isomorfisme. Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

5

BAB II Dasar Teori

2.1.3 Subgraf Suatu graf H dikatakan subgraf dari G jika V(H) ⊆ V(G), E(H) ⊆ E(G), dan untuk setiap titik yang bertetangga di H maka bertetangga juga di G. Graf H dinotasikan dengan H ⊆ G. Ketika H ⊆ G tetapi H ≠ G, maka H disebut subgraf sejati dari G, yang dinotasikan dengan H ⊂ G. Jika H subgraf dari G, maka G supergraf dari H. Graf H dikatakan sebagai subgraf pembangun dari G, jika H ⊆ G dan V(H) = V(G).

Gambar 2 Beberapa contoh subgraf dari G

Misalkan, V′(G) himpunan bagian dari V(G) yang tak kosong. Subgraf dari G yang himpunan titiknya adalah V′(G) dan himpunan sisinya adalah semua sisi dari G yang kedua ujungnya berada di V′(G) dinamakan subgraf dari G yang diinduksi oleh V′(G) dan dinotasikan G[V′]; kita katakan G[V′] adalah subgraf induksi dari G. Subgraf induksi G[V \V′] dinotasikan G − V′. G − V′ adalah subgraf yang didapat dari G dengan cara menghapus titik di V′ bersama dengan sisi yang terkait. Sebagai contoh, misalkan V′ = {v} kita tulis G − {v}. Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

6

BAB II Dasar Teori

Sekarang misalkan E′(G) himpunan bagian dari E(G) yang tak kosong. Subgraf dari G yang himpunan titiknya adalah semua ujung dari E′(G) dan himpunan sisinya adalah E′(G) dinamakan subgraf dari G yang diinduksi oleh E′(G) dan dinotasikan G[E′]; kita katakan G[V′] adalah edge-subgraf induksi dari G. Subgraf pembangun dari G dengan himpunan sisinya adalah E \E′ dinotasikan G − E′. G − E′ adalah subgraf yang didapat dari G dengan cara menghapus semua sisi di E′. Sama halnya dengan graf yang didapat dari G dengan menambahkan sisi E′(G) yang dinotasikan G + E′. Sebagai contoh, misalkan E′ = {e1, e2} kita tulis G − {e1, e2} atau G + {e1, e2}.

2.1.4 Graf Lengkap dan Graf Bipartit Graf Lengkap adalah graf sederhana yang setiap titiknya bertetangga dengan titiktitik lain di graf tersebut. Graf lengkap disimbolkan dengan Kn atau Kn, dengan n adalah jumlah titik di graf tersebut.

Gambar 3 Beberapa contoh graf lengkap

Jika ada definisi untuk suatu graf G dengan n titik maka ada juga definisi untuk komplemen G, yang dinotasikan G . Komplemen G adalah graf dengan himpunan titik V( G ) = V(G) dan himpunan sisi E( G ) = E(Kn) \ E(G). Sebagai contoh, suatu graf kosong dengan n titik merupakan komplemen dari Kn.

Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

7

BAB II Dasar Teori

Graf Bipartit adalah graf yang titik-titiknya dapat dipartisi ke dalam dua himpunan tak kosong, V1 dan V2, dimana setiap edge terhubung dengan sebuah titik di V1 dan sebuah titik di V2. Suatu partisi (V1, V2) adalah bipartisi dari suatu graf. Graf Bipartit disimbolkan dengan Ka,b , dengan a dan b adalah jumlah titik pada masing-masing partisi. Apabila himpunan partisi lebih dari dua, maka disebut graf multipartit.

Gambar 4 Graf bipartit lengkap K4,2

2.1.5 Walk, Trail, Path, dan Keterhubungan Suatu walk (jalan) di G adalah barisan tak kosong yang terbatas W = v0e1v1e2v2...ekvk, dengan titik ujung dari ei adalah vi − 1 dan vi. Kita katakan W adalah jalan dari v0 ke vk, yang dinotasikan (v0, vk)-walk. Titik awal v0 disebut origin dan titik akhir vk disebut terminus dari W, sedangkan v1, v2,…, vk

− 1

dinamakan titik internal.

Sedangkan k merupakan panjang dari W. Suatu section (bagian) dari W = v0e1v1e2v2...ekvk adalah sub barisan viei + 1vi + 1...ejvj dari barisan W, yang dinotasikan dengan (vi, vj)-section.

Dalam graf sederhana, suatu jalan di G dapat ditulis dalam bentuk barisan yang hanya terdiri dari titik-titik saja. Sebagai contoh, walk (jalan) v0e1v1e2v2...ekvk dapat ditulis menjadi barisan v0v1v2... vk. Misalkan W = v0e1v1e2v2...ekvk. Jika ei ≠ ej untuk setiap i ≠ j, maka W disebut trail, yang dinotasikan (v0, vk)-trail. Jika vi ≠ vj untuk Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

8

BAB II Dasar Teori

setiap i ≠ j, maka W disebut path (lintasan), yang dinotasikan (v0, vk)-path. Dua titik u, v ∈ V(G) dikatakan terhubung jika terdapat (u, v)-path di G. Graf G dikatakan terhubung jika dan hanya jika untuk setiap dua titik u, v ∈ V(G) selalu terhubung.

Gambar 5 Walk, trail, dan path pada G

Sebuah subgraf terhubung dikatakan maksimum apabila tidak ada subgraf terhubung lain dengan jumlah titik atau sisi yang lebih banyak dari subgraf tesebut. Komponen dari sebuah graf G adalah sebuah subgraf terhubung maksimum dari G, yang dinotasikan ω(G). Setiap graf terhubung hanya mempunyai satu komponen.

2.1.6 Jarak dan Diameter Jarak dari u ke v pada suatu graf terhubung G adalah panjang (u, v)-path terpendek di G, yang dinotasikan d(u, v). Diameter dari suatu graf G adalah jarak maksimum antara dua titik di G.

2.1.7 Cycle Sebuah walk atau trail dikatakan tertutup jika mempunyai panjang positif, dan origin dan terminus-nya berada pada titik yang sama. Sebuah barisan tertutup dengan ei ≠ ej

Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

9

BAB II Dasar Teori

dan vi ≠ vj untuk setiap i ≠ j disebut cycle. Sebuah cycle dengan panjang k dinamakan k-cycle. Suatu k-cycle dinamakan cycle genap atau cycle ganjil bergantung pada bilangan k itu sendiri.

Gambar 6 Cycle pada G

Dengan menggunakan konsep cycle, kita bisa mengetahui karakteristik dari graf bipartit. Teorema 1 : Suatu graf G dikatakan bipartit jika dan hanya jika G tidak mempunyai cycle ganjil. Bukti :

⇒ Misalkan G bipartit dengan partisinya (X,Y) dan misalkan C = v0v1v2...vk v0 suatu cycle di G. Tanpa mengurangi perumuman, kita asumsikan v0 ∈ X. Dengan demikian, karena v0v1 ∈ E(G) dan G bipartit maka v1 ∈ Y. Dengan cara yang sama maka v2 ∈ X, v3 ∈ Y, v4 ∈ X, dst. Secara umum, v2i ∈ X dan v2i + 1 ∈ Y. Karena v0 ∈ X dan vk ∈ Y maka k = 2i + 1, untuk suatu i, maka C merupakan cycle genap.

⇐ Misalkan G graf terhubung yang tidak mempunyai cycle ganjil. Pilih sembarang titik u dan definisikan dua partisi (X, Y) dari V(G), sebagai berikut : Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

10

BAB II Dasar Teori

X = {x ∈ V(G) | d(u, x) genap} Y = {y ∈ V(G) | d(u, y) ganjil} Sekarang akan dibuktikan bahwa (X, Y) adalah bipartit dari G. Misalkan v dan w dua titik di X. Misalkan P adalah panjang (u, v)-path terpendek dan Q adalah panjang (u, w)-path terpendek. Misalkan u1 sebagai titik terakhir yang berada di P dan Q. Karena P dan Q merupakan lintasan terpendek maka (u, u1)-section dari P dan Q adalah (u, u1)-path terpendek yang panjangnya sama.

Perhatikan bahwa P dan Q memiliki panjang genap. Oleh karena itu, misalkan P1 adalah panjang (u1, v)-section dari P dan Q1 adalah panjang (u1, w)-section dari Q , keduanya memiliki kesamaan dalam hal panjang. P1 dan Q1 bisa memiliki panjang genap atau ganjil sehingga P1−1Q1 yang merupakan (v, w)-path memiliki panjang genap. Jika v bertetangga dengan w, P1−1Q1 wv adalah cycle dengan panjang ganjil, kontradiksi dengan pemisalan awal. Hal serupa berlaku untuk Y. Jadi, tidak ada dua titik yang bertetangga di X, begitu juga tidak ada tua titik yang bertetangga di Y.

2.1.8 Independent set dan Clique Suatu S yang merupakan himpunan bagian dari V(G) dikatakan independent set dari G jika tidak ada dua titik di S yang bertetangga. Suatu independent set dikatakan maksimum jika G tidak mempunyai S′ yang merupakan independent set dengan |S′|>|S|. S dikatakan clique dari graf sederhana G jika G[S] merupakan graf lengkap. Suatu clique dikatakan maksimum jika G tidak mempunyai S′ yang merupakan clique dengan |S′|>|S|.

Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

11

BAB II Dasar Teori

Gambar 7 (a) clique dan (b) maksimum clique pada suatu graf

2.1.9 Penggabungan dan Penjumlahan Graf Seperti halnya himpunan, pada graf terdapat pula penggabungan dan penjumlahan dua buah graf. Misalkan G dan H adalah dua buah graf. Suatu G ∪ H adalah penggabungan G dan H jika himpunan titik V(G ∪ H) = V(G) ∪ V(H), dengan V(G) ∩ V(H) = ∅ dan himpunan sisi E(G ∪ H) = E(G) ∪ E(H).

Penjumlahan dua buah graf dinotasikan dengan G + H. Dikatakan demikian jika himpunan titik V(G + H) = V(G) ∪ V(H) dan himpunan sisi E(G + H) adalah himpunan sisi E(G) ∪ E(H) ∪ {uv| u ∈ V(G) dan v ∈ V(H)}.

Gambar 8 Penggabungan dan penjumlahan dua buah graf

Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

12

BAB II Dasar Teori

2.2

Dimensi Partisi

2.2.1 Jarak antara Titik dengan Partisi V(G) Hampir sama dengan jarak pada graf, misalkan S himpunan bagian dari V(G) dan v titik dari graf terhubung G, jarak antara v dengan S yang dinotasikan d(v, S) didefinisikan sebagai d(v, S) = min{d(v, x)|x ∈ S}.

2.2.2 Koordinat v terhadap

Π

Misalkan suatu k buah partisi Π = {S1, S2,…, Sk} dari V(G) dan v titik di G. Koordinat v terhadap Π didefinisikan sebagai r(v| Π ) = (d(v, S1), d(v, S2),..., d(v, Sk)). Suatu koordinat r(u| Π ) dikatakan sama dengan r(v| Π ) untuk suatu u, v ∈ V(G) jika d(u, Si) = d(v, Si), untuk 1 ≤ i ≤ k.

2.2.3 Dimensi Partisi pada Graf G Partisi Π dikatakan resolving partition jika k buah vektor r(v| Π ), untuk setiap v ∈ V(G) berbeda. Nilai minimum k yang menjadi resolving partition adalah dimensi partisi dari G, yang dinotasikan pd(G). Untuk lebih mengerti, sebagai contoh :

Gambar 9 Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

13

BAB II Dasar Teori

Misalkan Π 1 = {S1, S2, S3}, dengan S1 = {u}, S2 = {v, w, x}, dan S3 = {y}. Maka semua koordinat titik di G terhadap Π 1 adalah r(u| Π 1) = (0, 1, 1), r(v| Π 1) = (1, 0, 1), r(w| Π 1) = (2, 0, 1), r(x| Π 1) = (2, 0, 1), r(y| Π 1) = (1, 1, 0).

Karena r(w| Π 1) = r(x| Π 1) = (2, 0, 1), maka Π 1 bukan resolving partition dari G. Berikutnya, misalkan Π 2 = {S1, S2, S3, S4}, dengan S1 = {u}, S2 = {v, w}, S3 = {x}, dan S4 = {y}. Maka semua koordinat titik di G terhadap Π 2 adalah r(u| Π 2) = (0, 1, 2, 1), r(v| Π 2) = (1, 0, 2, 1), r(w| Π 2) = (2, 0, 1, 1), r(x| Π 2) = (2, 1, 0, 1), r(y| Π 2) = (1, 1, 1, 0).

Karena semua koordinat titik di G terhadap Π 2 berbeda maka Π 2 merupakan resolving partition dari G. Meskipun demikian, Π 2 bukan minimum resolving partition dari G. Untuk menunjukkannya, misalkan Π 3 = {S1, S2, S3}, dengan S1 = {u}, S2 = {v, w}, dan S3 = {x, y}. Maka semua koordinat titik di G terhadap Π 3 adalah r(u| Π 3) = (0, 1, 1), r(v| Π 3) = (1, 0, 1), Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

14

BAB II Dasar Teori

r(w| Π 3) = (2, 0, 1), r(x| Π 3) = (2, 1, 0), r(y| Π 3) = (1, 1, 0).

Jadi, Π 3 merupakan resolving partition dari G. Lebih lanjut, karena tidak ada 2 buah partisi dari V(G) yang merupakan resolving partition dari G maka Π 3 merupakan minimum resolving partition dari G. Jadi, pd(G) = 3. Mungkin timbul pertanyaan, mengapa tidak ada 2 buah partisi dari V(G) yang merupakan resolving partition dari G. Pembuktiannya dijelaskan pada Bab 3.

Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

15