Teori Graph Widya

BAB

I

PENDAHULUAN

1.1 Latar Belakang Teori graf merupakan salah satu bidang matematika, yang diperkenalkan pertama kali oleh ahli matematika asal Swiss, Leonardo Euler pada tahun 1736. Ide besarnya muncul sebagai upaya menyelesaikan masalah jembatan K o nisberg. Dari permasalahan itu, akhirnya Euler mengembangkan beberapa konsep mengenai Teori graf. Salah satu topik menarik dalam teori graf adalah eksentris digraf pada graf, ED (G), yang diperkenalkan pertama kali oleh Fred Buckley (Boland, J.,1999). Misalkan G adalah graf dengan himpunan titik V(G) dan himpunan sisi E(G). Jarak dari u ke v di G, dinotasikan d(u,v), adalah panjang lintasan terpendek dari u ke v. Jika tidak ada lintasan titik u dan v, maka d(u,v) = ∞. Eksentrisitas titik v dalam graf G, dinotasikan e(v), adalah jarak terjauh (maksimal lintasan terpendek) dari v ke setiap titik di G. Titik u adalah titik eksentrik dari v jika jarak dari u ke v sama dengan eksentrisitas dari v atau d(u, v) = e(v). Eksentris digraf pada graf, ED (G), didefinisikan sebagai graf yang mempunyai himpunan titik yang sama dengan G, V(ED (G)) = V(G), dimana arc (sisi yang mempunyai arah) menghubungkan titik u ke v, jika v adalah titik eksentrik dari u. Contoh graf dan eksentrik digrafnya diberikan pada gambar 1.1. Buckley menyimpulkan bahwa hampir setiap graf G, eksentrik digrafnya adalah ED (G) = ( G )*, dimana ( G )* adalah komplemen dari G yang setiap sisinya diganti dengan arc simetrik.

1

3

v1

v2

v1 v5

v4

v3

v2 v5

v6 v3

v6

v4

G

ED(G) Gambar 1.1 graf dan eksentrik digrafnya

Boland (1999) memperkenalkan eksentris digraf pada digraf, ED (D). Teori ini terinspirasi dari penelitian yang dilakukan oleh Buckley. Tetapi graf yang dikaji adalah graf berarah (digraf) dengan himpunan titik dan arc. Titik u menyatakan arc yang dapat dicapai dari v dalam digraf D jika terdapat lintasan berarah dari v ke u. Eksentrisitas titik v dalam digraf D, dinotasikan e(v), adalah jarak dari v ke titik terjauh dari v. Eksentris digraf pada digraf, ED (D), didefinisikan sebagai graf yang mempunyai himpunan titik yang sama dengan G, V(ED (G)) = V(G), dimana arc menghubungkan titik v ke u, jika dan hanya jika u adalah titik eksentrik dari v.

1.2 Masalah Permasalahan yang kita bahas dalam skripsi ini adalah eksentrik digraf pada kelas-kelas graf, khususnya graf path (lintasan), graf cycle (sikel) dan graf complete (lengkap).

1.3 Batasan Masalah Pada skripsi ini graf yang dikaji adalah graf sederhana dan graf hingga. Dimana graf sederhana adalah graf yang tidak memuat loop dan sisi rangkap (multiple edges). Loop adalah sisi yang menghubungkan suatu titik dengan dirinya

sendiri. Jika terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut dinamakan sisi rangkap. Sedangkan graf hingga didefinisikan sebagai graf

3

yang mempunyai order terbatas. Order didefinisikan sebagai banyaknya titik yang ada dalam graf.

1.4 Tujuan Penulisan skripsi ini bertujuan untuk mendapatkan eksentrik digraf dari graf lintasan, graf sikel dan graf lengkap.

1.5 Manfaat Manfaat yang dapat diambil dari penelitian ini adalah dapat menentukan maksimal lintasan terpendek dari suatu titik ke titik yang lain. Hal ini dapat diaplikasikan dalam sistem saluran air PDAM, sistem aliran listrik PLN dan sebagainya.

B A B II TINJAUAN PUSTAKA

2.1 Graf dan Digraf Graf tak berarah (Undirected Graph) G didefinisikan sebagai pasangan himpunan (V(G), E(G)) dimana V(G) adalah himpunan tak kosong dari elemen-elemen yang disebut titik (vertex) dan E(G) adalah himpunan (mungkin kosong) dari pasangan tak terurut (u,v) dari titik titik u,v di V yang disebut sisi (edge). Selanjutnya sisi e = (u,v) dalam graf G akan ditulis dengan e = uv dan graf tak berarah G akan disebut dengan graf G saja. Sebagai contoh graf G diberikan pada Gambar 2.1. v4

v1 e5

e4 v5

e1

e3

e6 v2

e2

v3

Gambar 2.1 Graf G dengan 5 titik dan 6 sisi

Graf G pada Gambar 2.1 adalah graf dengan himpunan titik V(G) = {v1, v2, v3, v4, v5} dan himpunan sisi E(G) = {e1, e2, e3, e4, e5, e6} yaitu pasangan tak terurut dari {v1 v2, v2v3, v3 v4, v4 v5, v5v1, v5v2}. Digraf (Graf berarah/ Directed Graph) D adalah pasangan himpunan (V(D), A(D)) dimana V(D) adalah himpunan tak kosong dari elemen-elemen yang disebut titik (vertex) dan A(D) adalah himpunan dari pasangan terurut (uv), yang mempunyai arah dari u ke v, dari titik-titik u,v di V yang disebut arc. Arc yang menghubungkan titik u ke titik v dan titik v ke titik u dinamakan arc simetrik, yang dinotasikan dengan a = uv . Contoh digraf D diberikan pada Gambar 2.2, dengan 4

5

himpunan titik V(D) = {v1, v2, v3, v4, v5} dan himpunan arc A(D) = {a1, a 2 , a3, a4, a5, a 6 } yaitu pasangan terurut dari {v1v2, v 2v 3 , v3v4, v4v5, v1v5, v5v 2 }. v4

v1 a5

a4

a1

v5

a3

a6 v2

a2

v3

Gambar 2.2 Digraf D dengan 5 titik dan 6 sisi

2.2 Definisi dan Notasi Order n dari graf G adalah banyaknya titik yang ada di G yaitu n. Graf yang mempunyai order terbatas dinamakan graf hingga. Sebagai contoh Gambar 2.3 adalah graf order 4. v1

v2

v4

v3

Gambar 2.3 Graf G order 4

Dalam suatu graf G, apabila suatu titik v dihubungkan dengan dirinya sendiri atau e = vv, maka sisi e dinamakan loop. Jika terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut dinamakan sisi rangkap (multiple edges). Graf yang tidak memuat loop dan sisi rangkap dinamakan graf sederhana (simple graf). Pada skripsi ini, graf yang dikaji adalah graf sederhana dan graf hingga.

6

Contoh graf yang memuat loop dan sisi rangkap diberikan pada Gambar 2.4, dimana e2 dan e4 adalah loop, sedangkan sisi e6 e7 adalah sisi rangkap. v1

v2 e1

e2

e6 e8

e7

e3

e5 v3

v4

e4

Gambar 2.4 Graf dengan loop dan sisi rangkap

Jika dua titik v1 dan v2 di graf G dihubungkan oleh suatu sisi e, maka titik v1 dan v2 dikatakan adjacent (tetangga) dan sisi e insiden dengan kedua titik yang dihubungkan. v1

e4 v4

e1 e5

e3

v2

e2 v3

Gambar 2.5 Graf untuk mengilustrasikan adjacent dan insiden

Pada Gambar 2.5, titik-titik yang adjacent adalah v1 dan v2, v2 dan v3, v3 dan v4, v4 dan v1, v1 dan v3, sedangkan sisi e1 insiden dengan v1 dan v2, e2 insiden dengan v2 dan v3, e3 insiden dengan v3 dan v4, e4 insiden dengan v4 dan v1, dan e5 insiden dengan v1 dan v3. Derajat (degree) dari titik v adalah jumlah sisi yang berinsiden dengan titik v, dinotasikan dengan deg (v). Misalkan pada gambar 2.5, deg (v1) = deg (v3) = 3 dan deg (v2) = deg (v4) = 2. Jika setiap titik dalam suatu graf G mempunyai derajat yang sama, maka graf tersebut dinamakan graf reguler.

7

Sebuah jalan (walk) W pada graf G adalah barisan berhingga yang diawali dan diakhiri dengan titik, yaitu: (n ≥ 0)

W = v0, e1, v1, e2, v2, e3, . . ., vn-1, en, vn

dimana suku-sukunya bergantian antara titik dan sisi, sedemikian hingga (vi,vi+I) adalah sisi di G, untuk 1≤ i ≤ n-1. Jalan dikatakan tertutup jika v0 = vn dan terbuka jika v0 ≠ vn. Suatu jalan yang barisan titik-titiknya tidak ada pengulangan dinamakan lintasan (path), tetapi jika yang berbeda adalah sisi-sisinya, maka jalan tersebut disebut jejak (trail). Sikel (cycle) didefinisikan sebagai jalan tertutup dengan barisan titik yang berbeda. Dengan kata lain, sikel adalah suatu lintasan yang tertutup. v1

e1

v2 e2

e5

e6

v3

e7 e3

v5

e4

v4

Gambar 2.6 Graf untuk mengilustrasikan jalan

Barisan v1, e1, v2, e7, v4, e6, v1, e5, v5, e4, v4, e3, v3 dari Gambar 2.6 adalah jalan, barisan v1, e1, v2, e2, v3, e3, v4, e4, v5 adalah lintasan, barisan v1, e1, v2, e7, v4, e6, v1, e5, v5, e4, v4, e3, v3 adalah jejak dan barisan v1, e1, v2, e2, v3, e3, v4, e4, v5, e5, v1 adalah sikel.

2.3 Graf Terhubung dan Komplemen Graf Graf H dikatakan subgraf dari graf G jika setiap titik di H adalah titik di G dan setiap sisi di H adalah sisi di G. Dengan kata lain V(H) ⊆ V(G) dan E(H) ⊆ E(G). Pada Gambar 2.7, G1 adalah subgraf dari G tetapi G2 bukan subgraf dari G karena ada sisi v2 v3 di G2 yang bukan merupakan elemen dari E(G).

8

G:

v1

G1: v2

v4

v1

G2: v2

v4

v2

v4

v3

v3

v1

v3

Gambar 2.7 Graf dan subgraf

Jika setiap pasang titik di graf G ada lintasannya, maka G dinamakan terhubung (connected). Komponen dari graf adalah subgraf terhubung maksimal dari G. Jadi, setiap graf terhubung hanya mempunyai satu komponen. Sedangkan untuk graf tak terhubung, memiliki sedikitnya dua komponen. Gambar 2.8 adalah contoh untuk graf terhubung dan graf tak terhubung.

(a)

(b)

Gambar 2.8 Graf terhubung dan graf tak terhubung

Misalkan ada dua graf G1 dan G2, dimana himpunan titik V(G1) dan himpunan titik V(G2) saling asing, begitu juga himpunan sisi E(G1) dan himpunan sisi E(G2). Gabungan dari G1 dan G2 dinotasikan dengan G1 ∪ G2, adalah graf dengan himpunan titik V(G1 ∪ G2) = V(G1) ∪ V(G2) dan himpunan sisi E(G1 ∪ G2) = E(G1) ∪ E(G2).

9

Sebagai contoh graf gabungan diberikan pada Gambar 2.9. v1

v1

G1: v3

v2

G2: v1

v2

G : G1 ∪ G2

v3

v2

v4

v5

Gambar 2.9 Gabungan graf

Komplemen dari Graf G, dinotasikan dengan G , adalah graf dengan himpunan titik yang sama dengan himpunan titik di G, dengan kata lain V(G) = V( G ), dan titik u,v di G adalah adjacent jika dan hanya jika titik u,v di G tidak adjacent. Contoh graf dan komplemennya dapat dilihat pada Gambar 2.10. v2

v2 v1

v1 v3 v5

v4

v3 v5

G

v4 G G

Gambar 2.10 Graf dan komplemennya G

2.4 Kelas-kelas Graf Graf terbagi dalam beberapa kelas. Pada skripsi ini, kelas graf yang kita kaji adalah graf path (lintasan), graf cycle (sikel) dan graf complete (lengkap).

10

2.4.1

Graf Path (lintasan) Graf path (lintasan) ialah graf yang terdiri dari satu lintasan. Graf lintasan

dengan n titik, dinotasikan dengan Pn. Beberapa contoh dari graf lintasan, diberikan pada Gambar 2.11. P1

:

P2

:

P3

:

v1 v1

v2

v1

v2

v3

Gambar 2.11 Graf lintasan

2.4.2

Graf cycle (sikel) Graf cycle (sikel) ialah graf yang terdiri dari satu sikel. Graf sikel dengan n

titik, dinotasikan dengan Cn. Pada graf sikel, jumlah titiknya minimal 3. Gambar 2.12 adalah contoh dari graf sikel. v1

v1

v2 v5

v3

v2 C3

v4

v3 C4 Gambar 2.12 Graf sikel

v2

v3

v4 C5

11

2.4.3

Graf Complete (lengkap) Graf complete (lengkap) didefinisikan sebagai graf dimana setiap dua titik

berbeda di G dihubungkan dengan sisi. Graf lengkap dengan n titik dinotasikan dengan Kn. Beberapa contoh dari graf lengkap, diberikan pada Gambar 2.13. v1

v1

v1

v2 v5

v3

v2 K3

v4

v3 K4

v2

v3

v4 K5

Gambar 2.13 Graf lengkap

2.4.4

Graf n - partit Graf n- partit didefinisikan sebagai graf dimana himpunan titik V(G) dapat

dipisah menjadi n himpunan titik, yaitu V1(G), V2(G), …, Vn(G). Sisi-sisi pada graf n-partit terhubung dari titik-titik pada Vi(G) ke titik-titik pada himpunan titik selain Vi(G) atau Vi (G ) , dimana Vi (G ) adalah komplemen dari Vi(G). Untuk n = 2, dinamakan graf bipartit. Jika V1 = k dan V2 = l, maka graf bipartit tersebut dinotasikan dengan Bk,l. Sedangkan untuk n = 3, dinamakan graf tripatit, yang dinotasikan dengan Tk,l,m. Contoh graf bipartit dan graf tripartit dapat dilihat pada Gambar 2.14

12

v1

V1

v3

v2

v1

v2

v3 V1

V 2 v4 v5 V2

v5

v4

v6

B3,2

v7

V3 v8

T3,2,3 Gambar 2.14 Graf bipartit dan graf tripartit

2.5 Eksentrisitas Jarak (distance) antara titik u dan v di graf G, dinotasikan dengan d(u,v) adalah panjang lintasan terpendek dari u ke v di G. Jika tidak ada lintasan dari titik u ke v, maka d(u,v) = ∞. v1

v2

v5

v4

v3

v6

v7

Gambar 2.15 Graf untuk mengilustrasikan jarak

Pada Gambar 2.15, d(v1, v3) = d(v1, v4) = 2, d(v2, v6) = ∞. Untuk masalah lintasan terpendek, kita akan bahas mengenai algoritma BFS (Breadth First Search) Moore. Ini berarti bahwa didalam setiap langkah, algoritma itu mengunjungi semua titik yang adjacent dari titik yang dicapai pada langkah tersebut. Algoritma BFS Moore untuk lintasan terpendek, dimana semua sisi mempunyai panjang 1, adalah: [G = (V(G), E(G), u, v] 1.

Mengambil salah satu titik, misal u, dan diberi label 0

13

2.

Semua titik yang adjacent dengan u diberi label 1

3.

Semua titik yang adjacent dengan 1 diberi label 2 dan demikian seterusnya sampai titik yang dimaksud, misal v, sudah berlabel

4.

Selanjutnya penelusuran langkah mundur menghasilkan lintasan terpendek, yaitu k (= label titik v), k – 1, k – 2, ..., 0. Eksentrisitas titik v di graf G, dinotasikan e(v), adalah jarak terjauh

(maksimal lintasan terpendek) dari v ke setiap titik di G, dengan kata lain: e(v) = max { d(v, u)  u ∈ V(G)}. Titik v adalah titik eksentrik dari u jika jarak dari v ke u sama dengan eksentrisitas dari u atau d(v, u) = e(u). Radius pada graf G, dinotasikan dengan rad(G), adalah eksentrisitas minimum dari G. Sedangkan diameter pada graf G, dinotasikan dengan diam (G), didefinisikan sebagai eksentrisitas maksimum dari G. Sebuah titik pada G, dinamakan titik sentral jika eksentrisitasnya adalah sama dengan rad (G), dengan kata lain e(u) = rad (G). Center dari graf G adalah subgraf pada G yang terbentuk dari titik sentral yang saling dihubungkan. v1

v2

v6

v3

v5

v4

Gambar 2.16 Graf untuk mengilustrasikan eksentrisitas

Dari graf G pada Gambar 2.16: e(v1) = 3 dengan titik eksentrik v4; e(v2) = 2 dengan titik eksentrik v4 dan v5; e(v3) = 2 dengan titik eksentrik v1 dan v6; e(v4) = 3 dengan titik eksentrik v1;

14

e(v5) = 2 dengan titik eksentrik v1 dan v2; e(v6) = 2 dengan titik eksentrik v3 dan v4.

Setelah titik eksentrik dari setiap titik v di G didapatkan, maka antara titik v dengan titik eksentriknya dihubungkan oleh arc. Graf yang dihasilkan dinamakan eksentrik digraf dari graf G, ED(G), yang didefinisikan sebagai graf yang mempunyai himpunan titik yang sama dengan G atau V(ED(G)) = V(G) dimana arc menghubungkan titik u ke v, jika v adalah titik eksentrik dari u. Contoh graf dengan eksentrik digrafnya diberikan pada gambar 2.17. Eksentrik digraf dari graf lintasan, graf sikel dan graf lengkap akan dibahas secara lengkap pada BAB III.

v1

v2

v3

v1

v3

v2

v5

v6 v6

v5 G

v4 ED(G)

Gambar 2.17 Graf G dan eksentrik digrafnya

v4

15

B A B III HASIL DAN PEMBAHASAN

Pada bab ini, akan kita bahas mengenai eksentrik digraf pada graf lintasan, graf sikel dan graf lengkap. Diasumsikan bahwa pada graf lintasan, graf sikel dan graf lengkap, jarak antara dua titik berbeda yang adjacent adalah 1. 3.1 Eksentrik Digraf pada Graf Lintasan Misalkan graf lintasan Pn dengan himpunan titik V(Pn) = {v1, v2, v3, ..., vn} dan himpunan sisi E(Pn) = {e1, e2, e3, ..., en-1} dimana ei = vivi+1

untuk setiap i = 1, 2, ..., n.

Eksentrisitas titik v pada graf lintasan Pn untuk n ganjil adalah sebagai berikut: e(v1) = e(vn) = n - 1 e(v2) = e(vn-1) = n – 2


e( vn+1) = e(v 2

) n= 1n -

n-

2

n +1

,

2

maka e(vi) = n – i

untuk i = 1, 2, …,

e(vi) = i – 1

untuk i =

n +1 2

dan

n+3 n+5 ,

2

, …, n

2

Jadi dapat disimpulkan bahwa eksentrisitas titik e(vi) pada graf lintasan Pn untuk n ganjil adalah:

 n − i e(vi) =  i −1 î

untuk i = 1, 2, ..., untuk i =

n +1 2

n+3 n+5 ,

2

, ..., n

2

Setelah nilai eksentrisitas e(vi) diperoleh, maka kita dapat menentukan titik eksentriknya dengan mudah, yaitu:

16

  vn titik eksentrik dari v i =   v1 î

untuk i = 1, 2, ...,

n +1

2 n +1 n + 3 untuk i = , , ..., n 2 2

Graf Pn dengan n ganjil mempunyai center berupa titik, yaitu titik v

, sehingga n+1 titik eksentriknya 2

ada 2 yaitu titik v1 dan titik vn, dimana jarak antara v vn. Sehingga akan ada arc dari v berturut-turut dengan a

dan 

ke v1 adalah sama dengan jarak antara v

ke vn dan dari

2

v

ke v1 yang akan kita notasikan secara

n+1

n+1

2.

2 n+1

n+1

ke

n+1

n+1

Eksentrik digraf pada graf lintasan ED(Pn) dengan n ganjil adalah digraf dengan 2 2 himpunan

2

titik V(ED(Pn)) = {v1, v2, v3, ..., vn} dan himpunan arc

A(ED(Pn)) = {a1, a2, a3, ..., an,

}, 

dimana: n+1 2

vivn

n +1

untuk i = 1, 2, 3, ...,

ai =

untuk i =

viv1

2

n +3 n +5 , , ..., n 2

2

dan i 

untuk i =

= viv1

n +1

.

2

Jadi banyaknya arc pada ED(Pn) untuk n ganjil adalah n + 1. Dengan demikian, eksentrik digraf pada graf lintasan ED(Pn) untuk n ganjil adalah digraf tripartit }, V2 = {v1, v2, …, v n-1

} dan V3 = {v

,v

n-1

ganjil2 diberikan pada 2

T1,

,

, …, vn}. Contoh eksentrik digraf dari graf Pn untuk n n+1

Gambar 3.1.

, dengan himpunan titik V1 = {v n-1 2

2

n+3

n+5

2

2

v1 V 2

v1

v2

v3

v1

v2

v2

v3 V1

v3 P3

ED (P3) = T1, 1, 1

V3

17

v1

v2

v3

v4

v5

P5 V2 v2

v1 v1

v2

v3

v3

v5

v4

V1

v4

v5 V3

ED (P5) = T1, 2, 2

v1

v2

v3

v4

v5

v7 a3

v6

P7

v1

v2 v3

v2

v3

v7

v6

v5

V2

V1

v6

v4

v1 v7

v5

v4 V3

ED (P7) = T1, 3, 3

Gambar 3.1 Graf P3, P5, P7 dan eksentrik digrafnya Dengan cara serupa seperti pada n ganjil, maka eksentrisitas titik v pada graf lintasan Pn dengan n genap dapat dijelaskan sebagai berikut: e(v1) = e(vn) = n - 1 e(v2) = e(vn-1) = n – 2 

e(v )n= e(v 2

)n=+2n 2

n

.

2

Sehingga eksentrisitas titik e(vi) pada graf lintasan Pn untuk n genap adalah:

18

 n − i e(vi) =  i −1 î

untuk i = 1, 2, ..., untuk i =

 vn Dengan demikian titik eksentrik dari vi =  v1 î

n

,

2

n+2 n+4 , , ..., n. 2

2

untuk i = 1, 2, ..., untuk i =

n ,

2

n+2 n+4 ,

2

Untuk n genap, eksentrik digraf pada graf lintasan ED(Pn) adalah himpunan titik V(ED(Pn)) = {v1, v2, v3, ..., vn} dan himpunan arc vivn

i = 1, 2, 3, ...,

viv1

i=

digraf dengan

A(Pn) = {a1, a2, a3, ..., an}, dimana:

n 2

ai =

n+2 n+4 ,

2

, ..., n

2

Jadi banyaknya arc pada ED(Pn) untuk n genap adalah n. Dengan demikian untuk eksentrik digraf pada graf lintasan ED(Pn) adalah digraf bipartit B v2, …, v }dan V2 = {v

, ..., n.

2

,v

,

n genap, maka

, dengan himpunan titik V1 = {v1, n n

2 2 , …, vn}. Gambar 3.2 adalah contoh eksentrik digraf pada graf Pn untuk

n genap.

n

n+2

n+2

2

2

2

v1 V 1

v1

v2

v1

v2 v2

P2

V2

ED (P2) = B1, 1

V1 v2

v1

v1

v2

v3

v4

v1

v2

v3

v4 v4

v3 V2 P4

ED (P4) = B2, 2

19

v1

v2

v3

v4

v5

v6

P6

v1

V1 v2 v3

v1

v2

v3

v4

v6

v5

v4

v5 V2

v6

ED (P6) = B3, 3

Gambar 3.2 Graf P2, P4, P6 dan eksentrik digrafnya 3.2 Eksentrik Digraf pada Graf Sikel Misalkan graf sikel Cn mempunyai himpunan titik V(Cn) = {v1, v2, v3, ..., vn} dan himpunan sisi E(Cn) = {e1, e2, e3, ..., en} dimana

i = 1, 2, ..., n − 1 i=n

vivi + 1 î viv1

ei = 

Eksentrisitas titik e(vi) pada graf sikel Cn adalah sama untuk setiap titiknya, yaitu e(v1) = e(v2) = …= e(vn). Hal ini disebabkan karena jarak terjauh (maksimal lintasan terpendek) dari setiap titiknya adalah sama, yaitu

n −1

untuk n ganjil dan

2

n 2

untuk n genap. Jadi eksentrisitas titik e(vi)

pada graf sikel Cn untuk setiap i = 1, 2, ..., n adalah:  n  e(vi) =  2 n −1  î 2 Dengan demikian, untuk n ganjil:

jika n genap jika n ganjil

20

v i + n - 1 dan vi + n + 1

i = 1, 2, ...,

vn dan v1

i=

2

2

n +1

i=

,

n+3 n+5 , , ..., n.

2

2

,

2

2

titik eksentrik dari vi =

v i - n - 1 dan v i - n + 1

n −1

2

2

Eksentrik digraf pada graf sikel, ED(Cn), untuk n ganjil, adalah digraf himpunan titik V(ED(Cn)) = {v1, v2, v3, ..., vn} dan himpunan arc ..., 

n

dengan

A(ED(Cn)) = {a1, a2, ..., an, 

1, 

2,

}, dimana:

 v vi i + n 2- 1 ai =  v vi i - n + 1 î 2

untuk i = 1, 2, ...,

n +1 2

n+3 n+5 untuk i = , , ..., n 2

2

dan



  v vi i + n +2 1 i= v vi i - n - 1 2 î

untuk i = 1, 2, ..., untuk i =

n −1 2

n +1 n + 3 ,

2

, ..., n

2

Jadi jumlah arc dalam ED(Cn) untuk n ganjil adalah dua kali jumlah titiknya, yaitu 2n. Dengan demikian, untuk n ganjil eksentrik digraf pada graf sikel sikel

Cn dengan jarak setiap arcnya

ED(Cn) adalah digraf

n −1 , dimana arcnya adalah arc simetrik. Contoh eksentrik 2

digraf dari graf Cn dengan n ganjil diberikan pada Gambar 3.3. v1

v1

v3

C3

v2

v3

v2 ED(C3) =

C3

21

v1

v5

v2

v4

v1

v1

v5

v2

v3

v4

C5

v1

v3

v4

v3

v5

v2 ED(C5) =

v1

C5

v1

v7

v2

v7

v2

v5

v4

v6

v3

v6

v3

v2

v7

v5

v5

v4

v4

v6

C7

ED(C7) =

v3

C7

Gambar 3.3 Graf C3, C5, C7 dan eksentrik digrafnya Selanjutnya, dengan cara yang sama seperti pada n ganjil, maka titik eksentrik dari graf Cn dengan n genap adalah sebagai berikut:

 v titik eksentrik dari vi =  v î

i+n

untuk i = 1, 2, ...,

2

i-n 2

untuk i =

n 2

n+2 n+4 ,

2

, ..., n

2

Eksentrik digraf dari graf sikel, ED(Cn), untuk n genap, adalah digraf himpunan titik V(ED(Cn)) = {v1, v2, v3, ..., vn} dan himpunan arc

A(ED(Cn)) = {a1, a2, a3, ..., an},

dimana:

  v vi i + n2 ai =   vv i- n i î 2

n untuk i = 1, 2, ..., , 2

n+2 n+4 untuk i = , , ..., n. 2

dengan

2

22

Jadi jumlah arc dalam ED(Cn) untuk n genap adalah n, dimana ai dapat digambarkan sebagai lintasan dengan dua titik yang berjarak

n . 2

Sehingga eksentrik digraf dari graf sikel dengan n genap ED(Cn) adalah gabungan n

digraf lintasan dengan dua titik, yang dinotasikan dengan

2

P 2 , dimana setiap arcnya adalah 

i =1

simetrik. Contoh eksentrik digraf pada graf Cn dengan n genap diberikan pada Gambar 3.4.

v1

v2

v1

v2

v1

v2

v4

v3

v4

v3

v3

v4

C4

ED(C4) = 2

v1

v2

v1

P2

v2

v2 v1

v3

v6

v3

v3

v6 v5

v4

v5

v1

v4

v4

C6

ED(C6) = 3

v2

v1 v3

v8

v7

v4

v7

P2

v2

v5 C8

v3

v1

v4

v3 v4 v5

v6

v6

v5

v2 v8

v6

n 2

v5 ED(C8) = 4

P2

v6

v7

v8

23

Gambar 3.4 Graf C4, C6, C8 dan eksentrik digrafnya 3.3

Eksentrik Digraf pada Graf Lengkap Misalkan graf lengkap Kn mempunyai himpunan titik V(Kn) = {v1, v2, v3, ..., vn}

dan himpunan sisi E(Kn) = { vivj | i ≠ j, i< j dan i, j = 1, 2, …, n } dimana jumlah sisinya adalah

1

n(n – 1).

2 Dari definisi graf lengkap, maka dapat disimpulkan bahwa eksentrisitas

titik e(vi) pada

setiap graf lengkap Kn adalah sama pada setiap titiknya, yaitu 1. Sehingga titik eksentrik dari vi untuk setiap i = 1, 2, …, n adalah semua titik dalam Kn kecuali dirinya sendiri atau vi, dimana vi adalah komplemen dari vi. Jadi eksentrik digraf dari graf lengkap ED(Kn) adalah graf dengan himpunan titik

V(ED

(Kn)) = {v1, v2, v3, ..., vn} dan himpunan arc A(ED (Kn)) = { vivj | i ≠ j dan i, j = 1, 2, …, n } Dimana

vivj adalah arc yang terhubung dari titik vi ke titik vj dan dari titik vj ke

titik vi. Jadi

banyaknya arc pada ED(Kn) adalah n(n – 1). Sehingga eksentrik digraf dari graf lengkap ED (Kn) adalah digraf lengkap

Kn yang setiap

arcnya simetrik. Contoh eksentrik digraf dari graf lengkap Kn diberikan pada Gambar 3.5.

v1

v2

v1

v2

v4

v3

v4

v3

K4

ED(K4)

24

v1

v1

v5

v2

v4

v3 K5

v2

v5

v3

v4 ED(K5)

Gambar 3.5 Graf K4, K5 dan eksentrik digrafnya

B A B IV KESIMPULAN DAN SARAN 4.1 Kesimpulan

Berdasarkan pembahasan yang telah dilakukan, maka kesimpulan yang dapat diambil mengenai eksentrik digraf pada graf lintasan, graf sikel dan graf lengkap adalah sebagai berikut: 1. a.

Eksentrik digraf pada graf lintasan ED(Pn) dibedakan menjadi dua, yaitu: Untuk jumlah titik n ganjil, eksentrik digraf pada graf lintasan ED(Pn)

tripartit T1,

,

dengan himpunan titik V1 = {v n-1 2

…, vn}. n-1

b.

}, V2 = {v1, v2, …, v

} dan V3 = {v

,v

,

n+1 2

n+5

2 2 2 eksentrik Untuk jumlah titik n genap, digraf pada graf lintasan ED(Pn) adalah digraf bipartit B

dengan himpunan titik V1 = {v1, v2, …, v }dan V2 = {v

,

2. a.

n+3

n-1 2

adalah digraf

n

n

2

2

v

, …, vn}. n

n+2 2

2

Eksentrik digraf pada graf sikel ED(Cn) dibedakan menjadi dua, yaitu:

n+4 2 Untuk

jumlah titik n ganjil, eksentrik digraf pada graf sikel ED(Cn) adalah digraf sikel

yang setiap arcnya adalah arc simetrik yang berjarak b.

,

Cn

n −1 . 2

Untuk jumlah titik n genap, eksentrik digraf pada graf sikel ED(Cn) adalah gabungan

n digraf lintasan dengan 2 titik 2 3.

n

2

P 2 , dimana arcnya adalah arc simetrik. 

i =1

Eksentrik digraf dari graf lengkap ED(Kn) adalah digraf lengkap

Kn yang setiap

arcnya adalah simetrik.

4.2 Saran

Penelitian mengenai eksentrik digraf masih dapat dikembangkan pada

graf-

graf yang lain, misalnya pada graf berbobot, baik yang berarah maupun yang tidak berarah.

27