Penerapan Teori Graf untuk Mencari Eksentrik Digraf dari Graf Star, Graf Double Star dan Graf Komplit Bipartit
Ivan Saputra – 13505091
Program Studi Teknik Informatika, Institut Teknologi Bandung
Jl. Ganesha 10, Bandung
E-mail : if115091@students.if.itb.ac.id
Abstrak
Makalah ini membahas tentang kajian teori baru yaitu eksentrik digraf dari graf star, graf double star dan
graf komplit bipartit dengan mengacu pada teori graf yang didapat di mata kuliah Matematika Diskrit.
Teori graf merupakan topik yang banyak mendapat perhatian, karena model-modelnya sangat berguna
untuk aplikasi yang luas, seperti masalah dalam jaringan komunikasi, transportasi, ilmu komputer, dan
lain sebagainya. Salah satu aplikasi dalam teori graf adalah menentukan kota terjauh (maksimal lintasan
terpendek) dari suatu kota ke kota lain. Jarak (distance) d(u,v) antara dua titik u dan v adalah panjang
lintasan terpendek dari titik u ke titik v di G. Jika tidak ada lintasan dari u ke v, maka d(u,v) = ∞.
Eksentrisitas titik v di graf G, dinotasikan ec(v) adalah jarak terjauh (maksimal lintasan terpendek) dari v
ke setiap titik di G. Titik v adalah titik eksentrik dari u jika jarak dari v ke u sama dengan eksentrisitas dari
u atau d(v, u) = ec(u). Eksentrik digraf pada graf ED(G) 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. Masalah yang dibahas dalam penelitian ini adalah menentukan eksentrik
digraf dari graf star, graf double star dan graf komplit bipartit. Hasil yang diperoleh dari penelitian ini
adalah sebagai berikut. Eksentrik digraf dari graf star ED(Sm) adalah graf komplit Km yang mempunyai
arah dan eksentrik digraf dari graf double star ED(Sn,m) adalah digraf bipartit D(Bn,m). Selanjutnya
eksentrik digraf dari graf komplit bipartit ED(Km,n) adalah digraf komplemen Km,n = D (Km,n ).
Kata kunci : graf star, graf double star, graf komplit bipartit, jarak, eksentrisitas,
titik eksentrik dan eksentrik digraf.
1. Pendahuluan
Teori graf saat ini menjadi topik yang banyak
mendapat perhatian, karena model-model yang
ada pada 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. Masalah ini ekuivalen dengan
menentukan eksentrisitas titik pada graf.
Misal G graf dengan himpunan titik V(G) dan
himpunan sisi E(G). Jarak d(u,v) antara dua titik
u dan v adalah panjang lintasan terpendek dari
titik u ke v. Jika tidak ada lintasan dari titik u ke
v, maka kita definisikan jarak d(u,v) = ∞.
Eksentrisitas ec(v) pada sebuah titik v dalam graf
G adalah jarak terjauh (maksimal lintasan
terpendek) dari titik v ke setiap titik di G, dapat
dituliskan ec(v) = max{d(v,u)|u ∈ V(G)}. Radius
r(G) dari G adalah eksentrisitas minimum pada
setiap titik di G, dapat dituliskan r(G) =
min{ec(v)|v∈V} sedangkan diameter dari G,
dinotasikan dia(G) adalah eksentrisitas
maksimum pada setiap titik di G, dapat
dituliskan dia (G) = maks{ec(v)|v∈V}. Titik v
disebut titik central jika ec(v) = r(G).
Eksentrik digraf diperkenalkan pertama kalinya
oleh Fred Buckley pada tahun 90-an.
Eksentrik digraf ED(G) pada graf G
didefinisikan sebagai graf yang mempunyai
himpunan titik yang sama dengan himpunan titik
di G atau V(ED(G))=V(G), dimana arc
menghubungkan titik u ke v jika v adalah titik
eksentrik dari u. Pada papernya [1] Buckley
memberikan kesimpulan bahwa hampir setiap
graf G, eksentrik digrafnya adalah ED(G) =
(G)∗ , dimana (G)∗ adalah graf komplemen dari
G yang setiap sisinya diganti dengan dua arc (sisi
berarah) yang simetrik.
Pada skripsi ini, kita tertarik untuk membahas
eksentrik digraf dari graf komplit bipartit, graf
star, dan graf double star.
2. Dasar Graf
Graf tak berarah G adalah pasangan himpunan
(V, E) dimana V adalah himpunan tak kosong
dari elemen yang disebut titik (vertex) dan E
adalah himpunan dari pasangan tak terurut (u, v)
(selanjutnya akan ditulis uv) dari titik u, v di V
yang disebut sisi (edge). Untuk selanjutnya graf
tak berarah G akan disebut graf G saja. Sebagai
contoh, gambar 2.1 (a) adalah graf dengan
himpunan titik V(G) = {u, v, x, y, z, w}dan
himpunan sisi E(G) = {vx, vy, yz, zu, zw}.
Sisi yang menghubungkan dua titik yang sama,
yakni e = uu disebut loop. Jika terdapat lebih dari
satu sisi yang menghubungkan dua titik, maka
sisi tersebut dinamakan sisi rangkap (multiple
edge). Pada gambar 2.1 (b), sisi e3 adalah loop
dan sisi e1, e2 adalah sisi rangkap. Graf yang
tidak mempunyai loop dan sisi rangkap disebut
graf sederhana.
Order n dari graf G adalah banyaknya titik di G,
yakni n = |V|. Graf yang ordernya hingga disebut
dengan graf hingga. Sebagai contoh, gambar 2.1
(a) adalah graf yang mempunyai order 6. Pada
skripsi ini, graf yang kita bahas adalah graf
sederhana dan graf hingga.
Gambar 2.1 Contoh Graf
Misal u dan v titik pada graf G. Titik v dikatakan
tetangga (adjacent) u jika ada sisi e yang
menghubungkan titik u dan v, yaitu e = uv.
Himpunan semua tetangga dari titik v
dinotasikan dengan N(v). Jika e = uv adalah sisi
pada graf G maka e dikatakan menempel
(incident) pada titik u dan v. Contohnya pada
gambar 2.2 , titik u adalah adjacent titik v dan x
tetapi titik u bukan adjacent titik w, titik u dan
sisi e1 adalah incident tetapi titik w dan sisi e1
bukan incident.
Gambar 2.2 Adjacent dan incident
Derajat (degree) dari titik v di G adalah jumlah
sisi yang berhubungan dengan v. Jika setiap titik
v pada graf G mempunyai derajat yang sama,
maka graf G disebut graf reguler. Sebuah graf G
dikatakan r-reguler atau reguler pada derajat r,
jika setiap titik pada G mempunyai derajat r.
Sebagai contoh pada gambar 2.3, graf G adalah
graf 3 − reguler.
Gambar 2.3 Graf Reguler
Komplemen dari graf G dinotasikan G adalah
graf dengan himpunan titik V(G ) = V(G)
dimana titik u, v tetangga pada G jika dan hanya
jika titik u,v bukan tetangga pada G. Contoh graf
dan komplemennya dapat dilihat pada gambar
2.4.
Gambar 2.4 Graf dan Komplemennya
Jalan (walk) W dengan panjang n dari titik a ke b
pada graf G adalah barisan titik a = vo, e1, v1, e2,
v2, e3, v3, …, vn-1, en, vn = b (n ≥ 0) yang terdiri
dari titik dan sisi di G yang diawali dan diakhiri
dengan titik, sedemikian hingga (vi, vi+1) adalah
sisi di G untuk setiap i = 0, 1, 2, …, n-1. Jalan ini
menghubungkan titik vo dan vn, dan dapat juga
dinotasikan sebagai vo-v1-…-vn. Jalan dikatakan
tertutup jika a = b dan terbuka jika a ≠ b.
Sebagai contoh pada gambar 2.5, x–w–y–v–u–x
adalah jalan tertutup dengan panjang 5 dan u–vw–
x–u–v–y adalah jalan terbuka dengan panjang 6.
Jejak (trail) adalah jalan dimana tidak ada sisi
yang berulang. Jalan dikatakan lintasan (path)
jika semua titiknya berbeda. Lintasan adalah
jejak, akan tetapi tidak semua jejak adalah
lintasan. Sedangkan lintasan tertutup dinamakan
sikel (cycle). Pada gambar 2.5, jalan x–w–v–u–w–y
adalah jejak tetapi bukan lintasan, sedangkan ux–
w–v–y adalah lintasan, dan u–w–y–v–u adalah
sikel.
Gambar 2.5 Walk pada 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). Sebagai contoh pada gambar
2.6, G1 dan G2 adalah subgraf dari G tetapi G3
bukan subgraf dari G karena ada sisi xw di E(G3)
yang bukan elemen dari E(G).
Gambar 2.6 Graf dan Subgrafnya
Komponen dari G adalah subgraf terhubung
maksimal dari G. Jadi setiap graf terhubung
hanya mempunyai satu komponen dan untuk graf
tak terhubung mempunyai sedikitnya dua
komponen. Gambar 2.7 (a) adalah graf
terhubung dan 2.7 (b) adalah graf tak terhubung
dengan dua komponen.
Gambar 2.7 Graf terhubung dan graf tak terhubung
Jarak d(u,v) antara dua titik u dan v pada graf G
adalah panjang lintasan terpendek dari titik u ke
v. Jika tidak ada lintasan dari titik u ke v, maka
kita definisikan jarak d(u,v) = ∞. Sebagai contoh,
graf pada gambar 2.8, d(u,v) = 2 sedangkan d(v,
w) = ∞.
Gambar 2.8 Jarak pada Graf
Eksentrisitas ec(v) pada titik v dalam graf G
adalah jarak terjauh (maksimal lintasan
terpendek) dari titik v ke setiap titik di G, dapat
dituliskan ec(v) = max{d(v,u)|u ∈ V(G)}. Radius
r(G) dari G adalah eksentrisitas minimum pada
setiap titik di G, dapat dituliskan r(G) =
min{ec(v)|v∈V} dan diameter dari G,
dinotasikan dia(G) adalah eksentrisitas
maksimum pada setiap titik di G, dapat
dituliskan dia (G) = maks{ec(v)|v∈V}, titik v
disebut titik central jika ec(v) = r(G), center
dinotasikan cen(G) adalah subgraf pada G yang
terbentuk dari titik central. Titik v dikatakan titik
eksentrik dari u jika jarak dari v ke u sama
dengan titik eksentrik dari u, dapat dituliskan
d(v,u) = ec(u). Eksentrisitas titik, titik eksentrik,
radius, diameter dan center dari graf pada
gambar 2.9 adalah sebagai berikut :
Gambar 2.9 Eksentrisitas
Titik Eksentrisitas Titik Eksentrik
a ec(a) = 3 f
b ec(b) = 2 c, f
c ec(c) = 3 f
d ec(d) = 2 a, f
e ec(e) = 2 a, c
f ec(f) = 3 a, c
Jadi r(G) = 2, dia (G) = 3, cen(G) =
Graf yang setiap dua titik yang berbeda adalah
tetangga disebut graf komplit. Graf komplit
dengan n titik dinotasikan Kn. Contoh graf
komplit K2 dan K3 ditunjukkan pada gambar
2.10.
Gambar 2.10 Graf komplit
Graf yang terdiri dari satu lintasan disebut graf
lintasan. Graf lintasan dengan n titik dinotasikan
Pn. Contoh graf lintasan P2, P3 dan P4 dapat
dilihat pada gambar 2.11.
Gambar 2.11 Graf Lintasan
Sebuah graf yang terdiri dari satu lingkaran
disebut graf sikel. Graf sikel dengan n titik
dinotasikan Cn. Pada gambar 2.12 dapat dilihat
graf lingkaran C3, C4 dan C5.
Gambar 2.12 Graf Sikel
Graf G dikatakan bipartit jika himpunan titiktitik
V(G) dapat dipisah menjadi dua himpunan
V1(G) dan V2(G). Jika setiap pasang titik di V1
dan V2 saling terhubung maka graf tersebut
dinamakan graf komplit bipartit. Jika |V1| = m
dan |V2| = n, graf komplit bipartit dinotasikan
Km,n. Graf star adalah graf komplit bipartit K1,n
atau Kn,1. Untuk pembahasan selanjutnya graf
star K1,n atau Kn,1 akan dinotasikan dengan Sm,
dimana m = n + 1 Contoh graf komplit bipartit
K2,3 dan graf star S5 dapat dilihat pada gambar
2.13.
Gambar 2.13 Graf Komplit Bipartit
Graf star adalah graf komplit bipartit K1,n atau
Kn,1. Untuk pembahasan selanjutnya graf star
K1,n atau Kn,1 akan dinotasikan dengan Sm, dengan
m = n + 1, dimana 1 titik berderajat n disebut
titik central dan n titik berderajat 1 disebut titik
daun. Contoh graf star S5 dapat dilihat pada
gambar 2.14.
Gambar 2.14 Graf Star
Sebuah pohon (tree) T adalah graf terhubung
yang tidak memuat sikel (cycle). Sebagai contoh,
pada gambar 2.15 adalah pohon dengan order 6.
Gambar 2.15 Pohon
Pohon T dikatakan double star jika terdiri dari
dua graf star Sn dan Sm, dimana kedua titik
centralnya saling bertetangga, dinotasikan Sn,m
(selanjutnya akan ditulis graf double star).
Contoh graf double star S3,3 dapat dilihat pada
gambar 2.16.
Gambar 2.16 Graf double Star
Misal ada dua graf G1 dan G2 dimana himpunan
titik V(G1) dan V(G2) saling asing begitu juga
himpunan sisi E(G1) dan E(G2), maka gabungan
graf dinotasikan G1 ∪ G2 adalah graf yang
mempunyai himpunan titik V(G1 ∪ G2) = V(G1)
∪ V(G2) dan himpunan sisi E(G1 ∪ G2) = E(G1)
∪ E(G2). Sebagai contoh, pada gambar 2.17 graf
G = P2 ∪ C3 adalah gabungan graf lintasan P2
dan graf lingkaran C3.
Gambar 2.17 Graf gabungan
Digraf D adalah pasangan himpunan (V, A)
dimana V adalah himpunan tak kosong dari
elemen-elemen yang disebut titik dan A adalah
himpunan dari pasangan terurut (u, v) dari titik u,
v di V yang disebut arc. Pada gambar 2.18
menunjukkan sebuah graf berarah dengan
himpunan titik V(D) = {u, v, w, x} dan himpunan
arc A(D) = {(u, w), (v, u), (v, w), (w, x), (x, w)}.
Gambar 2.18 Digraf
Eksentrik Digraf ED(G) didefinisikan sebagai
graf yang mempunyai himpunan titik yang sama
dengan himpunan titik di G atau
V(ED(G))=V(G), dimana arc menghubungkan
titik u ke v jika v adalah titik eksentrik dari u.
Contoh graf dan eksentrik digrafnya diberikan
pada gambar 2.19.
Gambar 2.19 Graf dan eksentrik digrafnya
3. Eksentrik Digraf
Eksentrik Digraf dari Graf Star.
Misal graf star Sm mempunyai himpunan titik
V(Sm) = {vo, v1, v2,…, vm-1} dimana vo adalah
titik central dan v1, v2,…, vm-1 adalah titik daun,
dan himpunan sisi E(Sm) = {e1, e2, …, em-1}
dimana sisi ei = vovi untuk setiap i = 1, 2, 3, …,
m-1.
Sifat 3.1 Eksentrisitas titik vi pada graf star Sm
adalah sebagai berikut
1 untuk i = 0
ec(vi) =
2 untuk i = 1, 2, 3, …, m-1.
Dari definisi graf star, dimana vo adalah titik
central dan vi untuk setiap i = 1, 2, 3, …, m-1
adalah titik daun, maka dapat diketahui jarak
terjauh (maksimal lintasan terpendek) dari titik
central adalah semua titik daun, yaitu dengan
jarak 1. Jadi eksentrisitas titik ec(vo) = 1.
Demikian juga eksentrisitas dari titik daun
adalah titik daun lainnya, yaitu dengan jarak 2.
Jadi eksentrisitas titik ec(vi) = 2.
Akibat 3.1 Titik eksentrik pada graf star Sm
adalah sebagai berikut
vj untuk i = 0
titik eksentrik dari vi = j=1,2,3,…,m-1
vj untuk i,j=1,2,3,…,m-1
i ≠ j.
Dari sifat 3.1, eksentrisitas dari titik central vo
adalah 1, maka titik eksentriknya adalah semua
titik daun vj untuk setiap j = 1, 2, 3, …, m-1.
Demikian juga eksentrisitas dari titik daun vi
adalah 2 untuk setiap i = 1, 2, 3, …, m-1 maka
titik eksentriknya adalah semua titik daun vj
untuk setiap j = 1, 2, 3, …, m-1 dengan i ≠ j.
Dari eksentrisitas titik ec(vi) dan titik eksentrik
pada graf star Sm, selanjutnya kita mempunyai
sifat berikut:
Sifat 3.2 Eksentrik digraf dari graf star ED(Sm)
adalah digraf dengan himpunan titik V(ED(Sm))
= {vo, v1, v2,…, vm-1} dan himpunan arc
vovj untuk j = 1, 2, 3, …, m-1
A(ED(Sm)) =
vivj untuk i, j = 1, 2, 3, …, m-1
i ≠ j.
Dari akibat 3.1, titik eksentrik dari titik central
vo adalah titik daun vj untuk setiap j = 1, 2, …,
m-1, sehingga ada arc dari vo ke vj yaitu vovj.
Demikian juga untuk titik daun vi untuk setiap i
= 1, 2, …, m-1 titik eksentriknya adalah titik
daun vj untuk setiap j = 1, 2, …, m-1 dengan i
≠ j, sehingga ada arc dari vi ke vj yaitu vivj.
Dari sifat 3.2 dapat disimpulkan bahwa eksentrik
digraf dari graf star ED(Sm) adalah graf komplit
Km dimana arc dari titik central adjacent keluar
ke semua titik daun dan arc dari setiap titik daun
adjcent keluar ke setiap titik daun lainnya dengan
jumlah arc
|A(Km)| = |A(ED(Sm))| = (m-1)2.
Contoh eksentrik digraf dari graf star Sm
diberikan pada Gambar 3.1.
Gambar 3.1 Garf S5 dan eksentrik digrafnya
Eksentrik Digraf dari Graf Double Star.
Graf double star Sn,m adalah graf yang terdiri dari
dua graf star Sn dan Sm, dimana kedua titik
centralnya saling bertetangga. Misal graf double
star Sn,m mempunyai himpunan titik
V1 = {v1, v2, …, vn}
V(Sn,m) =
V2 = {vn+1, vn+2, …, vn+m}
dimana : v1 adalah titik central di V1, v2, v3, …,
vn adalah titik daun di V1, vn+1 adalah titik central
di V2 dan vn+2, vn+3, …, vn+m adalah titik daun di
V2, dan himpunan sisi
E1 = {e0} dimana e0 = v1vn+1
E(Sn,m) = E2 = {e1, e2, …, en-1} dimana ei = v1vi+1
untuk i = 1, 2, …, n-1
E3 = {en, en+1, …, en+m-2}dimana en-1+i =
vn+1vn+1+i untuk i = 1,
2, …, m-1.
Sifat 3.3 Eksentrisitas titik vi pada graf double
star Sn,m adalah sebagai berikut
2 untuk i = 1,n+1
ec(vi) =
3 untuk i = 2, 3, …, n,n+2,…,n+m
Dari definisi graf double star Sn,m, dimana v1 dan
vn+1 adalah titik central dan vi untuk setiap i = 2,
3, …, n, n+2, …, n+m adalah titik daun, maka
jarak terjauh (maksimal lintasan terpendek) dari
titik central v1 di V1 adalah semua titik daun di V2
dan jarak terjauh dari titik central vn+1 di V2
adalah semua titik daun di V1 yaitu dengan jarak
2. Jadi eksentrisitas titik ec(v1) = ec(vn+1) = 2.
Demikian juga jarak terjauh (maksimal lintasan
terpendek) dari titik daun di V1 adalah semua
titik daun di V2 dan jarak terjauh (maksimal
lintasan terpendek) titik daun di V2 adalah semua
titik daun di V1 yaitu dengan jarak 3. Jadi
eksentrisitas titik ec(v2) = ec(v3) = … = ec(vn) =
ec(vn+2) = ec(vn+3) =… = ec(vn+m) = 3.
Akibat 3.2 Titik eksentrik pada graf double star
Sn,m adalah sebagai berikut:
vj untuk i = 1
j = n + 2, n + 3, …, n + m
vj untuk i = n + 1,
titik eksentrik dari vi = j = 2, 3, …, n
vj untuk i = 2, 3, …, n
j = n + 2, n + 3, …, n + m
vj untuk i = n + 2, n + 3,…,n + m
j = 2, 3, …, n.
Dari sifat 3.3, eksentrisitas dari titik central v1 di
V1 adalah 2, maka titik eksentriknya adalah titik
daun vj untuk setiap j = n+2, n+3, …, n+m di V2
dan eksentrisitas dari titik central vn+1 di V2
adalah 2, maka titik eksentriknya adalah titik
daun vj untuk setiap j = 2, 3, …, n di V1.
Demikian juga eksentrisitas dari titik daun vi
untuk setiap i = 2, 3, …, n di V1 adalah 3
sehingga titik eksentriknya adalah titik daun vj
untuk setiap j = n+2, n+3, …, n+m di V2 dan
eksentrisitas dari titik daun vi untuk setiap i =
n+2, n+3, …, n+m di V2 adalah 3 sehingga titik
eksentriknya adalah titik daun vj untuk setiap j =
2, 3, …, n di V1.
Eksentrisitas titik ec(vi) dan titik eksentrik dari
graf double star kita peroleh, maka kita
mempunyai:
Sifat 3.4 Eksentrik digraf dari graf double star
ED(Sn,m) adalah digraf dengan himpunan titik
V(ED(Sn,m)) = {v1, v2, v3, …, vn, vn+1, vn+2,
…, vn+m} dan himpunan arc
v1vj untuk j = n + 2, n + 3, …, n + m
vn+1vj untuk j = 2, 3, …, n
A(ED(Sn,m))= vivj untuk i = 2, 3, …, n
j = n + 2, n + 3, …, n + m
vivj untuk i = n + 2, n + 3,…,n + m
j = 2, 3, …, n.
Dari akibat 3.2, dimana titik eksentrik dari titik
central v1 di V1 adalah titik daun vj untuk setiap j
= n+2, n+3, …, n+m di V2, sehingga ada arc dari
v1 ke vj yaitu v1vj dan titik eksentrik dari titik
central vn+1 di V2 adalah titik daun vj untuk setiap
j = 2, 3, …, n di V1, sehingga ada arc dari vn+1 ke
vj yaitu vn+1vj. Demikian juga titik eksentrik dari
titik daun vi untuk setiap i = 2, 3, …, n di V1
adalah titik daun vj untuk setiap j = n+2, n+3, …,
n+m di V2, sehingga ada arc dari vi ke vj yaitu
vivj dan titik eksentrik dari titik daun vi untuk
setiap i = n+2, n+3, …, n+m di V2 adalah titik
daun vj untuk setiap j = 2, 3, …, n di V1,
sehingga ada arc dari vi ke vj yaitu vivj.
Dari sifat 3.4 dapat disimpulkan bahwa eksentrik
digraf dari graf double star ED(Sn,m) adalah
digraf bipartit D(Bn,m) yang mempunyai dua
himpunan titik yaitu V1(Bn) dan V2(Bm), dengan
V1(Bn) = {v1, v2, …, vn}dan V2(Bm) = {vn+1, vn+2,
…, vn+m}, dimana arc dari titik central v1 di V1
adjacent keluar ke titik daun di V2 dan arc dari
titik central vn+1 di V2 adjacent keluar ke titik
daun di V1, demikian juga arc dari titik daun V1
adjacent keluar ke titik daun di V2 dan arc dari
titik daun V2 adjacent keluar ke titik daun di V1
dengan jumlah arc
|A(ED(Sn,m))| = [(n – 1)m + (m – 1)n].
Contoh, eksentrik digraf dari graf double star Sn,m
diberikan pada Gambar 3.2.
Gambar 3.2 Graf S3,4 dan eksentrik diagrafnya
Eksentrik Digraf dari Graf Komplit Bipartit.
Misal graf komplit bipartit Km,n mempunyai
himpunan titik
V1 = {v1, v2, …, vm}
V(Km,n) =
V2 = {vm+1, vm+2, …, vm+n}
dan himpunan sisi E(Km,n) = {e11, e21, …,en1, e12,
…, en2, …,enm} dimana eij = vjvm+i untuk setiap i
= 1, 2, 3, …, n dan j = 1, 2, 3, …, m.
Sifat 3.5 Eksentrisitas titik vi pada graf komplit
bipartit Km,n adalah sebagai berikut:
ec(vi) = 2 untuk setiap i = 1, 2, 3, …, m+n
Dari definisi graf komplit bipartit, jarak terjauh
(maksimal lintasan terpendek) dari vi untuk
setiap i = 1, 2, …, m di V1 adalah semua titik di
V1 kecuali dirinya sendiri, demikian juga jarak
terjauh dari vi untuk setiap i = m+1, m+2, …,
m+n di V2 adalah semua titik di V2 kecuali
dirinya sendiri, yaitu dengan jarak 2. Jadi ec(vi) =
2 untuk setiap i = 1, 2, …, m+n.
Akibat 3.5 Titik eksentrik pada graf komplit
bipartit Km,n adalah sebagai berikut:
titik eksentrik di V1 dari vi = vj untuk i, j = 1, 2,
…, m
j ≠ i,
titik eksentrik di V2 dari vi = vj untuk i, j = m+1,
m+2, …, m+n
j ≠ i.
Dari sifat 3.5, titik eksentrik dari vi di V1 untuk
setiap i = 1, 2, …, m adalah vj di V1 untuk setiap
j = 1, 2, …, m dan j ≠ i dan titik eksentrik dari vi
di V2 untuk i = m+1, m+2, …, m+n adalah vj di
V2 untuk j = m+1, m+2, …, m+n dan j ≠ i.
Sifat 3.6 Eksentrik digraf dari graf komplit
bipartit ED(Km,n) adalah digraf dengan
himpunan titik V(ED(Km,n)) = {v1, v2, v3,…,
vm+n} dan himpunan arc
vivj untuk i, j = 1, 2, 3, …, m
A(ED(Km,n)) = j ≠ i
vivj untuk i,j = m+1,m+2,…,m+n
j ≠ i
Dari akibat 3.3, titik eksentrik dari vi di V1 untuk
setiap i = 1, 2, …, m adalah vj di V1 untuk setiap j
= 1, 2, …, m dengan j ≠ i, sehingga ada arc dari
vi ke vj yaitu vivj dan titik eksentrik dari vi di V2
untuk setiap i = m+1, m+2, …, m+n adalah vj di
V2 untuk setiap j = m+1, m+2, …, m+n dengan j
≠ i, sehingga ada arc dari titik vi ke vj yaitu vivj.
Dari sifat 3.6 dapat disimpulkan bahwa eksentrik
digraf dari graf komplit bipartit ED(Km,n) adalah
digraf komplemen Km,n = D (Km,n ) dengan
himpunan titik V (D (Km,n)) = V(Km,n) dimana
arc dari V1 adjacent keluar ke semua titik di V1
demikian juga di V2 dengan jumlah arc
|A(ED(Km,n))| = [(m2 + n2) – (m + n)].
Contoh, graf komplit bipartit Km,n dan eksentrik
digrafnya diberikan pada gambar 3.3.
Gambar 3.3 Graf komplit bipartit K3,3 dan eksentrik
diagraf
4. Kesimpulan
Berdasarkan pembahasan yang telah dilakukan,
maka kesimpulan yang dapat diambil mengenai
eksentrik digraf dari graf star, graf double star
dan graf komplit bipartit adalah sebagai berikut:
1. Eksentrik digraf dari graf star ED(Sm) adalah
graf komplit Km, dimana arc dari titik central
adjacent keluar ke titik daun dan arc dari titik
daun adjcent keluar ke titik daun lainnya
dengan jumlah arc |A(Km)| = |A(ED(Sm))| =
(m-1)2.
2. Eksentrik digraf dari graf double star
ED(Sn,m) adalah digraf bipartit D(Bn,m),
dengan himpunan titik V1(Bm) = {v1, v2, …,
vn}dan V2(Bm) = {vn+1, vn+2, …, vn+m}, dimana
arc dari titik central v1 di V1 adjacent keluar
ke titik daun di V2, arc dari titik central vn+1 di
V1 adjacent keluar ke titik daun di V2, arc dari
titik central vn+1 di V2 adjacent keluar ke titik
daun di V1, arc dari titik daun V1 adjacent
keluar ke titik daun di V2 adjacent keluar ke
titik daun di V1 dengan jumlah arc
|A(ED(Sn,m))| = [(n – 1)m + (m – 1)n].
3. Eksentrik digraf dari graf komplit bipartit
ED(Km,n) adalah digraf komplemen D(Km,n),
dengan himpunan titik V(D(Km,n))= V(Km,n),
dimana arc dari V1 adjacent keluar ke semua
titik di V1 dan arc dari V2 adjacent keluar ke
semua titik di V2 dengan jumlah arc
|A(ED(Km,n))| = [(m2 + n2) – (m + n)].
DAFTAR PUSTAKA
[1] Nugroho, Kustanto Widi. 2002 . http://www.unej.ac.id/fakultas/mipa/skripsi/widi.pdf . Tanggal akses:
28 Desember 2006 pukul 17:00.
[2] Munir, Rinaldi. 2006. Matematika Diskrit Edisi Keempat. Departemen Teknik Informatika, Institut
Teknologi Bandung.
[3] Gary Chartrand & Ortrud R. O. 1993. Apllied and Algorithmic Graph Theory. McGraw. Hill, Inc.
[4] Townsend, Michael . 1987 . Discrete Mathemathic : Applied Combinatorics and Graph Theory . The
Benjamin/Cummings Publishing Company, Inc.
[5] Wilson , Robin J. & John J. Watkins . 1990 . Graphs an Introductory Approach . John Wiley & Sons,
Inc.
[6] Buckley, F. —- . The Eccentric Digraph of a Graph, preprint.
[7] Chartrand, G. and Lesniak . 1996 . Graphs & Digraphs, 3rd ed . Chapman & Hill.
sumber : http://repository.unand.ac.id/181/1/35-40_zainal_abidin.pdf
dewiprifina 