Terminologi Graf

• Ketetanggaan (adjocent) antara 2 simpul: bila kedua simpul tersebut terhubung langsung
• Contoh: G1= {{1,2},{1,3},{2,3},{2,4},{3,4}}
• Simpul 1 bertetangga dengan simpul 2 dan 3
• Simpul 1 tdk bertetangga dengan simpul 4
• Bersisian (incidency)
• Sisi e= {vj,vk}
• e bersisian dengan simpul vj dan
• e bersisian dengan simpul vk

Contoh :

• Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya

• Graf kosong adalah graf yang himpunan sisinya merupakan himpunan kosong

• Derajad suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut

Derajad (a) = 2
Derajad (b) = 2
Derajad (c) = 3
Derajad (d) = 1
Derajad (e) = 0

Jumlah Derajad = 8

Derajad pada graf tak berarah adalah GENAP atau 2x sisinya.

• Notasi : d(v)
• d(simpul terpencil)?
• d(simpul anting-anting) ?

Pada Graf Berarah

• din (v)= derajad masuk
• =jumlah sisi yang masuk kesimpul tersebut
• dout(v) = derajad keluar
• =jumlah sisi yang keluar dari simpul tersebut
• d(v)= din (v) + dout(v)

Contoh :

• Lintasan dari simpul awal v0 kesimpul tujuan vn
• Panjang lintasan adalah jumlah sisi dalam lintasan tersebut
• Sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama
• Graf disebut terhubung jika untuk setiap 2 pasang simpul vi dan vj terdapat lntasan dari vi ke vj