Jenis-jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:

1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G₁ pada Gambar 2 adalah contoh graf sederhana

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G₂ dan G₃ pada Gambar 2 adalah contoh graf tak-sederhna

Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berhingga (limited graph)

Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.

· Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.

2. Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

Jenis-jenis graf

Jenis	Sisi	Sisi ganda dibolehkan?	Sisi gelang dibolehkan?
Graf sederhana Graf ganda Graf semu Graf berarah Graf-ganda berarah	Tak-berarah Tak-berarah Tak-berarah Bearah Bearah	Tidak Ya Ya Tidak Ya	Tidak Tidak Ya Ya Ya

Graf Euler dan Hamilton

Graf Euler
Lintasan dan Sirkuit Euler
• Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.
• Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali..
• Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).
(a) dan (b) grafsemi-Euler, (c) dan (d) graf Euler , (e) dan (f) bukan graf semi-Euler atau graf Euler
Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1
Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3
Sirkuit Euler pada graf (c) : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1
Sirkuit Euler pada graf (d) : a, c, f, e, c, b, d, e, a, d, f, b, a
Graf (e) dan (f) tidak mempunyai lintasanmaupun sirkuit Euler

Teorema-teorema
• TEOREMA 6.2. Graf tidak berarah memiliki lintasan Euler jika
dan hanya jika terhubung dan memiliki dua buah simpul
berderajat ganjil atau tidak ada simpul berderajat ganjil sama
sekali.
• TEOREMA 6.3. Graf tidak berarah G adalah graf Euler
(memiliki sirkuit Euler) jika dan hanya jika setiap simpul
berderajat genap.
• (Catatlah bahwa graf yang memiliki sirkuit Euler pasti
mempunyai lintasan Euler, tetapi tidak sebaliknya)
• TEOREMA 6.4. Graf berarah G memiliki sirkuit Euler jika dan
hanya jika G terhubung dan setiap simpul memiliki derajat-
masuk dan derajat-keluar sama. G memiliki lintasan Euler jika
dan hanya jika G terhubung dan setiap simpul memiliki
derajat-masuk dan derajat-keluar sama kecuali dua simpul,
yang pertamamemiliki derajat-keluar satu lebih besar derajat-
masuk, dan yang kedua memiliki derajat-masuk satu lebih
besar dari derajat-keluar.

Graf Hamilton
Lintasan dan Sirkuit Hamilton
• Lintasan Hamilton ialah lintasan yang melalui
tiap simpul di dalam graf tepat satu kali.
• Sirkuit Hamilton ialah sirkuit yang melalui tiap
simpul di dalam graf tepat satu kali, kecuali
simpul asal (sekaligus simpul akhir) yang dilalui
dua kali.
• Graf yang memiliki sirkuit Hamilton dinamakan
graf Hamilton, sedangkan graf yang hanya
memiliki lintasan Hamilton disebut graf semi-
Hamilton.

Teorema
• TEOREMA 6.5. Syarat cukup (jadi bukan syarat perlu)
supaya graf sederhana G dengan n (³ 3) buah simpul
adalah graf Hamilton ialah bila derajat tiap simpul paling
sedikit n/2 (yaitu, d(v) ³ n/2 untuk setiap simpul v di G).
• TEOREMA 6.6. Setiap graf lengkap adalah graf
Hamilton.
• TEOREMA 6.7. Di dalam graf lengkap G dengan n buah
simpul (n ³ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.
• TEOREMA 6.8. Di dalam graf lengkap G dengan n buah
simpul (n ³ 3 dan n ganjil), terdapat (n - 1)/2 buah sirkuit
Hamilton yang saling lepas (tidak ada sisi yang
beririsan). Jika n genap dan n ³ 4, maka di dalam G
terdapat (n - 2)/2 buah sirkuit Hamilton yang saling
lepas.

Dasar-dasar Teori Graf

Graf adalah kumpulan simpul (nodes) yang dihubungkan satu sama lain
melalui sisi/busur (edges). Suatu Graf G terdiri dari dua himpunan
yaitu himpunan V dan himpunan E.



Suatu graph G dapat dinyatakan sebagai G = < V,E > . Graph G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada gambar di atas adalah : V = {1,2,3,4,5,6} dan E = {(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}

Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

• Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
• Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path
• Cycle siklus ? path yang kembali melalui titik asal 2 kembali ke 2.
• Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
• Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (v_i,v_j)=(v_j,v_i)
• Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.