Teori Graf: Kasus Khusus dari Graf

1. Graf Lengkap (Complete Graph)

Graf lengkap adalah graf sederhana yang setiap titiknya adjacent dengan semua titik lainnya. Dapat juga dikatakan bahwa graf lengkap adalah graf sederhana yang setiap dua titik berbeda terhubung oleh tepat satu sisi. Graf lengkap dengan n titik disimbolkan dengan Kₙ. Masing-masing titik pada Kₙ berderajat n – 1.

Banyak sisi pada Kₙ adalah C(n, 2) = n(n – 1)/2.

2. Graf Lingkaran atau Graf Siklis (Cycle Graph)

Graf siklis adalah graf sederhana dengan 3 titik atau lebih dan derajat masing-masing titik adalah 2. Graf siklik dengan n titik disimbolkan dengan Cₙ. Banyak sisi pada Cₙ adalah n.

3. Graf Roda (Wheel Graph)

Graf roda diperoleh jika kita menambahkan satu titik pada graf siklis dan menghubungkan titik tambahan tersebut dengan setiap titik pada graf siklis. Graf siklik dengan n + 1 titik disimbolkan dengan Wₙ. Banyak sisi pada Wₙ adalah 2n.

Derajat masing-masing titik dari graf siklik sebelumnya adalah 3, sedangkan derajat titik tambahan adalah n.

4. Graf Teratur (Regular Graph)

Graf teratur adalah graf (tidak harus sederhana) yang semua titik berderajat sama. Dikarenakan semua titik berderajat sama, untuk graf teratur dengan n titik dan derajat r adalah nr. Juga dikarenakan jumlah derajat semua titik selalu genap, mustahil n dan r keduanya ganjil, sehingga n atau r harus ada yang genap.

Mudah dihitung bahwa banyak sisi pada graf teratur dengan n titik dan derajat r adalah nr/2.

5. Graf Hiperkubus (Hypercube Graph)

Hiperkubus berdimensi-n dinyatakan Qₙ adalah graf yang titiknya merepresentasikan 2ⁿ bit string dengan panjang n. Dua titik adjacent jika dan hanya jika bit string yang mereka representasikan berbeda dalam tepat satu posisi bit.

Kita dapat mengkonstruksi Qₙ₊₁ dari Qₙ dengan membuat dua salinan dari Qₙ kemudian menempatkan angka 0 didepan di suatu salinan dan 1 didepan salinan lainnya dan menambahkan sisi yang menghubungkan dua titik yang berbeda dalam tepat satu posisi bit.

6. Graf Lintasan (Path Graph)

Graf lintasan, disimbolkan Pₙ, adalah sebuah graf dengan n titik dimana 2 titik berderajat 1 dan n – 2 titik lainnya berderajat 2.

Graf Lintasan adalah sebuah graf yang dapat digambar sedemikian rupa semua titik dan sisinya terletak dalam satu garis lurus.

7. Graf Bipartit (Bipartite Graph)

A. Graf bipartit umum

Definisi: Suatu graf sederhana G = (V, E) dikatakan bipartit jika himpunan titik V dapat di partisi menjadi dua himpunan yang tidak beririsan V₁ dan V₂ sedemikian sehingga setiap sisi pada graf menghubungkan titik dalam V₁ dengan titik dalam V₂ (demikian sehingga tidak ada sisi pada G yang menghubungkan dua titik dalam V₁ atau dua titik dalam V₂). Jika hal ini dipenuhi kita katakan pasangan (V₁, V₂) suatu bipartisi dari himpunan simpul V.

Sebagai contoh, perhatikan gambar berikut:

misal himpunan V dipartisi menjadi dua V₁ = {a, d, e, g} dan V₂ = {b, c, f}, kita dapat menyajikan graf ini dalam bentuk berikut:

Ini berarti graf ini merupakan graf bipartit.

B. Teorema dua warna

Suatu graf sederhana adalah bipartit jika dan hanya jika mungkin untuk mengaitkan satu dari dua warna yang berbeda pada setiap titik dari graf sedemikian sehingga tidak terdapat dua titik yang bersebelahan dikaitkan dengan warna yang sama.

C. Graf bipartit lengkap (complete bipartite graph)

Graf bipartit lengkap; disimbolkan Kₘ,ₙ; adalah suatu graf yang memiliki himpunan titik yang dipartisi menjadi dua himpunan bagian dengan m dan n titik sedemikian sehingga terdapat sisi yang menghubungkan setiap pasangan titik dari kedua himpunan bagian.

Banyak sisi dari graf bipartit lengkap adalah mn, sehingga untuk graf bipartit secara umum berlaku ketaksamaan |E| ≤ |V₁|·|V₂|.

D. Graf bintang (star graph)

Graf Bintang atau Star Graph adalah Graph bipartisi komplit K₁,ₙ atau Kₙ,₁. Graf Bintang dengan n + 1 titik sering disimbolkan dengan Sₙ.

E. Ketaksamaan titik-sisi

"Jika G graf bipartit dengan n titik dan m sisi, maka m ≤ ¼n²".

Bukti:

Diberikan G = (V, E) graf bipartit dengan |E| = m dan |V| = n.

Kita dapat mempartisi V menjadi V₁ dan V₂, misal |V₁| = p dan |V₂| = q, berlaku hubungan n = p + q.

Ingat kembali bahwa |E| ≤ |V₁|·|V₂| ⇔ m ≤ pq.

Dikarenakan bilangan kuadrat tidak mungkin negatif, berlaku ketaksamaan

0 ≤ (p – q)² = p² + q² – 2pq, tambahkan masing-masing ruas dengan 4pq

4pq ≤ p² + q² + 2pq = (p + q)² = n², bagi masing-masing ruas dengan 4

pq ≤ ¼n²

Dikarenakan m ≤ pq dan pq ≤ ¼n², menurut sifat transitif berlaku m ≤ ¼n².

F. Sikel genap

"Panjang setiap sikel (jika ada) di graf bipartit selalu genap."

Hal ini benar karena misal graf G = (V, E) memiliki sikel dan titik-titik pada sikel diberi nomor, pastilah titik terakhir terhubung dengan titik pertama. Lalu titik-titik ganjil dimasukkan ke V₁ dan titik-titik genap dimasukkan ke V₂, agar titik terakhir yang terhubung dengan titik pertama berbeda partisi, diharuskan bernomor genap, sehingga panjang sikelnya genap.

Dengan keberadaan sikel ganjil pada graf, bisa dipastikan graf tersebut bukan graf bipartit.