Abdussakir

Dzikir, Fikir, dan Amal Shaleh

GRAF GARIS (LINE GRAPH)

Posted by abdussakir on December 27, 2008

Misalkan G graf dengan himpunan titik V(G) yang tidak boleh kosong dan himpunan sisi E(G) yang merupakan pasangan tak terurut dari unsur-unsur yang berbeda di V(G). E(G) boleh merupakan himpunan kosong.

Jika e = (u,v) adalah sisi di G, maka u dan v disebut terhubung langsung (adjacent). u dan e serta v dan e disebut terkait langsung (incident). Titik u dan v disebut titik ujung dari e. Sisi e1 dan e2 disebut terhubung langsung (adjacent) di G, jika e1 dan e2 bersekutu pada satu titik ujung yang sama.  

Graf garis (line graph) dari graf G, dinotasikan dengan L(G), adalah graf dengan V(L(G)) = E(G) dan dua titik akan terhubung langsung (adjacent) di L(G) jika sisi yang bersesuaian terhubung langsung di G. Secara sederhana dapat dikatakan bahwa graf garis L(G) dari graf G adalah graf yang himpunan titiknya adalah himpunan sisi-sisi di G dan dua sisi tersebut akan terhubung langsung di L(G) jika keduanya terhubung langsung di G.

Sebagai contoh, graf lintasan (path) Pn dengan himpunan titik {v1, v2, v3, …, vn} dan himpunan sisi {e1, e2, e3, …, en-1} dengan ei = (vi,vi+1), i = 1, 2, …, n-1. Maka graf garis dari Pn atau L(Pn) mempunyai himpunan titik {e1, e2, e3, …, en-1}. Karena sisi ei hanya terhubung langsung dengan ei+1, i = 1, 2, …, n-2 di Pn, maka L(Pn) mempunyai himpunan sisi {(e1,e2), (e2,e3), …, (en-2,en-1)}. Jadi, L(Pn) tidak lain berbentuk Pn-1.

Nah, tugas Anda adalah menentukan

1.      Bentuk umum graf garis dari graf-graf yang lain selain graf lintasan, sikel, dan bintang.

2.      Ciri-ciri suatu graf G sehingga L(L(G)) = G.

3.      Ciri-ciri suatu graf G sehingga L(L(L(G))) = G.

Atau lainnya. Mau coba????

7 Responses to “GRAF GARIS (LINE GRAPH)”

  1. imam said

    Assalamu`alaikum, pak, saya minta topik yang bagus buat skripsi graf yang tidak monoton pada ilmu graf, ada campuran ilmu lain, soalnya skripsi graph di perpus tidak ada perkawinan dengan ilmu lain, seperti aljabar atau geometri?
    trimakasih.

  2. abdussakir said

    Datang aja ke kantor, nanti saya beritahu perkawinan graf dengan aljabar linear, aljabar abstrak, atau al-qur’an. Siapa tahu Anda tertarik. Ok, saya tunggu.

    • mollycoddle said

      pak, boleh tau gak,,, apa manfaat dari graf garis??

      • abdussakir said

        saya belum pernah membaca tentang manfaat graf garis itu, terutama aplikasinya, matematika itu kadang hanya fokus pada pencarian pola, tanpa melihat aplikasi nyatanya.

  3. luluk '04 said

    Assalamu’alaikum,pak…saya mau numpang tanya, saya mengambil materi tugas akhir tentang line graf yaitu pada graf helm dan graf helm tertutup. saya sudah menemukan bentuk umumnya, tapi hasil gambar pada line graf helm dan helm tertutup belum menemukan nama dari graf itu!!terus solusinys gimana Pak? saya bingung untuk untuk memberikan nama pada hasil gambar line graf dari graf helm dan graf helm tertutup!sebelunya saya ucapkan terima kasih Pak…

  4. yuli said

    pak, saya mau numpang tanya… kalau hubungannya graf piramida dengan graf garis apa ya???

  5. rispa said

    pak boleh tahu apa manfaat atau aplikasi dari graf garis

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: