7/27/2019 Makalah tugas teori graf

1/18

1. Latar BelakangTeori graf saat ini menjadi topik yang banyak mendapat perhatian, karena model-

model yang terdapat dalam teori graf berguna untuk aplikasi yang luas, seperti masalah dalam

jaringan komunikasi, transportasi, ilmu komputer, riset operasi, dan lain sebagainya. Salah

satu aplikasi dalam teori graf adalah menentukan kota terjauh (maksimal lintasan terpendek)

dari suatu kota ke kota lain yang terdiri dari kumpulan kota dalam suatu daerah.

Misalkan G adalah graf yang memiliki himpunan vertex V(G) dan himpunan edge

E(G), dengan vertex adalah kota dan jalan yang menghubungkan dua kota adalah edge. Jarak

(distance) dari vertex u ke v di G adalah panjang lintasan (path) terpendek dari vertex u ke v,

dinotasikan dengan d(u,v). Jarak (distance) dari vertex u ke setiap vertex di G, dapat

ditentukan dengan menggunakan Algoritma BFS-Moore. Eksentrisitas (eccentricity) vertex u

pada grafG , dinotasikan e(u) adalah jarak terjauh (lintasan terpendek maksimum) dari vertex

u ke setiap vertex di G. Digraf eksentrik dari graf G adalah graf yang memiliki himpunan

vertex yang sama dengan himpunan vertex di G dan arc (edge yang berarah) menghubungkan

vertex u ke vjika v adalah vertex eksentrik dari u. Vertex v merupakan vertex eksentrik dari u

jika d(u,v) = e(u).

Menurut Kusmayadi [1], terdapat beberapa operasi dalam graf seperti operasi union,

join, cartesian product. Double cones adalah salah satu dari kelas-kelas graf. Graf double

cones memiliki vertex dan edge. Sebagai contoh, grafdouble cones DC3 dengan 5vertex dan 9 edge yang disajikan pada Gambar 1.

Gambar 1. GrafDouble cones DC3

Selain contoh dari double conesDC3 akan dijelaskan lebih rinci mengenai operasi-

operasi dalam graf dan digraf eksentrik yang melandasi adanya teorema maupun lemma

dalam double cones. Oleh karena itu, dalam makalah ini akan dibahas mengenai digraf

eksentrik pada grafdouble cones dan operasi dari grafP3 dan C3.

7/27/2019 Makalah tugas teori graf

2/18

2. Rumusan MasalahBerdasarkan latar belakang dapat dirumuskan masalah sebagai berikut,

1. bagaimana hasil union,joint, dan cartesian productdari grafP3 dan C3, dan2. bagaimana menentukan digraf eksentrik dari GrafDouble Cones.

(kayake biasanya pakai tanda tanya)

3. TujuanTujuan dari makalah ini adalah sebagai berikut,

1. dapat menentukan hasil union,joint, dan cartesian productdari grafP3 danC3, dan

2. dapat menentukan digraf eksentrik dari grafdouble cones.

4. Pembahasan4.1. Graf dan Digraf

Berdasarkan Chartand [2] diperoleh definisi-definisi berikut.

Definisi 1. Suatu graf G adalah sebuah kumpulan obyek-obyek yang disebut kumpulan vertex

yang berpasangan antara satu vertex dengan vertex lainnya yang dihubungkan dengan

sebuah edge. Himpunan vertex dan himpunan edge dalam graf disimbolkan dengan dan Definisi 2. Directed graph atau digraf adalah himpunan tidak kosong berhingga yang tediri dari

vertex dengan himpunan (mungkin himpunan kosong) dari pasangan vertex yang berbeda pada yang dihubungkan dengan edge berarah yang disebut arc.

Gambar 2. Contoh (a) Grafdan (b) Digraf

4.2.

Graf P3 dan C3

7/27/2019 Makalah tugas teori graf

3/18

Berikut ini akan diberikan definisi Menurut Chartrand dan Lesniak [1].

Definisi 3.1.1. Graf lintasan adalah graf yang terdiri dari satu lintasan (path).

Gambar 1. Graf LintasanP3

Definisi 3.1.2. Graf cycle Cn adalah suatu connected graf yang membentuk cycle

dengan n-vertex (n 3) dan setiap vertexnya mempunyai degree 2

.

Gambar 2. GrafCycleC3

4.3. Operasi pada GrafMenurut Kusmayadi [1], grafG1 dan G2 dapat dioperasikan dengan cara union,join,

dan cartesian product. Definisi dari operasi-operasi tersebut adalah sebagai berikut.

4.3.1. UnionDefinisi 3.2.1. Union dari G1 dan G2, dinotasikan adalah graf dengan dan .Dari definisi union, maka jika G1 adalah graf lintasanP3dan G2adalah GrafCycleC3

maka disajikan pada gambar 3.

7/27/2019 Makalah tugas teori graf

4/18

Gambar 3. GrafUnion 4.3.2. Joint

Definisi 3.2.2.Joint dari G1 dan G2, dinotasikan , adalah graf terdiri dariunion bersama-sama dengan semua edge , dimana dan dengan

Dari definisijoint, maka jika G1adalah graf lintasanP3dan G2adalah GrafCycleC3

maka disajikan pada gambar 4.

Gambar 4. GrafJoint 4.3.3. Cartesian Product

Definisi 3.2.3. Cartesian Product dari G1 dan G2 , dinotasikan

merupakan

graf yang memiliki himpunan vertex dan dua vertex dan

7/27/2019 Makalah tugas teori graf

5/18

adjacent dalam jika hanya jika dan , atau dan .Dari definisi Cartesian Product, maka jika G1 adalah graf lintasanP3dan G2adalah

GrafCycleC3 maka disajikan pada gambar 5.

Gambar 5. GrafCartesian Product 4.4.Algoritma BFS-Moore

Definisi dari jarak (distance) menurut Kusmayadi [1] adalah sebagai berikut

Definisi 3.3.1 Jarak (distance) dari vertex u ke v di G adalah panjang lintasan (path)

terpendek dari vertex u ke v, dinotasikan dengan d(u,v). Jika tidak ada lintasan yang

menghubungkan vertex u dan v, maka d(u,v) = .

Dari definisi jarak, dapat dikatakan jika tidak ada lintasan yang menghubungkan

vertex u dan v, maka d(u,v)=. Selanjutnya, untuk menyelesaikan masalah lintasan terpendek

dalam suatu graf G digunakan algoritma BFS (Breadth First Search) Moore. Langkah-

langkah algoritma BFSMoore adalah

1. diambil salah satu vertex, misal u, dan dilabeli 0 yang menyatakan jarak dari u ke dirinyasendiri, sedangkan semua vertex selain u dilabeli,

2. semua vertex berlabel yang adjacentdengan u dilabeli 1,

7/27/2019 Makalah tugas teori graf

6/18

3. semua vertex berlabel yang adjacentdengan vertexberlabel 1 dilabeli 2 dan demikianseterusnya sampai vertex yang dimaksud, misal v, sudah berlabel hingga. Dalam hal ini,

label dari setiap vertex menyatakan vertex dari vertex u.

Sebagai ilustrasi, diberikan grafG pada Gambar 6.

AlgoritmaBFS-Moore digunakan untuk menentukan jarakvertex u ke setiap vertex di

G, dengan langkah-langkahsebagai berikut.

1. Vertex u dilabeli 0 dan semua vertex selain u dilabeli .2. Semua vertex berlabel yang adjacentdengan u, yaitu 21 , vv dan 5v dilabeli 1.

3.

Semua vertexberlabel

yang adjacentdengan vertex berlabel 1, yaitu,

3v

64 ,vv

dan

10v , dilabeli 2.

4. Semua vertexberlabel yang adjacentdengan vertex berlabel 2, yaitu ,7v dilabeli 3.Dari langkah-langkah di atas diperoleh label untuk tiap-tiap vertex sebagaimana dapat

dilihat pada Gambar 6.

Gambar 6. Graf untuk Menggambarkan Jarak

4.5.Digraf eksentrik

Digraf eksentrik dan eksentrisitas menurut Kusmayadi [1] adalah sebagai berikut.

7/27/2019 Makalah tugas teori graf

7/18

Definisi 3.4.1.Digraf eksentrik dari graf G, dinotasikan ED(G) adalah graf yang

memiliki himpunan vertex yang sama dengan himpunan vertex di G, V(ED(G)) = V(G), dan

arc (edge yang berarah ) menghubungkan vertex u ke v jika v adalah vertex eksentrik dari u.

Definisi 3.4.2.Eksentrisitas (eccentricity) vertex u, dinotasikan e(u), dalam graf G

adalah jarak terjauh (lintasan terpendek maksimum) dari vertex u ke setiap vertex di G,

dapat dituliskan

e(u)=max(d(u,v)|vV(G))Menurut Kusmayadi [1], radius dari adalah eksentrisitas minimum pada setiap

vertex di yang dinotasikan dengan rad(G) atau dapat dituliskan rad(G)=min{e(u)|uV(G)}.Sedangkan diameter dari

adalah eksentrisitas maksimum pada setiap vertex di

yang

dinotasikan dengan diam(G) atau dapat ditulis diam(G)=max{e(u)|uV(G)}. Jikae(u)=rad(G), maka vertex u disebut vertex pusat (central vertex). Vertex v merupakan vertex

eksentrik (eccentric vertex) dari u jika d(u,v)=e(u).

Definisi 3.4.3. Digraf eksentrik dari graf G, dinotasikan ED(G) adalah graf yang

memiliki himpunan vertex yang sama dengan himpunan vertex di G, V(ED(G)) = V(G), dan

arc (edge yang berarah ) menghubungkan vertex u ke v jika v adalah vertex eksentrik dari u

Sama dengan definisi 3.4.1

Untuk menentukan digraf eksentrik dari grafG adalah sebagai berikut,

1. Menentukan jarak (distance) dari vertex u ke setiap vertex dalam graf G.2. Menentukan eksentrisitas setiap vertex-nya dan vertex eksentriknya.3. Eksentrisitas vertex dan vertex eksentrik disajikan dalam suatu Tabel.4. Selanjutnya antara setiap vertex dengan vertex eksentriknya dihubungkan oleh arc,

sehingga diperoleh digraf eksentrik yang merupakan komplemen dari graf G dimana

setiap edge-nya diganti dengan arc.

Diberikan contoh untuk menentukan digraf eksentrik dari graf G pada Gambar 7.

Langkah pertama adalah dengan menentukan eksentrisitas tiap vertexnya dan vertex

eksentrisitasnya terlebih dahulu

7/27/2019 Makalah tugas teori graf

8/18

.

Gambar 7. Graf untuk mengilustrasikan Eksentrisitas

Tabel 1 menjelaskan eksentrisitas vertex, vertex eksentrik, radius, diameter, dan center

dari graf

pada Gambar 7.

Tabel 1. Tabel eksentrisitas

Vertex Eksentrisitas vertex Vertex eksentrik

Dari Tabel 1 didapatkan dan . Setelah diperoleh vertexeksentrisitas dari setiap vertex. Selanjutnya antara setiap vertex dihubungkan dengan arcsehingga diperoleh digraf eksentrik yang merupakan komplemen dari graf dimana edge-nya diganti dengan arc. Gambar 8 menunjukkan digraf eksentrik dari Gambar 7.

7/27/2019 Makalah tugas teori graf

9/18

Gambar 8. Digraf eksentrik dari graf4.4.GrafDouble ConesDefinisi dari grafdouble cones menurut Kusmayadi [1] adalah sebagai berikut

Definisi 4.4.1. Graf double cones (DCn) adalah himpunan vertex V(DCn)) =* + dan himpunan edge E(DCn) = * +, dimana edge , edge , dan edge untuk setiap.Contoh grafdouble cones secara umum dapat dilihat pada gambar 9.

Gambar 9. GrafDouble Cones

7/27/2019 Makalah tugas teori graf

10/18

Definisi 4.4.2. Graf double cones, dinotasikan , adalah join dari cycle dankomplemen

, sehingga dapat dituliskan

untuk

.

Graf double cones memiliki n+2 vertex dan 3n edge. Sebagai contoh, graf double

cones DC3 dan DC4 disajikan pada Gambar 10 dan Gambar 11.

Gambar 10. Graf DC3

7/27/2019 Makalah tugas teori graf

11/18

Gambar 11. Graf DC4

4.5.Digraf eksentrik dari GrafDouble Cones

4.5.1. Digraf eksentrik dari GrafDouble Cones DC3Graf double cones DC3 memiliki himpunan vertex

*+

dan himpunan edge * +, dimana edge , edge , dan edge untuk setiap . Graf double conesuntuk dapat dilihat pada gambar 12.

Gambar 12. GrafDouble Cones DC3

7/27/2019 Makalah tugas teori graf

12/18

Dari gambar 12, dapat ditentukan jarak (distance) menggunakan algoritma BFS-

Moore, selanjutnya dapat ditentukan eksentrisitas tiap vertexnya dan vertex eksentriknya.

Eksentrisitas vertex dan vertex eksentrik pada grafdouble cones disajikan dalam tabel 2.Tabel 2. Eksentrisitas GrafDC3

Vertex Eksentrisitas vertex Vertex Eksentrik

u0 e(u0)=2 u1

u1 e(u1)=2 u0

v0 e(v0)=1 v1,v2,u0 ,u1

v1 e(v1)=1 v0,v2,u0 ,u1

v2 e(v2)=1 v0,v1,u0 ,u1

Dari tabel 2, diperoleh rad(DC3)=1, diam(DC3)=2, dan vertex v0,v1, dan v2

merupakan vertexpusat. Digraf eksentrik dariDC3 disajikan pada gambar 13.

Gambar 13. Digraf eksentrik dari grafDouble Cones DC3

Akibat 4.5.1.1.Misalmerupakan graf double cones untuk , makaEksentrisitas

7/27/2019 Makalah tugas teori graf

13/18

Bukti

Dari observasi, terlihat bahwa jarak terjauh dari vertex ui adalah 2 jika ke vertexuj

dengan i,j=0,1 dimana j i, sehingga e(ui)=2 untuk setiap i = 0,1. Selain itu, jarak terjauh

dari vertexvi adalah 1 jika ke semua vertex pada grafDC3 kecuali ke dirinya sendiri dengan i

= 0,1,2, sehingga e(vi) = 1, untuk setiap i=0,1,2.

Akibat 4.5.1.2.Misal DCn merupakan graf double cones untuk n=3, maka

Vertex eksentrisitas Bukti

Eksentrisitas semua vertex yang telah diperoleh digunakan untuk menentukan vertex

eksentrik dari semua vertex pada grafdouble cones DC3. Dari Akibat 1 e(ui)=2, maka vertex

eksentrik dari ui adalah vertexuj untuk setiap i,j = 0,1 dimanaj i. Di samping itu, e(vi)=1,

maka vertex eksentrik dari vi adalah vertexu0, u1, dan vj untuk setiap i,j = 0,1,2 dimanaj i.

Akibat 4.5.1.3.Misal DCn merupakan graf double cones untuk n=3, maka digraf eksentiknya

adalah digraf dengan himpunan vertex

V(ED(DC3))={ u0,u1,v0,v1,v3}

dan himpunan arc

A(ED(DC3)) Bukti

Arc diperoleh dengan menghubungkan setiap vertex ke vertex eksentriknya pada grafdouble cones DC3. Dari akibat 2, vertex eksentrik dari vertexui adalah vertex uj, untuk setiap

i,j = 0 dimanaj i, sehingga ui dihubungkan ke ujmembentukarcui uj. Di lain pihak, vertex

eksentrik dari vertex vi adalah vertex u0,u1, dan vj untuk setiap i,j = 0,1,2 dimana j i,

sehingga dari vi dihubungkan ke vertex u0,u1, dan vj membentuk arc viu0, viu1, vivj. Maka

terbentuk digraf eksentrik dari graf double cones DC3 dengan himpunan vertex

V(ED(DC3))= V(DC3) dan himpunan arcA(ED(DC3)) tersebut.

7/27/2019 Makalah tugas teori graf

14/18

Teorema 4.5.1. Misal DCn merupakan graf double cones untuk n=3, maka digraf eksentik

ED(DC3) adalah C3 + K2 dengan karakteristik memiliki himpunan vertex V(ED(CD3))= {u0,

u1, v0, v1, v2} dan himpunan arc

A(ED(DC3)) Bukti

Dari akibat 3, arc dari vertex ui adjacent keluar ke vertex vj untuksetiap i,j=0,1 dimana ji

dan arc dari vertex vi adjacent.

4.5.2. Digraf eksentrik dari GrafDouble Cones DCnuntukn>3Untuk mencari jarak dari setiap vertex ke vertex lainnya pada grafdouble cones

untuk , digunakan algoritma BFS Moore. Diperoleh jarak dari vertex untuk setiap adalah 0 jika ke dirinya sendiri, 2 bila ke vertexuntuk setiap dimana dan 1 bila ke semua vertex untuk setiap . Sedangkan jarakvertexuntuksetiap

adalah 0 jika ke dirinya sendiri, 1 jika ke vertex

untuk setiap

dan vertexuntuk mod n dan dan 2 jika ke vertex untuksetiap dimana mod n, mod n dan .,s\ 0Akibat 4.5.2.1.Misal merupakan graf double cones untuk , maka

Bukti

Dengan algoritma BFS Moore diperoleh bahwa jarak terjauh dari vertex adalah 2jka ke vertex untuk setiap dimana , sehingga eksentrisitasvertex adalah 2. Demikian juga jarak terjauh dari vertex adalah 2 jika ke vertex untuk setiap dimana dan ,sehingga eksentritas vertex adalah 2.

7/27/2019 Makalah tugas teori graf

15/18

Akibat 4.5.2.2.Misal merupakan graf double cones untuk , maka

Bukti

Eksenrisitas semua vertex yang telah diperoleh digunakan untuk menentukan vertex

eksentrik dari semua vertex pada graf double cones untuk Dari Akibatn 2.4.5,eksentrik dari vertex

adalah vertex

untuk setiap

dimana. Selain itu,

eksentrisitas dari vertex yaitu 2, maka vertex eksentrik dari adalah vertex untuk dimana dan .Akibat 4.5.2.3. Misal merupakan graf double cones dengan , maka digrafeksentriknya adalah digraf dengan himpunan vertex () * +,

untuk

dimana

dan himpunan arc() untuk , dimana .

Bukti

Arc diperoleh dengan menghubungkan setiap vertex pada grafdouble cones dengan

pada vertex eksentriknya. Dari Akibat 6, didapat:1. Vertex eksentrik dari vertex adalah vertex , untuk , dimana

sehingga dihubungkan ke dan membentuk suatu arc .2. Vertex eksentrik dari vertex adalah vertex untuk , dimana sehingga dihubungkan ke dan

membentuk suatu arc .Maka terbentuk digraf eksentrik dari graf double cones

dengan

yang

himpunan vertexnya () =, dan himpunan arc() tersebut.

7/27/2019 Makalah tugas teori graf

16/18

Teorema 4.5.2. Misal graf merupakan graf double cones untuk , maka digrafeksentrik adalah digraf dengan karakteristik memiliki himpunan vertex() * +, dan himpunan arc untuk dimana

() untuk , dimana .

Bukti

Dari Akibat 7(akibat dimana?), didapat:

1. Arc dari vertexadjacentkeluar ke vertex untuk setiap dimana ,sehingga didapatkan membentuk digraf.

2. Arc dari vertex adjacent keluar ke vertex untuk setiap ,dimana sedemikian sehinggasemua arc-nya simetrik, dan didapatkan bahwa vertex

akan adjacent keluar ke

seluruh vertex kecuali vertex dan vertex , sehingga vertex * +dan arc * + membentuk digraf .Dengan demikian dapat disimpulkan bahwa digraf eksentrik dari graf double cones

untuk adalah digraf dengan himpunan vertex() * +, dan himpunan arc () { | + {| +.

7/27/2019 Makalah tugas teori graf

17/18

Gambar 11. GrafDouble Cones untuk dan digraf eksentriknya5. Kesimpulan

1. Operasi-operasi dalam graf yaitu ada union, joint, dan Cartesian product. Union dari dan , dinotasikan , adalah graf dengan dan . Jointdari G1dan G2, dinotasikan G1 + G2, adalah grafterdiri dari union bersama-sama dengan semua edge , dimana dan dengan . Sedangkan Cartesian Product dari G1 dan G2,dinotasikan , merupakan graf yang memiliki himpunan vertex dan dua vertex (u1, u2) dan (v1, v2) adjacentdalam

jika dan hanya jika

dan ), atau dan 2. Digraf eksentrik yang merupakan komplemen dari graf dimana edge-nya diganti dengan arc.3. Digraf eksentrik dari double cones dengan himpunan vertexnya

dan himpunan arc() diperoleh dengan menghubungkan setiapvertex pada grafdouble conespada vertex eksentriknya didapatkan

a. Vertex eksentrik dari vertex adalah vertex , untuk , dimana sehingga

dihubungkan ke

dan membentuk suatu arc

.b. Vertex eksentrik dari vertex adalah vertex untuk , dimana sehingga dihubungkan ke dan

membentuk suatu arc .

7/27/2019 Makalah tugas teori graf

18/18

DAFTAR PUSTAKA

[1] Kusmayadi, T. A., Graf dan Digraf Eksentrik, UNS Press, Solo, 2011.

[2] Chartrand, G, Introductory of Graph Theory, Western Michigan University,

Dover Publication Inc.,New York, 1977.