EKSENTRISITAS DIGRAF PADA GRAF TANGGA

Abstract

Misalkan  adalah graf dengan himpunan simpul  dan himpunan sisi . Jarak dari simpul  ke simpul  adalah panjang lintasan dari simpul ke , dinotasikan . Jarak adalah  jumlah sisi-sisi yang di lewati dari satu titik ke titik yang lain. Jarak pada graf berbobot yang dihitung adalah jumlah bobot pada setiap sisinya, sedangkan pada graf tak berbobot yang dihitung adalah banyaknya sisi yang dilalui. Eksentrisitas simpul  dalam graf  adalah jarak terjauh dari titik  ke setiap simpul di , dinotasikan dengan . Simpul  merupakan titik eksentrik dari  jika . Eksentrik digraf dari suatu graf  dinotasikan dengan . Eksentrik digraf adalah graf yang mempunyai himpunan simpul yang sama dengan himpunan simpul di , dan arc yang menghubungkan simpul  ke simpul  adalah eksentrisitas dari simpul  ke simpul  Penelitian ini bertujuan menentukan eksentrisitas digraf pada graf tangga  Diberikan graf tangga dengan  simpul, kemudian menentukan jarak dari setiap simpul  dan  ke semua simpul di  Selanjutnya  dicari titik eksentrik dari setiap simpul di   ke semua simpul di  Didapat bahwa titik eksentrik dari simpul  adalah dengan  dengan jarak , kemudian titik eksentrik dari  adalah dengan jarak . Setelah mendapat titik eksentrik dari setiap simpul maka selanjutnya mengkonstruksikan eksentrik digraf ke dalam graf berarah.

Kata Kunci: komplemen graf, graf lintasan, jarak terjauh