GRAF
A. Pengertian Graf
Secara sederhana graf didefinisikan adalah kumpulan titik yang dihubungkan oleh garis. Secara sistematis, graf adalah pasangan himpunan { V,E } dimana V, adalah himpunan tak kosong yang memiliki elemen disebut simpul ( vertices ) dan E adalah dari dua elemen subsets V yang disebut busur ( edges ).
B. Jenis-jenis Graf
1. Graf Sederhana ( simple graph )
Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana.
2. Graf Tak Sederhana ( unsimple graph )
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana. Ada dua macam graf tak sederhana, yaitu ganda ( multigraph) atau graf semu ( pseudograph ). Graf ganda adalah yang mengandung sisi ganda, sedangkan Graf semu adalah graf yang mengandung gelang.
Berdasarkan orientasi arah pada sisi, maka secara umum Graf dibedakan menjadi dua:
1. Graf Tak Berarah
Pada graf yang tak berarah urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, ( u,v ) = ( v,u ) adalah sisi yang sama.
2. Graf Berarah
Pada graf berarah ( u,v ) dan ( v,u ) menyatakan dua buah busur yang berbeda.
Sirkuit Euler
Sirkuit dimana setiap titik dalam graf muncul paling sedikit sekali, dan setiap garis dalam graf muncul hanya satu kali.
Sirkuit Hamilton
Suatu graf terhubung disebut Sirkuit Hamilton, bila ada sirkuit setiap titiknya dikunjungi sekali.
Berikut ini adalah contoh gambar dari Graf derajat 3, 4, 5 beserta Videonya:
