Graf adalah suatu diagram yg memuat informasi Tujuan merepresentasikan obyek-obyek diskrit dan hubungan obyek2 tersebut. Secara visual obyek dinyatakan dg bulatan kecil dan
hubungan obyek dinyatakan dg garis, garis bisa berarah ataupun tdk berarah.
Contoh : Strktur organisasi, peta rangkaian listrik dll.
Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, dimana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).
Teori graf memiliki definisi yang bervariasi. Di bawah ini
merupakan definisi dasar graf dan strukturnya
Sebuah graf atau graf tidak berarah G adalah sebuah pasangan G := (V, E) yang memenuhi
kondis:
V adalah
sebuah himpunan
yang elemennya dinamakan sudut atau simpul
E adalah
sebuah himpunan dari pasangan-pasangan sudut yang terpisah, yang dinamakan sisi
atau garis
Suatu graph G dapat dinyatakan sebagai G =< V, E > . Graph
G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan
dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai
pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada
gambar di atas adalah : V = { 1, 2, 3, 4, 5, 6 } dan E =
{( 1, 2), ( 1, 5 ), ( 2, 3 ), ( 3, 4 ),
( 4, 5 ), ( 5, 2 ), ( 4, 6 )}
Pada digraf
maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf
(gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge
sebagai berikut :
E = {<1,2>, <1,5>,
<2,5>, <3,2>, <4,3>, <5,4>, <4,6>}
Dalam himpunan edge untuk digraf, urutan
pasangan verteks menentukan arah dari edge tersebut.
1.
Dasar-Dasar GRAF
Definisi Graf
Suatu Graf G terdiri dari 2 himpunan yg berhingga yaitu himpunan titik
tidak kosong dan himpunan garis.
- - Suatu grs
berhubungan dg satu titik atau dua titik (titik –titik tsb dsbut titik ujung), garis yang berhubungan dgn satu titik ujung disebut LOOP, dua grs yg beda menghubungkan
ttk yg sama disebut Garis Paralel.
-
- Dua titik
dikatakan berhubungan jika ada garis yg menghubungkan keduanya
-
- Titik yg tdk
memiliki garis yg berhubungan dgnya dsbut Titik Terasing
-
- Graf yg tidak
memiliki titik (shingga tdk memiliki garis) dsbut Graf Kosong
-
- Panjang garis ,
kelengkungan garis srta letak ttk tdk berpengaruh dlm suatu graf
- - Graf berarah jika
semua garisnya berarah, dan sebaliknya
Graf Tak Berarah
Graf Bipartite
Graf sederhana adalah graf yang tidak memiliki loop ataupun garis paralel
Komplemen Graf
Komplemen suatu graf G dinotasikan dengan G dengan n titik
adalah suatu graf sederhana dengan
1. Titik –titik G
sama dg titik G jadi V(G)=V(G)
2.
Garis –garis G
adalah komplemen garis-garis G terhadap graf lengkapnya (Kn) E(Ĝ)= Kn)
– E(G) berarti titi-titik yg dihubungkan dg garis dalam G
tidak terhubung dalam G dan sebaliknya titik-titik yg terhubung dalam G menjadi
tdk terhubung dalam G(dengan kata laingaris yg ada pada G tidak ada pada G)
Sub Graf
Misalkan G adalah suatu graf . Graf Hdikatakan subgraf G bila hanya bila
1.
V(H)ÍV(G)
2.
E(H)ÍE(G)
3. Setiap garis dalam
H memiliki titik ujung yg sama dg garis
tersebut dalam G
Sirkuit Euler
Adalah sirkuit dimana setiap titik dlm graf muncul paling sedikit sekali , dan setiap garis dlm graf muncul satu kali
Sirkuit Hamilton
Suatu graf terhubung disebut Sirkuit Hamilton bila ada sirkuit setiap titiknya dikunjungi sekali (kecuali titik awal yg sama dgtitik akhir) dan garisnya tdk semuanya harus dilalui.
Catatan
1)Sirkuit Euler setiap garisnya harus dilalui sekali , titiknya boleh dikunjungi lebih dari satu kali
2)Petunjuk untuk menentukan graf adl sirkuit hamilton adl memiliki sub graf H dg sifat
i) H terhubung
ii)H memuat semua titik G
iii) H memiliki jumlah garis yg sama dg jumlah titiknya
iv) setiap ttk dalam H mempunuai derajat 2
Adalah sirkuit dimana setiap titik dlm graf muncul paling sedikit sekali , dan setiap garis dlm graf muncul satu kali
Sirkuit Hamilton
Suatu graf terhubung disebut Sirkuit Hamilton bila ada sirkuit setiap titiknya dikunjungi sekali (kecuali titik awal yg sama dgtitik akhir) dan garisnya tdk semuanya harus dilalui.
Catatan
1)Sirkuit Euler setiap garisnya harus dilalui sekali , titiknya boleh dikunjungi lebih dari satu kali
2)Petunjuk untuk menentukan graf adl sirkuit hamilton adl memiliki sub graf H dg sifat
i) H terhubung
ii)H memuat semua titik G
iii) H memiliki jumlah garis yg sama dg jumlah titiknya
iv) setiap ttk dalam H mempunuai derajat 2
Berikut adalah gambar dan video contoh graf derajat 3, 4, dan 5
l Sumber :
