EKSENTRIK DIGRAF PADA GRAF LINTASAN, GRAF SIKEL DAN GRAF LENGKAP

Abstract

Jarak (distance) antara titik u dan v di graf G, dinotasikan dengan d(u,v) adalah panjang lintasan terpendek dari ke v di G. Jika tidak ada lintasan dari it ke v, maka d(u,v) = co. Eksentrisitas titik v di graf G, dinotasikan e(v), adalah jarak terjauh dari v ke setiap titik di G. Titik v adalah titik eksentrik dari u jika jarak dari v ke it sama dengan eksentrisitas dari u atau d(v, u) = e(u). Eksentrik digraf pada graf ED(G) didefinisikan sebagai graf yang mempunyai himpunan titik yang sama dengan atau V(ED(G)) = V(G) dimana arc menghubungkan titik u ke v, jika v adalah titik eksentrik dari u. Penulisan skripsi ini bertujuan untuk mendapatkan eksentrik digraf pada graf path (Mutual?), graf cycle (sikel) dan graf complete (lengkap). Hasil dad penelitian yang telah dilakukan didapatkan bahwa: eksentrik digraf pada graf lintasan dibedakan menjadi dua, yaitu graf lintasan dengan jumlah titik n ganjil, eksentrik digrafnya ED(P„) berupa digraf tripartit, sedangkan graf lintasan dengan jumlah titik genap, eksentrik digrafnya ED(P„)berupa digraf bipartite Eksentrik digraf pada graf Sikel juga dibedakan menjadi dua, yaitu graf sikel dengan jumlah titik n ganjil, eksentrik digrafnya ED(C.:„) berupa digraf sikel dengan arc simetrik yang _lank setiap arcnya 11 - 1 2sedangkan graf sikel dengan jumlah titik n genap, eksentrik digrafnya ED(G) berupa gabungan 2 —n digraf lintasan dengan arc simetrik. Selanjutnya eksentrik digraf dari graf lengkap ED(K„) didapatkan digraf lengkap dengan arc simetrik.