Abdussakir

Dzikir, Fikir, dan Amal Shaleh

Open Problem dalam Graf: Jarak dan Eksentrik Digraf

Posted by abdussakir on October 28, 2008

Misalkan G suatu graf serta u dan v titik di G. Jarak dari u ke v di G, ditulis d(u,v), adalah panjang lintasan (path) terpendek dari u ke v di G. Himpunan V(G) dengan fungsi jarak d membentuk ruang metrik (metric space).

Masalah 1. Apakah Anda tertarik membahas ruang metrik dari suatu graf?

Jarak terjauh dari titik u ke semua titik yang lain pada graf G disebut eksentrisitas titik u dan ditulis
e(u).
Jadi
e(u) = maks d(u,v), untuk setiap v titik di G.
Titik v disebut titik eksentrik dari titik u, jika
d(u,v) = e(u).
Perlu dicatat bahwa titik eksentrik tidak harus tunggal. Radius graf G, ditulis rad G, adalah eksentrisitas terkecil dari semua titik di G, sedangkan diameter graf G, ditulis diam G, adalah eksentrisitas terbesar dari semua titik di G. Jadi,
rad G = min e(v), dan diam G = maks e(v), untuk setiap v titik di G.
Titik v disebut titik sentral dari graf G, jika e(v) = rad G. Himpunan titik sentral disebut zenter dari G, dan ditulis Z(G). Graf yang hanya memuat satu titik sentral disebut graf unisentral.

Masalah 2. Tentukan banyaknya titik minimum agar suatu graf unisentral G mempunyai radius r dan diameter d, (r dan d bilangan asli serta r < d < 2r)!
Masalah 2.1. Tentukan banyaknya titik minimum agar suatu graf unisentral G mempunyai radius r dan diameter 2r, (r bilangan asli)!
Masalah 2.2. Tentukan banyaknya titik minimum agar suatu graf unisentral G mempunyai radius r dan diameter r, (r bilangan asli)!

Kembali ke masalah eksentrisitas dan titik eksentrik. Misalkan G graf dengan himpunan titik V(G) dan himpunan sisi E(G). Digraf D dengan V(D) = V(G) dan ada busur dari titik u ke titik v dengan syarat v adalah titik eksentrik dari u, disebut eksentrik digraph dari graf G.

Masalah 3. Tentukan bentuk umum dan sifat-sifat eksentrik digraph dari berbagai jenis graf, selain graf lintasan, sikel, star dan double star, komplit, serta bipartisi komplit.

3 Responses to “Open Problem dalam Graf: Jarak dan Eksentrik Digraf”

  1. udin said

    Assalamu`alaikum,…
    Pak, saya coba mencari rumus umum mencari line digraph pada suatu graph, saya coba dulu graf roda dengan banyaknya titik 4, dengan memanfaatkan matrik ketetanggaan, saya cari model matrik pada graph roda, titiknya empat, kemudian saya cari line graphnya, kemudian saya bentuk matriknya juga, pikiran saya dengan sebuah fungsi komposisi tertentu, saya bisa mengubah matrik dari graph roda (daerah asalnya) menjadi matrik line graph dari graf roda, tapi mbulet, ada saran “jenis graf apa yang harus saya cari, yang ada polanya sesuai kasus diatas”, sukron.

  2. asis as adi haq said

    Assalamu`alaikum,…

    maaf pak saya hari ini g sengaja ketemu dengan blog bapak, saya mau curhat masa depan saya,saya bingung dengan nasib kedepan saya padahal dirumah uda menanti-nanti kepalangan saya dengan membawa gelar sarjana tapi ternyata saya masih belum bisa mewujudkan impian orang tua saya itu.apakah saya harus berhenti dan menghapus keinginan mereka yang ingin sekali melihat anaknya bisa menjadi sarjana.dalam sejarah keluarga saja kami hanya orang biasa mungkin kelihatan seperti orang punya tapi padahal semua serba kredit mulai dari hp tipe 3315 ampe motor yang ampe sekarang sangat mencekik kehidupan kami.tapi saya sebenarnya heran saya g pernah minta dibeliin apapun tapi mereka yang sepertinya memaksakan diri mungkin kasihan ngihat anaknya yang satu ini kemarin naik sepeda ontel yang setiap harinya pulang pergi k kampus.bapak mungkin pernah jalan2 kerumahnya pak usman, masya Allah pak jalannya betul2 bikin kaki saya g pernah lepas dari polesan balsem balpirik, sebenarnya saya g ingin pulang, setelah mengingat2 masa2 sulit itu.mohon doanya yaa pak semoga saya bisa menjadi orang yang paling berbakti diantara anak2 yang ada didunia ini.mungkin orang tua saya kangen,rindu kalo keluar kemana2 minta ditemenin anaknya yang satu ini, maklum beliu lagi kena struk kemana2 g bisa sendirian..tapi saya bisa melihat ada yang ingin diajarkan ma anaknya. dia ingin mengajarkan anak2nya tidak lemah terhadap kehidupan.sekeras apapun hidup ini, janngan pernah menyerah.terima kasih bapak, bapak mengajarkan saya banyak hal tentang kehidupan selain ilmu dikelas.terima kasih

  3. asis as adi haq said

    jangan lupa yaa pak, saya masih belum bisa membuktikan graf Tripartisi T2,n-1,n yang bapak ajarkan kemarin,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: