BAB. 11 Teori Pendukung Dalam Penelitian
Sebelum dilakukan aplikasi Graph dalam bidang lain, khususnya dalam teori transportasi maka dirasa perlu menjelaskan tentang Graph dan operasi graph serta yang terkait dengan aktifiti arus maksiraum. II.2 Pengertian Graph. Untuk memberikan gambaran yang lebih jelas tentang graph maka berikut ini akan diberikan beberapa definisi tentang graph. Definisi. 1. Suatu Graph G, Lengkap ditulis G(V,E) adalah koleksi atau pasangan dua himpunan : 1. Himpunan V yang elemen dinamakan simpul atau titik, atau vertek. 2. Himpunan E yang merupakan pasangan terurut dari sim.pul, disebut ruas atau edge atau garis. Definisi. 2. Banyak simpul ( anggota V ) disebut order graph G, sedangkan banyak ruas ( anggota E ) atau edge dinamakan ukuran graph G. Definisi. 3. Simpul u dan v disebut berdampingan bila terdapat ruas (' u,v ) Definisi. 4. Dua ruas ri=0/,\)
rj dan dan
ri
r2={n,v)
yang mempunyai kedua simpul yang ujung sama , yakni disebut ruas berganda atau sejajar.
Definisi. 5.
4
Sebuah ruas r\ yang kedua simpul ujung sama yakni
= (u,u)
disebut gelung .
Definisi. 6. Suatu graph G disebut graph hingga apabila G raempunyai sejumlah hingga simpul dan sejumlah hingga ruas. Definisi. 7. Graph G dinamakan graph berlabel jika ruas dan atau simpuJnya dikaitkan dengan suatu besaran tertentu. Secara khusus, jika setiap ruas e dari G dikaitkan dengan suatu bilangan nonnegatif d(e), maka d(e) dinamakan bobot atau panjang ruas e. Definisi. 8. Perjalanan atau walk pada suatu graph G adalah barisan simpul dan ruas berganti - ganti , v'],t?i,v2,e2, ..,
dimana
menghubungkan simpul
v,
dapat ditulis lebih singkat dengan hanya menuliskan barisan ruas ,
dan
v,+i Perjalanan
e\,e2.....,e„_\
Definisi. 9. Dari defmisi. 9.
v|
Disebut simpul awal dan
v„
dinamakan simpul akhir dari
perjalanan banyaknya ruas dalam bari^n disebut panjang perjalanan. Definisi. 10. Jalur atau Path adalah perjalanan yang semua simpul dalam barisan adalah berbeda. Definisi. 11. Jarak antara dua simpul u dan v dalam graph C ditulis d(u,v).
5
Definisi. 12 . ( Bertumpuan , bersisian dan Berderajat). . Bila sebuah vertek v, adalah ujung atau pangkal dari sisi (edge) ej maka Vi dan Cj disebut bertumpuan (berinsiden). Sedangkan dua venek dikatakan bersisian (beradjacent) jika vertekvertek tersebut adalah vertek ujung dari edge yang sama. Banyaknya sisi yang bertumpuan pada vertek v; dalam sebuah graph G disebut derajat (degree) dari vertek v, yang dapat ditulis dalam bentuk umum dengan G(vi) atau d(v,). Contoh 2.1:
G:
Gambar 2.2
Gambar
2.2 di atas merupakan gambar sebuah graph G dengan
V(G)={vi,V2,V3,V4,V5}
dan
E(G)=(ei,e2,e3,e4}
dan degree masing-masing venek
dalam graph tersebut secara berurutan (2,2,2,1,1} dimana p>(G)=5 dan q(G)=4. Selain bertumpuan, bersisian dan berderajat, dalam tuHsan ini juga diperlukan defmisi dari subgraph sebagai berikut.
Uctinisi. U. ( Subgraph ). • Sebuah subgraph adalah sebuah graph yang berada pada graph lain. Jika G = ( V , E ) adalah sebuah subgraph dari G=(V,E), maka V c Vdan E e,E. Dengan kata lain, sebuah subgraph adalah sebuah graph yang di bentuk oleh subhimpunan vertek dan subhimpunan besar.
edge dari sebuah graph yang lebih
Definisi. 14. ( Kompfemen Graph ). : Diberikan sebuah graph G=(V,E), komplemen dari graph G adalah sebuah graph G dengan V( G )=V(G) sehingga uv adalah sebuah edge dari G , jika dan hanya jika uv bukan sebuah edge dari G. Jika Vj adalah sebuah vertek yang mempunyai degree n dalam graph G yang berorder p, maka degree dari vertek Vj yang berada pada graph komplemen G banyaknya adalah p-n-1. Contoh 2.4 :
Gi
Gambar 2.5 Pada gambar 2.5 graph Gi adalah subgraph dari graph G dan graph G adaiah komplemen dari graph Gi dimana setiap edge yang berada pada graph G tidak berada pada graph G|. Graph G berorder 4,degree venek v-, yang berada pada graph Gi banyaknya adalah 1, sedangkan degree vertek V| yang berada pada graph komplemehnya ( G ) banyaknya adalah 2.
7
Dalam mempelajari teori graph, banyak dijumpai istilah graph. Salah satu dari istilah tersebut adalah graph lengkap. Definisi. 15. ( Graph Lengkap ). : Sebuah graph yang berorder p dimana setiap dua vertek yang berada pada graph tersebut beradjacent disebut graph lengkap. Graph lengkap sering dikatakan sebagai graph yang setiap pasang verteknya dihubungkan dengan sebuah edge. Contoh 2.5:
Gambar 2.6 merupakan gambar dari sebuah graph lengkap dengan order 4 dan size 6. 2.2. Poset Dari defmisi sebuah graph kita ketahui bahwa graph terdiri dari himpunan vertek dan edge. Definisi berikut ini adalah definisi dari himpunan venek daiam sebuah graph yang dikatakan sebagai poset, Oefinisi. 16. ( P o s e t : Suatu relasi terurut secara parsial yang mempunyai sifa:: retleksif, antisimetnk dan transitif Misalkan X himpunan vertek yang anggotanya-anggotanya
memenuh;
relasi pengurutan parsial < dengan notasi (X, <) di sebut poset.
8
l>cfinisi. 17. (lliai|)unan Bebas ). : Suatu himpunan vertek S yang berada pada graph G dikatakan bebas jika dua vertek dalam S tidak beradjacent dalam G.
Suatu himpunan bebas S dari vertek yang berada dalam sebuah graph G dikatakan bebas maksimal jika S tidak membangun subhimpunan dari himpunan bebas lain dari vertek dalam G. Kardinal maksimum dari sebuah himpunan bebas dari vertek dalam G disebut bilangan kebebasan dari G dan dinotasikan dengan P(G). Setiap himpunan bebas dari vertek dengan kardinal P(G) merupakan himpunan bebas maksimal, tetapi tidak beriaku sebaliknya.
Defenisi. 18. ( Clique ). : Himpunan vertek pada subgraph lengkap maksimal. Order maksimum dari sebuah clique disebut bilangan omega co(G).Sebuah himpunan S dari vertek dalam graph G merupakan sebuah himpunan dominan jika setiap vertek yang tidak berada dalam S beradjacent dengan sebuah vertek dalam S. Himpunan dominan S dikatakan himpunan dominan minimal jika tidak ada subhimpunan dan S yang juga himpunan dominan. Bilangan dominan a(G) dari G adalah kardinal minimum dari himpunan dominan dalam G.
i>ctinrsr. 19. ( Order dan likuran ). :Order dari sualu graph G adalah ban\aknya verteks didalam G dan ditulis dengan. i V(G) 1. likuran dari suatu graph CI adalah banyak edge didalam G dan ditulis dengan
I B(G) i . Uniuk
memudahkan
penulisan, sering juga order dan ukuran dari suatu graph G masing masing ditulis dengan p(G) dan q(G). dengan menggunakan notasi ini, sualu graph berorder p dan berukuran q dan dituhs sebagai graph (p,q).
I'corema 2.1 Misalkan G adalah suatu graph berorder p dan Ivrderajat q dengan V(G)=(V,,V2, ....,Vp}.
Maka : ^deg.v, = Iq
Bukti: Karena derajat suatu graph adalah banyaknya edge didalam graph G dan order dari suatu verteks adalah banyaknya edge yang incident dengan \ erteks tersebut maka dalam menjumlahkan derajat verteks-vcrteks didalam graph G I' setiap edge telah dihitung dua kali. Oleh karena itu ^deg.v, = 2(/
^
Akibat 2.2 Setiap graph memuat verteks ganjil dalam jumlah genap . Bukti: Misalkan G adalah sebarang graph berukuran q . selajutnya misalkan: Vi= himpunan verteks genap dari G. V2= himpunan verteks ganjil dari ( i . Oleh karena itu: ^ deg.v = ^ deg.v + ^ deg.v = 2q dari sini diperoleh:
10
deg.v
karena 2q dan
=2q-2;deg.v
(2.1)
^ d e g . v masing masing adalah bilangan genap maka
(2q-
^deg.v)=
^ d e g . v adalah bilangan genap. Oleh karena itu untuk setiap
veC,
veCj
VG V2 diperoleh deg.v - bilangan genap. Ini membuktikan ban\aknya \eneks ganjil adalah genap yaitu I V 2 ! = genap
^
Defmisi. 20. ( Graph Berarah ). : Suatu graph berarah D terdiri dari himpunan takkosong berhingga V(D) dan himpunan pasangan verteks-verteks E(D). Elemen -elemen dari E(D) disebut arc. Pengertian graph dan graph berarah adalah hampir sama , perbedaannya adalah dalam graph edge tidak berarah sedang dalam graph berarah arc-n\a berarah. Dalam graph berarah (u,v) dan (v,u) adalah dua arc yang berl^da . Definisi. 2 i . ( Order Berarah dan t k u r a n Berarah ). : Misalkan 1) adalah suatu graph berarah . Banyak verteks didalam D disebut order dari graph berarah D. Banyaknya arc didalam D disebut ukuran dari graph berarah D. Jika 1 u.v) adalah suatu arc dari D maka u disebut adjacent ke v dan v disebut adjacent dari u. Selanjutnya arc (u,v) disebut incident dari u dan incident ke v. Derajat luar dari verteks v didalam D dinyatakan dengan od (v) dan didelmisikan sebagai banyak verteks adjacent dari v. Sedangkan banyaknya verlcks adiaccnt kc s discbui derajat masuk dan dinyatakan dengan id(v). Derajat suatu verteks \ dalam graph berarah D dinyatakan dengan deg(v) dan didefinisikan sebagai: deg(v) = od(v) + id(v). 11
Teorenis. 2.2, Misalkan D adalah suatu graph berarah berorder p dan berukuran q dengan V ( D ) = { v i , V 2 , ....,Vp) maka
X/V/(v,) = X«^(v,) = q
Bukti: Bila derajat luar dari verteks - verteks dari D dijumlahkan maka setiap arc dari D dihitung sekali. Demikian juga bila derajat masuk dari verteks- verteks dari /'
D dijumlahkan maka setiap arc dari D dihitung sekali oleh karena itu : ^ / c / ( v j
^o./(v,) = q 1=1
•
Contoh 2.4 Pandang graph berarah D berikut ini • u
Gambar 2 4 Graph berarah. V(l))
fu, v, w, x }
i:(D) = ((u, vv), (v, u), (v, w), (w, x ) , (X, w)}, Derajat setiap verteks dari D adalah sebagai berikut: 12
Tabel: 2.1 verteks
od
id
deg
u
1
1
2
v
2
0
2
w
1
X
1
4 1
2
Suatu walk di dalam graph berarah adalah suatu barisan veneks dan arc berbentuk: W: vo, ei, vi, ...,Vn.,,en, Vn, ( n > 0 ) . Dimana: ei = (Vi-i, V,),
(i = 1, 2, .... n).
Disini w adalah walk Vo-v,, yang mempunyai panjang n.
13
n.3. Graph Batas Atas yang Berhubungan Dengan Operasi pada Graph
Berikut ini diberikan definisi operasi-operasi dalam graph yang dapat dikatakan sebagai graph batas atas.
Defmisi. 22. ( Graph Batas A t a s ) . : Untuk sebuah poset P(X <), graph Batas Atas (BA-Graph) dari P adalah sebuah graph U={X,Eu} dengan uveEu jika dan hanya jika Ur^v dan terdapat meX sedemikian hingga u,v < m .
Dctmisi. 23. ( Penjumiahan ). : Jumlah G + H dari dua graph G dan H adalah graph dengan bJmpunan V(G-!-H) = V(G) w V(H) dan himpunan edge E(G-^H) = E(G) u E(H) u {uv ; ue V(G), v€ V(H)}.
Untuk poset-poset P dan Q, gabungan dari P dan Q adalah poset P9Q pada gabungan PuQ sedemikian hingga x
\3
kebeberapa clique maksimal. Dengan demikian G + H bukan merupakan sebuah graph Batas Atas. H
Defmisi. 24. ( Perkatian Kartesius ). : Perkaiian kartesius G x H dari dua graph G dan H adalah graph himpunan vertek V(GxH)=V(G)xV(H), dimana perkaiian yang kedua adalah himpunan kanesius dan edge-edge didefinisikan sebagai ; (ui, U j ) adalah adjacent ( V ) , V2) jika kedua-duanya ui = vi dan U2 adalah adjacent V2 di dalam H, atau U| adjacent vj dalam G dan vi = v i . Jika E(G) = ^, maka G.xH adalah gabungan dari I V(G) I tiruan dan H.
Contoh 3.2:
Gambar 3.2 Perkaiian dua buah graph
Pada gambar 3.2
diatas m.erupakan GxH dengan jumlah venek 6 dan
jumlah edge 9.
14
Gambar 3.1 Penjumiahan dua buah graph
Pada gambar 3.1 diatas merupakan G+H dengan jumlah vertek 5 dan jumlah edge 10.
Proposisr. f
. y^^.^,, g^^p^ Batas Atas G dan H, G+H adalah sebuah graph
Batas Atas jika dan hanya jika G atau H adalah sebuah graph lengkap.
Bukti : <=z Jika G adalah grap lengkap, G+H adalah graph Batas Atas dari PQ'^PH, dimana PG dan PH adalah poset-poset yang batas atasnya G dan H. • =? Asumsikan bahwa salah satu G dan H bukan merupakan graph lengkap. Misai G = [G], G;:, ... Gn,} adalah sebuah selimui edge clique dari G dan / / = IH;, Hi:,
• Hp,; adalah sebuah selimut edge clique dan H, dimana masing-masing
G, dan masing-masing H, clique maksimal. Maka seuap G, u H, adalah sebiiih clique maksimal dalam G t- H.tapi semua vertek daiam Gi u H, berganturj
15
Proposisi. 2.
I : Untuk graph terhubung G dan H, G x H adalah tidak sebuah
graph Batas Atas, dimana I V(G) i > 2 dan i V(H) I > 2. Bukti : Misal (u,x) adalah sebuah vertek GxH. Maka, G adalah terhubung dari I V(G) > 2, dimana terdapat sebuah edge uv di dalam G, dan terdapat juga sebuah edge x y dalam H. maka (u,xXu,yXu,x)(v,x)eE (G x H) dan (u,y)(v,x)gE (G x H) dan (u,y) tidak sebuah vertek simplisial, maka G x H tidak graph Batas Atas.
Definisi. 25. (Komposisi). ; Komposisi G[H] dari dua graph G dan H adaiah graph dengan him.punan vertek V(G[H]) = V(G) x V(H) dan edge-edge didefenisikan sebagai berikut: (ui, u?) adalah adjacent ( v i , v o ) jika ui adjacent ke V] dalam G, atau Uj = v j dan ui adalah adjacent ke V2 di dalam H. Contoh 3.3 :
Gambar 3.3 Komposisi dua buah graph
16
I'roposisi. 3 V{G}
; Untuk graph Batas Atas graph terhubungn G dan H dimana
> 2dan |V(H)J > 2 , G [ H ] adalah sebuah graph Batas Atas jika dan hanya
jika H adalah sebuah graph lengkap. Bukti: => Misal (u,x) adalah sebuah vertek G [ H ] , maka G adalah terhubung dan V(G)J > 2 , maka terdapat sebuah vertek v di dalam G beradjacent u. Jika H adalah sebuah graph tidak lengkap, maka terdapat beradjacent
vertek yang tidak
y,z di dalam H. Maka (u,xXv,y), (u,xXv,z)eE(G[H]) dan
(v,yXv,z)eE(G[Ii]). Karena NG(H](U,X) adalah tidak clique dan (u,x) adalah tidak sebuah vertek simplisial. Maka G[H] adalah tidak sebuah graph Batas Atas. c= Asumsikan bahwa H adalah sebuah graph lengkap. Mis G={G\, adalah selimut edge clique dari G, maka GKJH = {Gi x V(H), Gi
G?,...., Gm) x
(V(H), ...,
Gm X V(H)} adalah selimut edge clique dari G[H] memenuhi Teorema 3.1.1. Maka GfHj adalah sebuah graph Batas Atas.
Ucflnisi. 26. ( Corona ). : Corona G"H dari dua graph G dan H didetmisikan sebagai graph yang dihasilkan dengan mengambil tiruan dan G dan
iV(Gjj
ditirukan ke H , dan gabungan vertek ke-i dari G ke beberapa vertek dalam tiruan ke-i dan H, jika E ( G ) = 0 , maka G"^H adalah gabungan dari JV(G) dengan tiruan dan H - K i .
17
Contoh 3.4 :
Gambar 3.4 Corona dua buah graph Pada gambar 3.4 Corona G°H dengan jumlah vertek 8 dan jumlah edge 13.
Proposisi. 4.
. Qj.2pj, Batas atas G dan H , G^H adalah sebuah graph Batas
Atas jika dan hanya jika E(G)=0.
Bukti :
wJika E(G)=0, maka G*^H adalah gabungan dari V(G)^ yang ditirukan oleh H+Ki dan sebuah graph Batas Atas. <= Jika E(G) ^ 0 , maka terdapat sebuah clique maksimal dari G^^H yang 'censi tiruan dan G dan tidak memiliki vertek simplisial. Dengan demikian G "H bukan merupakan graph Batas Atas.
18
Jika graph G dan H adalah (pi,qi) dan (pa.q?) maka untuk setiap operasi graph diatas dapat diperoleh jumlah vertek dan jumlah edge dalam graph hasiL seperti ditunjukkan dalam tabel dibawah ini.
Tabel Operasi Biner pada Graph
No.
Operasi
Jumlah Vertek
Jumlah Edge
1.
Penjumiahan G + H
P!
2.
Perkaiian G x H
Pi P2
Piq2-^P2qi
3.
Komposisi G[H]
PI P2
Piq2-^-p2^qi
4.
Corona G'^H
Pi ( I + P I )
qi + Pi q: + PiP:
P2
qi + q2 + piP2
;
:
19
