Hai hai semua

. Ketemu lagi sama aye, Admin K yang berkuasa lagi tangkas

. Tentu saja, masih di blog kesayangan kita yang lain dari yang lain ini, KnK Land. Kali ini aye akan membahas salah satu bidang matematika yang bisa dikatakan masih lumayan muda tapi masih lebih tua dari aye. Di postigan ini, aye akan sedikit membahas tentang teori graf. Nah, aye disini bakal membagikan macam-macam graf. Baiklah, daripada lama-lami, mending kita langsung saja cekidoot

.

Sebelum membaca postingan ini, alangkah baiknya kita harus fokus terlebih dahulu. Kurangi semua kesibukan, matikan tv, duduk manis, dan langsung saja mata dipandangkan di layar hape/laptop/device apapun yang kalian gunakan untuk membaca postingan ini. Jangan lupa juga pasang obat nyamuk atau kelambu agar tidak mengganggu proses pembacaan teks postingan ini. Baiklah mari kita mulai postingan utamanya.

Sebelum masuk ke macam-macam graf. Alangkah baiknya, kalian harus tau apa itu graf. Hmm, itu graf? Sebenarnya aye gak bakal ngebahas pengertian graf disini. Pengertian graf bakal aye posting di postingan yang lain. Sedikit menngingatkan atau memberitahu kalau graf didefinisikan sebagai pasangan 2 buah himpunan yakni himpunan titik dan himpunan sisi. Himpunan titik bisa himpunan apa saja asalkan tidak kosang. Adapun, himpunan sisi itu sendiri adalah suatu subhimpunan dari himpunan pasangan tak berurutan dari titik-titik berbeda di himpunan titik graf tersebut (himpunan sisi bisa kosong). Selanjutnya, graf juga bisa digambar.

Sebagai contoh kita punya graf G = (V, E) dengan V adalah himpunan titikdan E adalah himpunan sisi. Misalkan saja V = {a, b, c, d, e, f, g} dan E = {{e,b}, {f,a}, {a,e}, {b, f}} (Bisa juga ditulis E = {eb, fa, ae, bf}). Nah, selanjutnya, graf ini bisa digambar dalam bentuk titik dan garis. Titik-titik pada gambar menyatakan elemen-elemen di V, sedangkan sisi-sisi pada gambar menghubungkan antara dua titik yang berpasangan di E. Berikut gambarnya guys.

Ya, seperti itulah kira-kira gambar grafnya. Perlu diperhatikan bahwa tidak perlu terlalu kaku dalam menggambar graf. Yang terpenting adalah adanya titik serta sisi-sisinya yang menghubungkan. Gambar sisinya itu sendiri gak harus lurus, bisa juga melengkung asalkan ujungnya langsung "tertancap" pada titik. Bentuknya pun tidak perlu diatur-atur. Yang terpenting dari graf bukan bentuknya tapi bagaimana graf menggambarkan hubungan antara titik/objek.

Dan selanjutnya, dan selanjutnya, blablabla, hanya sedikit review tentang pengertian graf. Adapun untuk yang lain-lain misalnya konsep ketetanggaan, tolong kalian pelajari sendiri. Baiklah, mari kita langsung saja masuk ke main dish-nya.

Oh yah, definisi graf yang aye pake disini adalah graf sederhana. Jadi, yang dimaksud graf disini adalah graf sederhana sehingga tidak ada yang namanya sisi paralel (2 sisi yang mengaitkan pasangan titik yang sama) atau loop (titik yang bertetangga dengan dirinya sendiri)

1. Graf Lengkap

Graf lengkap adalah graf yang setiap 2 titiknya saling bertetangga. Graf lengkap yang mempunyai bayak titik n dinotasikan dengan Kn. Dinamakan graf lengkap karena udah lengkap sisi-sisinya, semua titik saling terhubung satu sama lain. Berikut contohnya yakni graf K1, K2, K3, dan K4.

2. Graf Trivial

Graf trivial adalah graf yang hanya mempunyai 1 titik. Karena hanya mempuyai 1 titik, maka graf ini tidak mempunyai sisi. Disebut graf trivial yah karena emang trivial, gak menarik, hanya sepele. Liat aja tuh si graf K1 hanya titik doang, itulah yang dinamakan graf trivial.

3. Graf Nol (Null)

Graf nol adalah graf yang tidak mempunyai sisi. Dengan kata lain himpunan sisinya kosong. Contohnya saja graf G berikut mempunyai 6 titik tapi tidak mempunyai sisi.

4. Graf Lintasan (Path)

Jika suatu graf mempunyai titik yang dilabeli v1,v2,...,vn sehingga semua sisinya adalah v1v2,v2v3,...,vn-1vn maka graf tersebut disebut graf lintasan (path). Graf lintasan berorde n dilambangkan dengan Pn. Dengan demikian, graf lintasan adalah graf yang terdiri dari barisan titik yang saling terhubung membentuk lintasan yang mempunyai 2 titik ujung.

5. Graf Lingkaran/Siklus (Cycle)

Graf Siklus adalah graf terhubung yang setiap titiknya berderajat 2. Jika suatu graf mempunyai titik yang dilabeli v1,v2,...,vn sehingga semua sisinya adalah v1v2,v2v3,...,vn-1vn, serta v1vn maka graf tersebut disebut graf siklus (cycle). Graf siklus dapat dibuat dengan menambah sisi pada graf lintasan berorde 3 atau lebih dengan menghubungkan kedua titik ujung. Graf siklus berorde n dinotasikan dengan Cn. Orde suatu graf siklus tidak boleh lebih kecil dari 3 karena tidak mungkin membuat graf siklus hanya dengan 1 atau 2 titik (jika kita menghubungkan titik ujung dari P1 maka akan terbentuk loop dan jika kita menghubungkan titik ujung dari P2 maka akan terbentuk sisi paralel).

6. Graf Pohon (Tree)

Graf pohon adalah graf terhubung (untuk setiap dua titik, terdapat lintasan dalam graf yang memuat kedua titik tersebut) yang tidak memuat graf siklus/sirkuit (cycle) atau dengan kata lain tidak mungkin terbentuk graf siklus apabila beberapa titik dan/atau beberapa sisi dihilangkan. Disebut graf pohon ya karena bentuknya bisa diimajinasikan seperti pohon yang bercabang-cabang.Contoh-contoh graf pohon adalah graf G1, G2, G3, dan G4.

Oh yah, perhatikan bahwa semua graf lengkap kecuali K1 dan K2 bukanlah graf pohon. Selain itu, semua graf lintasana adalah graf pohon. Adapun graf siklus jelas bukanlah graf pohon karena dirinya sendiri memang adalah siklus.

7. Graf Bipartit

Graf bipartit adalah graf yang himpunan titiknya dapat dipartisi (dibagi) menjadi dua himpunan sedemikian sehingga tidak ada 2 titik yang ada di himpunan (hasil partisi) yang sama saling bertetangga. Graf G5, G6, G7, dan G8 adalah contoh-contoh graf bipartit. Warna dari titik menunjukkan himpunan suatu titik berada setelah dipartisi, misal titik-titik merah di himpunan A dan titik-titik biru di himpunan B. Titik yang berwarna sama (di himpunan yang sama) tidak boleh saling bertetangga agar graf tersebut masuk dalam jenis graf bipartit.

8. Graf Bipartit Lengkap

Graf bipartit lengkap adalah graf bipartit tapi bukan graf bipartit secara umum. Kalau graf bipartit secara umum, himpunan titiknya terpartisi menjadi 2 himpunan misalnya saja A dan B sehingga setiap 2 titik di A tidak bertetangga serta setiap 2 titik di B juga tidak bertetangga. Nah, agar graf bipartit disebut graf bipartit lengkap, maka setiap titik di himpunan A harus bertetangga dengan setiap titik di himpunan B.Graf bipartit lengkap dinotasikan dengan Kn,m dengan n adalah banyaknya titik di himpunan A dan m adalah banyaknya titik di himpunan B. Contoh graf bipartit lengkap adalah graf K4,2, K8,5, dan K5,4.

Nah, itulah berbagai macam graf. Sebenarnya masih banyak lagi macam atau nama-nama graf tertentu yang diberikan oleh matematikawan atau ahli teori graf. Kalian juga bisa membuat macam graf sendiri kalau memang ada graf yang bentuknya menarik.

Baiklah cukup sekian postingan aye kali ini. Kalau ada tanggapan, protes, atau pertaanyaan, silakan sampaikan semuanya di kolom komentar di bawah ini. Sampai jumpa di postingan selanjutnya. Bye~