makalah tugas teori graf

Upload: hari-kuswanto

Post on 14-Apr-2018

297 views

Category:

Documents


15 download

TRANSCRIPT

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