Graf

Secara umumnya, graf ialah koleksi titik-titik, dengan beberapa titik yang disambungkan

dengan garisan. Titik atau ‘dot’ dipanggil sebagai bucu manakala garisan dipanggil

sebagai sisi atau garis.

Darjah bagi bucu pada suatu graf adalah bilangan sisi-sisi yang menyentuh kepada

bucu. Manakala bagi garis atau sisi yang bermula dan berakhir pada titik yang sama

mempunyai darjah 2.

A B

C

D

sisi / garisbucu

Darjah : A = 1 B = 1

loop

Darjah : C = 2Darjah : D = 1

directed graph

Definisi dan teorem asas :

Jalan (Walk)

- Jalan adalah jujukan berselangseli antara bucu dan sisi, bermula dan berakhir dengan

bucu.

- Bucu kedua bagi setiap sisi (kecuali sisi terakhir) merupakan bucu pertama bagi sisi

yang berikut.

Jejak (Trail)

- Jejak ialah jalan di mana semua sisi adalah berbeza.

Laluan (Path)

- Jika bucu bagi suatu jejak adalah berbeza, maka ianya dipanggil sebagai laluan (path).

- Laluan juga adalah jejak di mana tiada bucu berulang.

Kitaran (Cycle)

- Suatu jalan atau jejak atau laluan adalah tertutup jika bucu pertama juga ialah bucu

terakhir.

- Laluan yang tertutup dengan paling kurang satu bucu dipanggil kitaran (cycle).

Pokok (Tree)

- Setiap graf mestilah bersambung dan tidak mempunyai sebarang kitaran (cycle).

CONTOH :

A B

DC

Graf ringkas (simple graph)

Graf ringkas ialah apabila ianya hanya ada satu sisi disambung kepada dua titik. Tiada lingkaran pada graf ringkas ini.

Kitaran Hamiltonian atau laluan Hamiltonian

Sebuah rangkaian atau litar dalam graf dikatakan menjadi Hamiltonan jika setiap bucu

graf muncul tepat sekali (jalan yang melalui setiap bucu graf hanya sekali). Laluan dan

kitaran digraf dipanggil Hamiltonan jika mengandungi litar Hamiltonian. Laluan

Hamiltonian tidak semestinya melalui semua sisi graf.

- CD, DA, AB, BD, DA adalah walk (jalan)

dan dipanggil juga jalan dari C ke A.

- CD, DA, AB, BD, DA bukan jejak (trail)

kerana DA berulang dua kali tetapi CD,

DA, AB, BC dan CA adalah trail dari C ke

A.

- Trail dari C ke A bukan laluan (path)

kerana A dan C bertemu dua kali.

- CD, DA, AB adalah laluan dari C ke B.

Digraf

Digraf ialah suatu graf di mana sisi-sisinya mempunyai arah yang dikaitkan padanya

dan dipanggil arcs. Secara formalnya, digraf ialah satu set bucu bersama-sama dengan

satu set arcs. Dibawah ialah contoh 5 bucu :

Graf sempurna (Complete Graph)

Graf di mana setiap bucu disambung pada tiap-tiap bucu oleh satu garis tunggal. Graf

sempurna dengan n bucu dipanggil sebagai Kn.

Isomorfik (Isomorphic)

Dua graf ialah isomorfik jika mereka adalah graf yang sama, tetapi dilukis secara

berbeza. Dua graf isomorfik jika anda boleh melabelkan kedua-dua graf dengan label

K4 – mempunyai empat bucu dan empat sisi.

yang sama supaya setiap bucu mempunyai jiran (neighbours) yang hampir sama dalam

kedua-dua graf. Berikut adalah dua graf isomorfik :

*neighbour : jiran bagi suatu bucu adalah semua bucu yang mana ia bersebelahan.

Graf Planar (Planar Graph)

Graf planar adalah graf yang boleh dilukis pada permukaan yang rata, atau satah,

tanpa mana-mana sisi menyeberangi. Graf yang tidak boleh dilukis pada satah tanpa

pinggir berpalang atau menyeberang dipanggil graf bukan planar (non-planar graph).

Mana-mana graf yang mempunyai sama ada graf berikut sebagai subgraf adalah graf

bukan planar :

Graf Bipartite (Bipartite Graph)

Suatu graf adalah bipartite (dua bahagian) jika bucu boleh dibahagikan kepada dua set,

X dan Y oleh itu hanya sisi graf yang berada diantara bucu dalam X dan bucu dalam Y.

Pokok adalah contoh bagi graf bipartite.

Graf Bersambung (Connected Graph)

Graf di mana setiap bucu disambungkan (dengan satu sisi atau lebih satu sisi) antara

satu sama lain. Setiap pasangan bagi bucu adalah disambungkan dengan rantai. Graf

yang tidak disambungkan dipanggil disconnected, dan dipecahkan kepada connected

components.

Rujukan : http://www-math.ucdenver.edu/~wcherowi/courses/m4408/glossary.htm