BAB II
LANDASAN TEORI
2.1 Konsep Dasar Teori Graph
2.1.1 Graph Tak Berarah dan Digraph
Suatu Graph Tak Berarah (Undirected Graph) merupakan kumpulan dari titik yang disebut verteks dan segmen garis yang menghubungkan dua verteks yang disebut edge. Secara matematis, sebuah graph G didefinisikan sebagai pasangan himpunan (V , E ) , dimana
V
= himpunan tidak kosong dari verteks – verteks (simpul atau titik) = {v1 , v 2 ,..., v n }
dan E
= himpunan tak terurut dari edge (sisi) yang menghubungkan sepasang verteks = {e1 , e2 ,..., en }
Atau dapat dinotasikan dengan G = (V , E ) [1][2][3]. Definisi di atas menyatakan bahwa V (G ) ≠ Ø dimana V tidak boleh kosong, sedangkan E mungkin kosong sehingga sebuah graph dimungkinkan tidak mempunyai edge satu buah pun tetapi harus memiliki verteks minimal satu.
7
Sebuah Graph Berarah, atau Digraph / Directed Graph G terdiri dari: (i)
Sebuah himpunan V = V (G ) yang elemen – elemennya disebut node (verteks).
(ii)
Sebuah himpunan E = E (G ) dari pasangan – pasangan verteks terurut yang disebut busur atau edge berarah (arc) [2][5].
G (V , E ) dituliskan bilamana ingin menegaskan dua bagian dari G .
Beberapa pengertian dalam Digraph adalah sebagai berikut: (a)
Derajat ke luar (out degree) suatu verteks adalah banyaknya edge yang mulai atau ke luar dari verteks tersebut.
(b)
Derajat ke dalam (in degree) suatu verteks adalah banyaknya edge yang berakhir atau masuk ke verteks tersebut.
(c)
Verteks berderajat ke dalam = 0 disebut sumber (source), sedangkan verteks berderajat ke luar = 0 disebut muara (sink)
(d)
Pengertian jalan (walk), jejak (trail), lintasan (trail), dan cycle (sirkuit) berlaku pula pada Digraph, dimana harus sesuai dengan arah edge.
2.1.2 Defenisi dan Notasi
Sebuah graph G dapat digambarkan dengan menggunakan noktah atau titik sebagai verteks dan edge digambarkan dengan suatu garis (lurus atau melengkung) yang menghubungkan dua verteks yang berelasi. Letak verteks dan jarak antara dua verteks serta bentuk garis penghubung kedua verteks tersebut dapat digambarkan secara bebas.
Sebuah multigraph G = G (V , E ) terdiri dari suatu himpunan V (verteks) dan suatu himpunan E (edge), selain itu E mengandung multiedge, yaitu beberapa edge yang menghubungkan verteks – verteks ujung yang sama, dan E mungkin mengandung satu atau lebih loop, yaitu edge yang verteks – verteks ujungnya adalah verteks yang sama. Graph – graph (multigraph) G = G (V , E ) digambarkan dengan setiap verteks v dalam V yang diwakili oleh sebuah noktah dalam setiap edge (sisi) e = {u , v} yang diwakili oleh suatu kurva atau garis yang menghubungkan verteks -
verteks ujung u dan v . Suatu graph G yang tidak mengandung loop dan parallel
8
edge disebut Graph Sederhana. Gambar 2.1 adalah sebuah contoh graph sederhana tak berarah dengan himpunan verteks V (G ) = {v1 , v2 , v3 , v4 , v5 } , himpunan edge E (G ) = {e1 , e2 , e3 , e4 } . Gambar 2.2 merupakan sebuah multigraph dimana edge e3 adalah loop dan edge e1 , e2 adalah edge rangkap.
G:
v1
v3
e1
e3
v5 e4
v2
e2
v4
Gambar 2.1 Graph Sederhana Tak Berarah
G:
e1 e3 v1
e2
v2
e4 v3 Gambar 2.2 Multigraph
Pada suatu graph G = G (V , E ) , V (G ) merupakan himpunan verteks dari G dan E (G ) merupakan himpunan edge dari G dan sering disingkat dengan V dan E . Jumlah verteks dari G disebut order dari G . Order n dari G dapat dituliskan dengan n = V . Graph yang ordernya berhingga disebut graph hingga. Sebagai contoh, Gambar 2.3 adalah graph yang mempunyai order sebanyak 6.
9
G:
v2 v1
v4
v3 v5 v6 Gambar 2.3 Order pada Graph
Graph Berarah (Digraph) dikatakan berhingga bila himpunan V dari verteks – verteksnya dan himpunan E dari arc – nya (edge berarahnya) berhingga. Arc yang menghubungkan verteks u ke verteks v dan verteks v ke verteks u dinamakan arc simetrik, yang dinotasikan dengan e = uv . Setiap verteks v dalam V diwakili oleh
sebuah noktah (bulatan kecil) dan setiap arc e = [u , v] diwakili oleh sebuah panah, yaitu sebuah edge berarah dari verteks awalnya u ke verteks akhirnya v .
Sebagai
contoh,
Gambar
2.4
mewakili
Digraph
G (V , E )
dimana
V = {v1 , v 2 , v3 , v 4 } dan E terdiri dari delapan arc (edge berarah) e1 = [v1 , v4 ] , e2 = [v 2 , v1 ] , e3 = [v 2 , v1 ] , e4 = [v 4 , v2 ] , e5 = [v 2 , v3 ] , e6 = [v 4 , v3 ] , e7 = [v 2 , v2 ] , e8 = [v3 , v 4 ] .
D:
v1
e2
e1
e3
e7
v2
e4
v4
e6
e5
Gambar 2.4 Digraph
v3
e8
10
Sebuah edge e dalam sebuah graph (berarah atau tak berarah) yang menghubungkan verteks v1 dan v2 dikatakan insiden pada v1 dan v2 , serta v1 dan v2 dikatakan insiden pada e . Jika G merupakan suatu graph (tak terarah atau terarah) dengan verteks V dan edge E , ditulis G = (V , E ) . Jika dua verteks v1 dan v2 dihubungkan oleh suatu edge e , maka verteks v1 dan v2 dikatakan adjacent (bertetangga) dan edge e insiden dengan kedua verteks yang dihubungkan.
G:
e1
v1
v2
e5
e4
v4
e3
e2
v3
Gambar 2.5 Graph untuk Mengilustrasikan Adjacent dan Insiden
Pada Gambar 2.5, verteks yang adjacent adalah v1 dan v2 , v2 dan v3 , v3 dan v4 , v4 dan v1 , v1 dan v3 . Sedangkan edge e1 insiden dengan v1 dan v2 , e 2 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 verteks v adalah jumlah edge yang insiden dengan
verteks
v ,
dinotasikan
dengan
deg(v) .
Misalkan
pada
Gambar
2.5,
deg(v1 ) = deg(v3 ) = 3 dan deg(v2 ) = deg(v4 ) = 2. Banyaknya edge yang insiden pada verteks vi dalam graph G dimana loop dihitung dua kali disebut degree dari verteks vi . Suatu verteks vi berderajat satu disebut end vertex, sedangkan suatu verteks berderajat nol, dinamakan isolated vertex (verteks terasing) . Pada Gambar 2.6 (a), v2 dan v3 adalah end verteks sedangkan v4 adalah isolated vertex. Jika setiap verteks dalam suatu graph G mempunyai derajat yang sama, maka graph tersebut dinamakan graph regular.
11
G:
G:
v1
v4
v1
v4
v3
v3
v2
v2
(a) (b) Gambar 2.6 (a) End Vertex dan Isolated Vertex (b) Null Graph
Suatu graph G tanpa edge disebut null graph. Dengan kata lain, null graph adalah suatu graph dengan semua verteksnya berderajat nol. Akibatnya, setiap verteks pada null graph adalah isolated vertex. Gambar 2.6 (b) merupakan sebuah null graph dengan empat verteks.
Suatu graph sederhana dimana setiap dua verteks yang berlainan dihubungkan dengan sebuah edge dinamakan Graph Lengkap (complete graph). Graph Lengkap dengan m verteks dinotasikan dengan K m . Gambar 2.7 berikut merupakan sebuah Graph Lengkap dengan empat verteks.
v1
v2
v4
v3
Gambar 2.7 Graph Lengkap K 4
Jumlah edge pada Graph Lengkap K m dengan m verteks adalah E(K m ) =
Sehingga E(K m ) =
pada
Gambar
2.7,
1 m(m − 1) 2
jumlah
1 1 m(m − 1) = (4)(4 − 1) = 6 edge. 2 2
edge
Graph
Lengkap
K4
adalah
12
Sebuah jalan (walk) W pada graph G dengan panjang n dari verteks a ke b adalah barisan verteks a = v0 , e1 , v1 , e2 , v 2 , e3 , v3 ,..., v n−1 , en , v n = b , dimana n ≥ 0 yang terdiri dari verteks dan edge di G yang diawali dan diakhiri dengan verteks sedemikian hingga (v1 , vi +1 ) adalah edge di G untuk setiap i = 0,1,2,..., n − 1 .
Jalan ini menghubungkan verteks v0 dan v n dan dapat juga dinotasikan sebagai v0 − v1 − ... − vn . Jalan dikatakan tertutup jika v0 = v n dan terbuka jika v0 ≠ v n . Suatu jalan yang barisan verteksnya tidak ada pengulangan dinamakan lintasan (path), tetapi jika yang berbeda adalah edge-nya, maka jalan tersebut disebut jejak (trail). Lintasan adalah jejak akan tetapi tidak semua jejak adalah lintasan. Cycle
(sirkuit) didefinisikan sebagai jalan tertutup dengan barisan verteks yang berbeda. Dengan kata lain, cycle adalah suatu lintasan tertutup.
Gambar 2.8 menjelaskan bahwa jalan v4 − v5 − v 2 − v1 − v5 − v3 adalah jejak tetapi
bukan
lintasan,
sedangkan
v1 − v 4 − v5 − v 2 − v3
adalah
lintasan
dan
v1 − v5 − v3 − v 2 − v1 adalah cycle.
G:
e1
v1 e2 e4
v2 e3
e5
v5 e6
e7
v4 v3 Gambar 2.8 Walk pada Graph
2.2 Graph Terhubung dan Komplemen Graph
Graph H dikatakan subgraph dari graph G jika setiap verteks di H termuat di dalam G dan setiap edge dari H mempunyai verteks ujung yang sama dengan edge dari G .
13
Pada Gambar 2.9, G1 adalah subgraph dari G dan G2 bukan merupakan subgraph dari G karena terdapat edge v 2 v3 di G2 yang bukan merupakan elemen dari E (G ) .
G:
v1
v4
G1 :
v2
v3
v1
v4
G2 :
v2
v1
v4
v3
v2
v3
Gambar 2.9 Graph dan Subgraph
Suatu graph G dikatakan graph terhubung (connected graph) jika untuk setiap pasangan verteks di dalam G terdapat paling sedikit satu lintasan. Sebaliknya jika dalam graph G terdapat pasangan verteks yang tidak mempunyai lintasan, maka graph yang demikian disebut graph tak terhubung.
Dalam suatu graph tak terhubung memungkinkan terdapat dua atau lebih graph terhubung. Setiap graph terhubung dari graph tak terhubung disebut komponen. Dapat juga dikatakan bahwa komponen dari graph G adalah subgraph terhubung maksimal dari G . Jadi, setiap graph terhubung hanya mempunyai satu komponen sedangkan untuk graph tak terhubung memiliki setidaknya dua komponen. Untuk lebih jelas, dapat dilihat pada Gambar 2.10.
14
v2 (a)
v1
v1
v3
Graph Terhubung 1 komponen
v4
(b)
Graph Tak Terhubung 2 komponen v5 v2
v3
Gambar 2.10 (a) Graph Terhubung (b) Graph Tak Terhubung
Misalkan ada dua graph G1 dan G2 , dimana himpunan verteks V (G1 ) dan himpunan verteks V (G2 ) saling asing begitu juga himpunan edge E (G1 ) dan himpunan edge E (G2 ) . Gabungan dari G1 dan G2 dinotasikan G1 ∪ G2
adalah
graph dengan himpunan verteks V (G1 ∪ G2 ) = V (G1 ) ∪ V (G2 ) dan himpunan edge E (G1 ∪ G2 ) = E (G1 ) ∪ E (G2 ) . Sebagai contoh, perhatikan gabungan graph pada Gambar 2.11 dimana V (G1 ) = {v1 , v 2 , v3 , v 4 , v5 } dan V (G2 ) = {v1 , v 2 , v3 , v 4 } sehingga V (G1 ∪ G2 ) = {v1 , v 2 , v3 , v 4 , v5 } ∪ {v1 , v 2 , v3 , v 4 } = {v1 , v 2 , v3 , v 4 , v5 } .
v5
v5
v1
v4
v2
v3 G1
v1
v4
v2
v1
v3 G2
v4
v2
v3 G1 ∪ G2
Gambar 2.11 Gabungan Graph
Komplemen pada suatu graph sederhana G dinotasikan G , adalah graph
dengan himpunan verteks yang sama dengan himpunan verteks di G . Dengan kata lain V (G ) = V (G ) dan verteks u dan v di G adalah adjacent jika dan hanya jika
15
verteks u dan v di G tidak adjacent. Banyaknya edge dari graph komplemen suatu graph G adalah E (G ) = E ( K m ) − E (G ) dimana K m adalah graph lengkap dengan m verteks dan E ( K m ) =
1 m(m − 1) . 2
Contoh graph dan komplemennya dapat dilihat pada Gambar 2.12.
v2
v2 v1
v1
v3
v5
v4
v3
v5
G
v4 G
Gambar 2.12 Graph dan Komplemennya
Definisi komplemen suatu graph G memberikan beberapa akibat, yaitu: 1. Jika G suatu graph lengkap, maka G adalah null graph 2. Untuk setiap graph G , berlaku G ∪ G adalah graph lengkap
2.3 Pohon (Tree)
Acyclic Graph adalah suatu graph G tanpa cycle (sirkuit). Pohon adalah suatu acyclic
graph yang terhubung. Dengan demikian, suatu pohon tidak memuat edge yang parallel dan loop karena itu pohon juga merupakan graph sederhana. Apabila suatu graph terdiri dari beberapa komponen berupa pohon, maka graph yang demikian disebut forest (hutan). Sebagai contoh, lihat Gambar 2.13.
16
(a)
(b)
Gambar 2.13 Pohon dan Forest
Keterangan: (a)
Pohon dengan 9 verteks
(b) Forest dengan 4 komponen
Teorema 2.3.1
Terdapat satu dan hanya satu lintasan antara pasangan verteks dalam sebuah pohon T .
Bukti :
Akan dibuktikan bahwa lintasannya tunggal. Karena T pohon, maka T adalah graph terhubung, sehingga paling sedikit terdapat satu lintasan untuk setiap pasangan verteks di dalam T . Andaikan di antara dua verteks a dan b pada T terdapat dua atau lebih lintasan yang berbeda, maka gabungan dua lintasan yang berbeda akan membentuk cycle. Pernyataan ini kontradiksi dengan teorema 2.3.1. Karena itu haruslah lintasan yang menghubungkan setiap pasangan verteks pada T adalah tunggal.
ф
Teorema 2.3.2
Jika di dalam suatu graph G terdapat lintasan yang tunggal di antara setiap dua verteks berbeda, maka G adalah pohon.
17
Bukti :
Eksistensi dari sebuah lintasan di antara pasangan verteks menjamin G adalah graph terhubung. Selanjutnya suatu graph akan memuat cycle jika di dalam graph tersebut paling sedikit terdapat sepasang verteks (a, b) , sedemikian hingga ada dua atau lebih lintasan yang berbeda antara a dan b . Karena G hanya mempunyai lintasan yang tunggal antara setiap pasangan verteks, maka G tidak mempunyai cycle. Jadi G adalah graph terhubung tanpa cycle atau dapat dikatakan juga bahwa G adalah pohon.
ф
Teorema 2.3.3
Suatu pohon dengan n verteks mempunyai n − 1 edge. Bukti :
Secara induksi, untuk n = 1,2,3 dan 4 , teorema ini benar (lihat Gambar 2.13 (b)). Selanjutnya diasumsikan bahwa teorema ini berlaku untuk pohon dengan jumlah verteks lebih kecil dari n . Andaikan T adalah pohon dengan n verteks. Ambil edge ek pada T dengan verteksverteks ujung vi dan v j . Teorema 2.3.1 menjamin tidak ada lintasan antara vi dan v j kecuali ek . Karena itu penghapusan ek mengakibatkan T menjadi graph tak
terhubung, seperti yang ditunjukkan oleh Gambar 2.14 berikut. Selanjutnya T − ek menagkibatkan T menjadi dua komponen yang mana setiap komponennya adalah pohon, katakanlah T1 dan T2 . T1 dan T2 masing – masing mempunyai verteks lebih kecil dari n . Dengan menggunakan asumsi di atas, maka T − ek terdiri dari n verteks dan n − 2 edge. Jadi T mempunyai tepat n − 1 edge.
ф
18
vj
T2
ek T1 vi Gambar 2.14 Pohon T dengan n Verteks
Teorema 2.3.4
Suatu graph terhubung dengan n verteks dan n − 1 edge adalah sebuah Pohon T.
Bukti :
Andaikan T suatu graph terhubung dengan n verteks dan n − 1 edge, akan ditunjukkan bahwa T tidak memuat cycle. Andaikan T memuat cycle secara intuitive dapat dilihat bahwa untuk menghubungkan n verteks yang berbeda, minimum diperlukan n − 1 edge, jadi bila T memuat cycle satu buah saja, hal ini mengakibatkan T mempunyai isolated verteks atau T terdiri dari dua komponen; keduanya kontradiksi dengan T terhubung, maka harus ada T ф
yang tidak memuat cycle.
Sebagai contoh, ambil graph dengan empat verteks pada Gambar 2.15 yang menjelaskan keadaan di atas.
(a)
Tidak sesuai asumsi (edge = verteks)
19
(b)
Terdapat isolated vertex
(c)
Forest
(d)
Pohon
Gambar 2.15 Graph Dengan Empat Verteks
2.4 Graph Bipartit Lengkap
Sebuah graph G = (V , E ) terdiri dari dua bagian (dua pihak), jika himpunan verteks V dapat dibagi menjadi dua subhimpunan V1 dan V2 sehingga setiap edge dalam E
insiden (menempel) pada satu verteks di V1 dan satu verteks dalam V2 [3][10]. Graph ini disebut juga sebagai Graph Bipartit.
V1 v1
V2
v2 v4 v5 v3
Gambar 2.16 Graph Bipartit
20
Graph
dalam
Gambar
2.16
adalah
bipartit
karena
jika
misalkan
V1 = {v1 , v2 , v3 } dan V2 = {v 4 , v5 } , setiap edge terhubung pada satu verteks dalam V1 dan satu verteks dalam V2 . Definisi di atas tidak menyatakan bahwa andaikan v1 adalah sebuah verteks di V1 dan v2 sebuah verteks di V2 maka terdapat sebuah edge di antara v1 dan v2 . Sebagai contoh pada Gambar 2.16, masing – masing edge terhubung pada satu verteks di V1 = {v1 , v2 , v3 } dan satu verteks di V2 = {v 4 , v5 } akan tetapi tidak semua edge di antara verteks V1 dan V2 berada dalam graph, contohnya edge (v1 , v5 ) tidak ada.
Graph Bipartit Lengkap pada m dan n verteks dinotasikan dengan K m,n ,
adalah graph sederhana yang himpunan verteksnya dibagi menjadi himpunan V1 dengan m verteks dan V2 dengan n verteks di mana terdapat sebuah edge di antara setiap pasangan verteks v1 dan v2 dengan v1 berada di dalam V1 dan v2 berada di dalam V2 . Gambar 2.17 merupakan ilustrasi dari sebuah Graph Bipartit Lengkap K 2, 4 dengan m = 2 dan n = 4.
V2 V1 v1 v1
v2
v2
v3 v4
Gambar 2.17 Graph Bipartit Lengkap K 2, 4
21
2.5 Graph Bintang
Graph Bintang adalah Graph Bipartit Lengkap K1,n atau K n,1 . Graph Bintang
dinotasikan dengan S m dengan m = n + 1 , dimana 1 verteks berderajat n disebut verteks sentral dan n verteks berderajat 1 disebut verteks daun. Contoh Graph Bintang
S5
dapat
dilihat
pada
Gambar
2.18
dimana
n=4
sehingga
m = n +1 = 4 +1 = 5 .
v1
v2
v0
v3
v4
Gambar 2.18 Graph Bintang S 5
2.6 Graph Bintang Rangkap Dua
Sebuah pohon T dikatakan bintang rangkap dua bila terdiri dari dua Graph Bintang S n dan S m , di mana kedua verteks sentralnya saling adjacent, dinotasikan S n,m (selanjutnya akan ditulis Graph Bintang Rangkap Dua). Contoh Graph Bintang Rangkap Dua S 3,3 dapat dilihat pada Gambar 2.19 berikut.
22
S n , dengan n = 3
S m , dengan m = 3
Gambar 2.19 Graph Bintang Rangkap Dua
2.7 Lintasan Terpendek (Shortest Path)
Persoalan mencari lintasan terpendek di dalam graph merupakan salah satu persoalan optimasi. Graph yang digunakan dalam pencarian lintasan terpendek adalah graph berbobot (weighted graph), yaitu graph yang setiap edge-nya diberikan suatu nilai atau bobot. Bobot pada edge suatu graph dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pengangkatan, dan sebagainya. Asumsi yang digunakan di sini adalah semua bobot bernilai positif. Kata ”terpendek” berbeda – beda maknanya tergantung pada jenis persoalan yang akan diselesaikan. Namun, secara umum “terpendek” berarti meminimasi bobot pada suatu lintasan di dalam graph.
Ada beberapa macam persoalan lintasan terpendek, antara lain: (a)
Lintasan terpendek antara dua verteks tertentu.
(b)
Lintasan terpendek antara semua pasangan verteks.
(c)
Lintasan terpendek dari verteks tertentu ke semua verteks yang lain.
(d)
Lintasan terpendek antara dua verteks yang melalui beberapa verteks tertentu.
Pada dasarnya, jenis persoalan (a) mirip dengan persoalan (c), karena pencarian lintasan terpendek pada jenis persoalan (c) dapat dihentikan bila verteks tujuan yang dikehendaki sudah ditemukan lintasan terpendeknya.
23
2.8 Eksentrisitas
Eksentrisitas ec(v) pada verteks v dalam graph G adalah jarak terjauh (maksimal
lintasan terpendek) dari verteks v ke setiap verteks di G , dapat dituliskan
ec(v) = max { d (u , v) } u ∈ V (G )
Radius r (G ) dari G adalah eksentrisitas minimum pada setiap verteks di G ,
dan dapat dituliskan r (G ) = min{ec(v) v ∈ V } sedangkan diameter dari G dinotasikan dengan dia (G ) adalah eksentrisitas minimum pada setiap verteks di G , dapat dituliskan dia(G ) = max{ec(v) v ∈ V } . Verteks v disebut verteks sentral jika ec(v) = r (G ) . Sentral dari G dinotasikan dengan cen( G ) adalah subgraph pada G
yang terbentuk dari verteks sentral. Verteks v dikatakan verteks eksentrik dari u jika jarak dari v ke u sama dengan verteks eksentrik dari u , dapat dituliskan d (v, u ) = ec(u ) .
v1
v2
v3
v5
v4
v6
v7
v8 Gambar 2.20 Pohon Dengan Tujuh Verteks
Pada Gambar 2.20 dianggap setiap edge berbobot satu satuan, maka dapat ditentukan bahwa: ec(v1 ) = 5 dengan verteks eksentrik v7 ec(v 2 ) = 4 dengan verteks eksentrik v7 ec(v3 ) = 3 dengan verteks eksentrik v7 ec(v 4 ) = 3 dengan verteks eksentrik v1 dan v8 ec(v5 ) = 4 dengan verteks eksentrik v1 dan v8
24
ec(v6 ) = 4 dengan verteks eksentrik v1 dan v8 ec(v7 ) = 5 dengan verteks eksentrik v1 dan v8 ec(v8 ) = 5 dengan verteks eksentrik v7
Setelah verteks eksentrik dari setiap verteks v di graph G diperoleh, maka antara verteks v dengan verteks eksentriknya dihubungkan oleh sebuah arc. Graph yang dihasilkan disebut Eksentrik Digraph. Eksentrik Digraph ED(G ) didefinisikan sebagai graph yang mempunyai himpunan verteks yang sama dengan himpunan verteks di G atau V ( ED(G )) = V (G ) , dimana terdapat edge berarah (arc) yang menghubungkan verteks u ke v jika v adalah verteks eksentrik dari u . Untuk lebih jelasnya berikut diberikan sebuah contoh graph sembarang G (6,7) dan Eksentrik Digraph-nya pada Gambar 2.21 dan Gambar 2.23.
G:
v1
v2
v5
v3
v6
v4
Gambar 2.21 Graph Sembarang G (6,7)
Pada Gambar 2.21 dianggap bahwa setiap edge berbobot satu satuan, sehingga dapat ditentukan verteks eksentrik dari setiap verteks v pada graph sembarang G (6,7) yang dinyatakan dalam Tabel 2.1. Eksentrik Digraph dari graph sembarang G (6,7) diperoleh dengan menghubungkan sebuah arc pada setiap verteks v dengan verteks eksentriknya, dinyatakan pada Gambar 2.22.
25
Tabel 2.1 Eksentrisitas dan Verteks Eksentrik dari Graph Sembarang G (6,7)
Verteks
Eksentrisitas
Verteks Eksentrik
v1
ec(v1 ) = 3
v6
v2
ec(v 2 ) = 2
v3 , v 6
v3
ec(v3 ) = 3
v6
v4
ec(v 4 ) = 2
v1 , v6
v5
ec(v5 ) = 2
v1 , v3
v6
ec(v6 ) = 3
v1 , v3
v1
v2
G:
v5 v3
v6
v4
Gambar 2.22 Eksentrik Digraph Dari Graph Sembarang G (6,7)
Sementara itu: r (G ) = min{ec(v) v ∈ V } = 2 dia(G ) = max{ec(v) v ∈ V } = 3 cen( G ) = v2 v5 v4 Gambar 2.23 Sentral dari Graph Sembarang G (6,7)
Dengan demikian, Eksentrik Digraph dari Graph Sembarang G (6,7) (lihat Gambar 2.21) merupakan Graph Komplemen dari Graph Sembarang G (6,7) , atau
26
dapat dituliskan bahwa ED(G (6,7)) = G (6,7) (lihat Gambar 2.22) karena verteks vi dan v j untuk i, j = 1,2,...,6 dimana i ≠ j pada Graph Sembarang G (6,7) adjacent jika dan hanya jika verteks vi dan v j untuk i, j = 1,2,...,6 dimana i ≠ j pada Graph Komplemen G (6,7) tidak adjacent.
Contoh berikutnya, diberikan sebuah Graph Sembarang G (7,8) pada Gambar 2.24. G:
v1
v2
v6
v3
v7
v5
v4 Gambar 2.24 Graph Sembarang G (7,8)
Untuk mendapatkan verteks eksentrik dari Graph Sembarang G (7,8) pada Gambar 2.24, dilakukan pencarian verteks eksentrik dari Graph Sembarang G (7,8) dengan menggunakan Tabel 2.2 berikut.
27
Tabel 2.2 Eksentrisitas dan Verteks Eksentrik dari Graph Sembarang G (7,8)
Verteks Verteks Eksentrisitas
Eksentrik
v1
ec(v1 ) = 3
v7
v2
ec(v 2 ) = 3
v4
v3
ec(v3 ) = 3
v7
v4
ec(v 4 ) = 3
v 2 , v7
v5
ec(v5 ) = 2
v1 , v 2 , v7
v6
ec(v6 ) = 2
v1 , v3 , v 4
v7
ec(v7 ) = 3
v1 , v3 , v 4
ED(G (7,8) = G (7,8)
v1
v2 v6
v3
v7
v5
v4
Gambar 2.25 Eksentrik Digraph dari Graph Sembarang G (7,8)
28
Sementara itu, Cen(G ) = min{ec(v) v ∈ V }
=
v6
v5 Gambar 2.26 Sentral dari Graph Sembarang G (7,8)
Dengan demikian, Eksentrik Digraph dari Graph Sembarang G (7,8) (lihat Gambar 2.24) merupakan Graph Komplemen dari Graph Sembarang G (7,8) , atau dapat dituliskan bahwa ED(G (7,8)) = G (7,8) (lihat Gambar 2.25) karena verteks vi dan v j untuk i, j = 1,2,...,7 dimana i ≠ j pada Graph Sembarang G (7,8) (lihat Gambar 2.24) adjacent jika dan hanya jika verteks vi dan v j untuk i, j = 1,2,...,7 dimana i ≠ j pada Graph Komplemen G (7,8) tidak adjacent (lihat Gambar 2.25).
