EKSENTRIK DIGRAF DARI GRAF STAR, GRAF DOUBLE STAR DAN GRAF KOMPLIT BIPARTIT

Abstract

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) = 00. 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).