BAB 2 LANDASAN TEORI
2.1 Konsep Dasar Graf
Definisi 2.1.1 Sebuah graf G adalah pasangan (V, E) dengan V adalah himpunan yang tak kosong yang anggotanya disebut vertex, dan E adalah himpunan yang anggotanya adalah pasangan-pasangan tak berurut dan disebut dengan edge.
Gambaran umum mengenai graf diartikan sebagai diagram, dimana vertex disajikan berupa vertex dan dinotasikan dengan vi ; i = 1, 2, 3, . . . , m dan edge disajikan berupa garis lurus atau garis lengkung yang menghubungkan dua buah vertex (vi , vj ) dan dapat dinotasikan dengan ei ; i = 1, 2, 3, . . . , n. Definisi 2.1.1 menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai edge satu buah pun, tetapi vertexnya harus minimal ada satu. Sebagai ilustrasi dapat dilihat gambar 2.1 yaitu :
Gambar 2.1 : Graf
- G1 adalah graf dengan V = {1, 2, 3, 4} dan E = {(1, 2), (1, 3), (2, 3), (3, 4)}. - G2 adalah graf dengan V = {1, 2, 3, 4} dan E = {(1, 2), (2, 3), (1, 3), (2, 4), (3, 4), (3, 4)} = {e1, e2 , e3, e4, e5, e6, e7 }
Universitas Sumatera Utara
6 - G3 adalah graf dengan V = {1, 2, 3, 4} dan E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3)} = {e1, e2, e3 , e4, e5, e6, e7, e8 }
Definisi 2.1.2 Loop dan Edge Paralel Sebuah edge yang menghubungkan pasangan vertex yang sama yakni (vi , vj ) disebut loop dan dua buah atau lebih edge yang mempunyai vertex vertex ujung yang sama disebut edge-edge yang paralel atau multiple edge. Pada gambar 2.1 dapat dilihat, gambar G1 tidak memiliki loop maupun edge pararel, sedangkan pada gambar G2 tidak memiliki loop tetapi memiliki edge paralel yaitu e3, e4 dan e1 , e6. Dan pada gambar G3 memiliki loop yaitu e8 dan edge pararel yaitu e3, e4 dan e1 , e6.
Definisi 2.1.3 Graf Sederhana (Simple Graf) Simple graf adalah graf yang tidak memuat loop dan edge-edge yang pararel.
Gambar 2.2 : Simple Graf
Definisi 2.1.4 Ketetanggaan (Adjacent) Dua buah vertex pada graf dikatakan bertetangga bila kedua vertex tersebut terhubung langsung. Atau dapat kita sebut vj bertetangga dengan vk pada graf G jika (vj , vk ) adalah edge pada sebuah graf G.
Definisi 2.1.5 Bersisian (Incident) Untuk sembarang edge e = (vj , vk ) dikatakan bersisian dengan vertex vj atau e bersisian dengan vertex vk .
Universitas Sumatera Utara
7 Definisi 2.1.6 Vertex Terpencil (Isolated Vertex ) Vertex yang tidak memiliki edge yang bersisian dengannya atau tidak bertetangga dengan vertex lainnya disebut dengan vertex terpencil.
Definisi 2.1.7 Graf Kosong (Null Graf) Graf yang himpunan edgenya merupakan himpunan kosong (Nn ) disebut graf kosong, dimana nadalah jumlah vertex.
Gambar 2.3 : Graf Kosong
Definisi 2.1.8 Derajat (Degree) Derajat dari sebuah vertex vi dalam graf G adalah jumlah edge yang bersisian dengan vi , dengan loop dihitung dua kali. Bila jumlah edge yang bersisian dengan jumlah vertex vi adalah n maka degree dari vi adalah n sehingga d(vi ) = n.
Gambar 2.4 : Graf (7,8)
Dari gambar 2.4 maka V = {v1, v2, v3, v4, v5, v6, v7 } dan E = {e1 , e2, e3, e4, e5, e6 , e7, e8} dimana;
Universitas Sumatera Utara
8 - Vertex 1 bertetangga dengan vertex 2, 3 dan 4 tetapi tidak bertetangga dengan vertex 5 dan 6. - Vertex 5 bertetangga dengan vertex 2 dan 4 tetapi tidak bertetangga dengan vertex 1, 3, 4 dan 6. - Edge (1,2) bersisian dengan vertex 1 dan vertex 2. - Edge (1,4) bersisian dengan vertex 1 dan vertex 4. - Tetapi edge (3,4) tidak bersisian dengan vertex 1, 2, 5, 6 dan 7. - Vertex terpencil adalah vertex 7. - Derajat d(1) = d(2) = d(4) = 3, d(3) = d(5) = 2 dan d(6) = 1 dan d(7) = 0.
2.2 Jenis-jenis Graf Berdasarkan ada tidaknya gelang atau edge ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (Simple Graf) Graf yang tidak mengandung gelang maupun edge-ganda dinamakan graf sederhana. 2. Graf tak-sederhana (Unsimple-Graf) Graf yang mengandung edge ganda atau gelang dinamakan graf tak-sederhana (unsimple graf).
Berdasarkan jumlah vertex pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga(Limited Graf ) Universitas Sumatera Utara Graf berhingga adalah graf yang jumlah vertexnya n berhingga.
9 2. Graf tak-berhingga (Unlimited Graf) Graf yang jumlah vertexnya n tidak berhingga banyaknya disebut graf tak berhingga.
Berdasarkan orientasi arah pada edge, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (Undirected Graf) Graf yang edgenya tidak mempunyai orientasi arah disebut graf tak-berarah. 2. Graf berarah (Directed Graf atau Digraf ) Graf yang setiap edgenya diberikan orientasi arah disebut sebagai graf berarah.
Gambar 2.5 : Graf Berarah dan Graf-Ganda Berarah
Ada juga graf sederhana khusus yang terdiri dari:
a. Graf lengkap (Complete Graf) Graf lengkap ialah graf sederhana yang setiap vertexnya mempunyai edge ke semua vertex lainnya. Graf lengkap dengan n buah vertex dilambangkan dengan Kn . Jumlah edge pada graf lengkap yang terdiri dari n buah vertex adalah n(n1)/2.
Universitas Sumatera Utara
10
Gambar 2.6 : Graf Lengkap
b. Graf teratur (Regular Graf) Graf yang setiap vertexnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap vertex adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah edge pada graf teratur adalah nr/2.
Gambar 2.7 : Graf Teratur
c. Graf bipartisi (Bipartite Graf) Graf G yang himpunan vertexnya dapat dipisah menjadi dua himpunan bagian V1 dan V2 , sedemikian sehingga setiap edge pada G menghubungkan sebuah vertex di V1 ke sebuah vertex di V2 disebut graf bipartite dan dinyatakan sebagai G(V1 , V2 ).
Gambar 2.8 : Graf Bipartite Universitas Sumatera Utara
11 2.3 Terminologi Dasar
Definisi 2.3.1 Walk Suatu walk dalam graf G adalah suatu barisan berhingga dari vertex dan edge secara bergantian yang dimulai dan diakhiri dengan vertex sehingga setiap edge yang bersisian dengan vertex sebelum dan sesudahnya, dimana sebuah edge hanya dilalui satu kali. Di dalam suatu walk pada sebuah graf dapat terjadi bahwa satu vertex dilalui lebih dari satu kali. Pada umumnya penulisan barisan walk biasanya mengikutsertakan edgenya, tetapi boleh juga tidak.
Apabila vertex awal dan akhir dari suatu walk adalah sama, maka walk yang demikian disebut dengan closed walk (walk tertutup). Sedangkan bila vertex awal dan vertex akhir dari suatu walk berbeda, maka walk yang demikian disebut open walk (walk terbuka). Sebagai contoh diberikan pada gambar berikut :
Gambar 2.9 : Graf Pada gambar tersebut dapat diambil beberapa walk diantaranya sebagai berikut :
- v1e1v2 e4v6e7 v5e6v3 e2v1 - v1e2v3 e6v5e7 v6
(open walk) Universitas Sumatera Utara (open walk)
12 Walk di atas boleh juga ditulis dengan cara sebagai berikut :
- v1v2v6 v5v3v1 - v1v3v5 v6
(closed walk) (open walk)
Definisi 2.3.2 Trail Walk yang semua edge di dalam setiap barisan harus berbeda disebut trail. Trail tertutup adalah suatu trail dengan vertex awal dan vertex akhir yang sama.
Dari gambar 2.11, salah satu contoh yang merupakan trail adalah : v1 v2e3v3 e6v5e7 v6 e4v2e1 v1
Definisi 2.3.3 Lintasan (Path) Path dari suatu graf G adalah suatu walk yang keseluruhan vertex nya berbeda kecuali vertex awal dan vertex akhir yang boleh sama. Bila dalam suatu path di mana vertex awal dan akhir sama maka path yang demikian disebut closed path (path tertutup), sedangkan bila vertex awal dan akhir tidak sama maka disebut open path (path terbuka).
Sebagai contoh lihat gambar 2.11
- v1v3v5 v3v2v6
(open path)
- v5v3v6 v2v1v5
(closed path)
Definisi 2.3.4 Sirkuit (Cycle) Cycle dari suatu graf G adalah suatu closed path (path tertutup). Atau dengan kata lain cycle merupakan lintasan yang berawal dan berakhir pada vertex yang sama. Dari gambar di atas, yang merupakan cycle diantaranya : v1v2 v5v6v3v1 . Universitas Sumatera Utara
13 Definisi 2.3.5 Kite graf Kite graf adalah suatu gabungan graf G dengan sebuah path yang mana vertex akhir dari path merupakan vertex dari G.
Definisi 2.3.6 Graf Berbobot Dan Graf Berlabel Graf berbobot graf yang setiap edgenya diberi sebuah bobot sedangkan graf berlabel adalah graf yang tidak memiliki bobot
Gambar 2.10 : Graf Berbobot Dan Graf Berlabel
Definisi 2.3.7 Graf gabungan Misal ada dua buah graf G1 dan G2 dimana himpunan V (G1 ) dan V (G2 ) saling asing begitu juga himpunan E(G1 ) dan E(G1 ) maka gabungan graf dinotasikan G1 ∪G2 adalah graf yang mempunyai himpunan vertex V (G1 ∪G2 ) = V (G1 )∪V (G2 ) dan himpunan edge E(G1 ∪ G2 ) = E(G1 ) ∪ E(G2 ).
Contoh:
Gambar 2.11 : Gabungan Graf Universitas Sumatera Utara
14 2.4 Pemetaan
Definisi 2.4.1 Misalkan A dan B adalah dua himpunan yang tidak kosong. Suatu cara atau aturan yang memasangkan setiap elemen dari himpunan A dengan tepat satu elemen di himpunan B disebut pemetaan dari himpunan A ke himpunan B. Pemetaan dari himpunan A ke himpunan B diberi notasi λ, yaitu λ : A → B.
Selanjutnya himpunan A disebut sebagai daerah asal (domain) dan himpunan B disebut daerah kawan (kodomain). Secara umum, pemetaan dapat digolongkan menjadi 3 golongan sebagai berikut :
Definisi 2.4.2 Pemetaan satu-satu (injektif) adalah pemetaan dimana setiap elemen di daerah kodomain yang berpasangan mempunyai pasangan elemen tepat satu di daerah domain, dapat dituliskan secara matematika berikut : Pemetaan λ : A → B, injektif ↔ ∀x, y ∈ A, λ(x) = λ(y) → x = y
Contoh :
Gambar 2.12 : Pemetaan Satu-satu
Definisi 2.4.3 Pemetaan pada (surjektif) adalah pemetaan dimana semua Universitas Sumatera Utara elemen didaerah kodomain mempunyai pasangan elemen didaerah domain, dapat
15 dituliskan secara matematika berikut : Pemetaan λ : A → B, surjektif ↔ ∀x ∈ A, ∃y ∈ B, 3 λ(x) = y
Definisi 2.4.4 Pemetaan korespondensi satu-satu (bijektif) adalah pemetaan yang memenuhi pemetaan injektif dan pemetaan surjektif. Istilah ini berasal dari kenyataan bahwa setiap elemen domain akan berkorespondensi secara unik ke elemen kodomain dan sebaliknya.
Contoh:
Gambar 2.13 : Pemetaan Korespondensi Satu-satu
2.5 Pelabelan Graf
Definisi 2.5.1 Pelabelan pada suatu graf adalah sebarang pemetaan atau fungsi yang memasangkan unsur unsur graf (vertex atau edge) dengan bilangan (biasanya bilangan bulat positif ). Jika domain dari pemetaan adalah vertex, maka pelabelan disebut pelabelan vertex (vertex labeling). Jika domainnya adalah edge, maka disebut pelabelan edge (edge labeling), dan jika domainnya vertex dan edge, maka disebut pelabelan total (total labeling).
Pada graf terdapat banyak jenis pelabelan.
Definisi 2.5.2 Misalkan G graf dengan himpunan vertex V dan himpunan edge Universitas Sumatera Utara E. Pelabelan ajaib (magic labeling) pada graf G adalah pemetaan bijektif dari
16 E ke himpunan bilangan integer positif yang berbeda, sehingga untuk setiap vertex v ∈ V , penjumlahan semua label edge e yang insiden terhadap vertex v sama.
Berikut ini beberapa jenis pelabelan ajaib pada suatu graf.
a. Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Banyak vertex di G adalah p dan banyak edge di G adalah q. Pelabelan vertex edge ajaib (edge-magic vertex labeling) pada graf G adalah pemetaan bijektif dari V pada himpunan {1, 2, 3, . . . , p} sehingga untuk sebarang edge (xy) di G berlaku (x) + (y) = k untuk suatu konstanta k. Selanjutnya k disebut konstanta ajaib pada G dan G disebut graf vertex edge ajaib. Contoh:
Gambar 2.14 : edge magic vertex labeling
b. Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Banyak vertex di G adalah p, banyak edge di G adalah q dan h merupakan banyak vertex dan edge pada graf G atau h = p + q. Pelabelan total vertex ajaib (vertex-magic total labeling) pada graf G adalah pemetaan bijektif dari V E pada himpunan {1, 2, 3, . . . , h} sehingga untuk sebarang vertex x di P G berlaku λ(x) + λ(xy) = k dengan y merupakan vertex yang berdekatan dengan vertex x. Selanjutnya k disebut konstanta ajaib pada G dan G disebut graf total vertex ajaib. Contoh :
Universitas Sumatera Utara
17
Gambar 2.15 : vertex magic total labeling
c. Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Banyak vertex di G adalah p dan banyak edge di G adalah q. Pelabelan edge vertex ajaib (vertex-magic edge labeling) pada graf G adalah pemetaan bijektif dari E pada himpunan {1, 2, 3, . . . , q} sehingga untuk sebarang vertex x di G berlaku: X
λ(xy)
dengan y merupakan vertex yang berdekatan dengan vertex x. Selanjutnya k disebut konstanta ajaib pada G dan G disebut graf edge vertex ajaib. Contoh:
Gambar 2.16 : vertex magic edge labeling
d. Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Banyak vertex di G adalah p, banyak edge di G adalah q dan h merupakan banyak vertex dan edge pada graf G atau h = p + q. Pelabelan total edge ajaib (edge-magic total labeling) pada graf G adalah pemetaan bijektif dari V E pada himpunan {1, 2, 3, . . . , h} sehingga untuk sebarang edge xy di G berlaku (x) + (xy) + (y) = k. untuk suatu konstanta k. Selanjutnya k disebut konstanta ajaib pada G dan
Universitas Sumatera Utara
18 G disebut graf total edge ajaib. Contoh:
Gambar 2.17 : edge magic total labeling
Universitas Sumatera Utara
