6. Graf

Graf adalah suatu visualisasi objek yang memuat suatu informasi tertentu.

Suatau graf terdiri dari dua himpunan tak kosong, yaitu himpunan titik (vertices) V(G) dan himpunan garis (edges) E(G). Dapat dikatan Graf adalah kumpulan titik dan garis. Titik melambangkan objek dan garis melambangkan hubungan antar objek.

Contoh stasiun kereta api (titik) dan relkereta (garis).

Istilah-istilah Graf:

Vertex: Titik
Edge: Garis
Order: Jumlah titik
Size: Jumlah garis
Degree: Jumlah garis pada suatu titik
Loop: Garis dengan titik awal dan akhir yang sama
Parrarel Edge: 2garisyang menghubungkan 2 titik yang sama.

A. Graf Tak Berarah

Graf dibawah ini memiliki 3 titik (order 3) dan 5 garis (size5)

B. Graf Sederhana

Graf sederhana (simple graph) adalah graf yang tidak mempunyai loop dan parallel edges.

Bukan Graf sederhana Graf sederhana

C. Graf Lengkap

Graf lengkap (complete graph) Kn adalah graf sederhana dengan n titik dimana setiap dua titik dihubungkan dengan satu garis.

Jadi masing-masing titik memiliki jumlah garis:jumlah titik - 1

D. Graf Bipartite

Graf Bipartite (bipartite graph) adalah suatu graf yang himpunan titiknya dipartisi menjadi dua himpunan yang saling lepas V1 dan V2 dengan setiap garis yang menghubungkan satu titik di V1 dan satu titik di V2.

E. Graf Bipartite Lengkap

Graf bipartite lengkap (complete bipartite graph) Km,n adalah suatu graf bipartite dengan setiap titik di V1 dihubungkan oleh garis ke setiap titik di V2.

K3,4

F. Graf Komplemen

Komplemen suatu graf G dengan simbol:

dengan n titik adalah suatu graf dengan:

Jumlah titik G sama dengan jumlah titik yang ada di G komplemen jadi:
Garis yang ada pada G komplemen tidak sama dengan garis yang ada pada G,
Titik-tik yang dihubungkan dengan garis di G tidak terhubung di G komplemen dan sebaliknya.

G. Sub Graf

Suatu graf H dikatakan subgraf dari graf G jika dan hanya jika:

Himpunan titik H merupakan subset dari himpunan titik G, dituliskan :

Himpunan garis H merupakan subset dari himpunan garis G, dituliskan:

Setiap garis dalam H mempunyai titik ujung yang sama dengan setiap garis dalam G

H. Derajat

Misalkan v adalah suatu titik dalam suatu graf, derajat titik v, deg(v) adalah jumlah garis yang masuk maupun yang keluar dari titik v. Garis suatu loopdihitung 2 kali.

I. Walk dan Path

Misalkan v0 dan vn adalah dua titik dalam suatu graf G. Suatu walk dari v0 ke vn dengan panjang n adalah barisan bergantian dari (n+1) titik dan n garis yang dimulai dari titikv0 dan berakhir di titik vn.
Suatu part dari v ke w adalah suatu walk dari v ke w dengan tidak ada titik yang diulang.