02 graf tidak berarah
TRANSCRIPT
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 1/7
GRAF TIDAK BERARAH
Sistem Informasi
Universitas Gunadarma2012/2013
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 2/7
GRAF TIDAK BERARAH
Graf Sederhana adalah graf yang tidakmemiliki Loop ataupun Garis Paralel.
Graf Lengkap dengan n titik (simbol Kn) adalahgraf sederhana dengan n titik di mana setiap2titik yang berbeda selaludihubungkan dengan
suatu garis. anyaknya garisdalam suatu graf lengkapdengan n titik adalah buah
2
)1( nn
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 3/7
GRAF TIDAK BERARAH
Graf Bipartite adalah graf G yang himpunan
titiknya (V(G)) dapat dibagi menjadi 2 himpunanyaitu Va dan Vb.
Setiap garis dalam G menghubungkan titik di Vadengan titik di Vb.
Semua titik dalam Va atau Vb tidak saling berhubungan.
Apabila setiap
titik di Va berhubungan dengan
setiap
titik di Vb maka disebut Graf Bipartite
Lengkap
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 4/7
GRAF BERLABEL
Graf G disebut berlabel jika ruas dan atau
simpulnya dikaitkan dengan suatu besaran
tertentu. Khususnya jika setiap ruas e dari G
dikaitkan dengan suatu bilangan non negatif
d(e), maka d(e) disebut bobot atau panjang
dari ruas e.
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 5/7
GRAF BERLABEL
Graf erlabel adalah graf tanpa garis paralelyang setiap garisnya berhubungan denganbilangan riil positif yang menyatakan bobot
garis tersebut. Simbol graf berlabel adalah w(e).
Total Bobot : jumlah bobot semua garis dalam
graf.
Bobot suatu garis dapat mewakili “ jarak”,
“biaya”, “panjang ”, “kapasitas”, dll.
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 6/7
KASUS GRAF TIDAK BERARAH
Masalah Lintasan Euler
Masalah Pedagang Keliling (Travelling
Salesman Problem)
7/21/2019 02 Graf Tidak Berarah
http://slidepdf.com/reader/full/02-graf-tidak-berarah 7/7
TERIMA KASIH