Matematika Diskrit - Lebih Lanjut Tentang Grafik
Pewarnaan Grafik
Pewarnaan graf adalah prosedur pemberian warna pada setiap simpul pada graf G sehingga tidak ada simpul yang berdekatan yang memiliki warna yang sama. Tujuannya adalah meminimalkan jumlah warna saat mewarnai grafik. Jumlah warna terkecil yang diperlukan untuk mewarnai grafik G disebut dengan bilangan kromatik grafik tersebut. Masalah pewarnaan graf adalah masalah NP Lengkap.
Metode Mewarnai Grafik
Langkah-langkah yang diperlukan untuk mewarnai graf G dengan n jumlah simpul adalah sebagai berikut -
Step 1 - Atur simpul dari grafik dalam beberapa urutan.
Step 2 - Pilih simpul pertama dan warnai dengan warna pertama.
Step 3- Pilih simpul berikutnya dan warnai dengan warna bernomor terendah yang belum diwarnai pada sembarang simpul yang berdekatan dengannya. Jika semua simpul yang berdekatan diwarnai dengan warna ini, berikan warna baru padanya. Ulangi langkah ini sampai semua simpul diwarnai.
Example
Pada gambar di atas, pada simpul pertama $ a $ diwarnai merah. Karena simpul-simpul yang berdekatan dari simpul a kembali berdekatan, simpul $ b $ dan simpul $ d $ diwarnai dengan warna yang berbeda, hijau dan biru masing-masing. Kemudian simpul $ c $ diwarnai merah karena tidak ada simpul yang berdekatan dari $ c $ yang diwarnai merah. Karenanya, kita bisa mewarnai grafik dengan 3 warna. Oleh karena itu, bilangan kromatik grafiknya adalah 3.
Aplikasi Pewarnaan Grafik
Beberapa aplikasi pewarnaan grafik meliputi -
- Daftar Alokasi
- Pewarnaan Peta
- Pemeriksaan Graf Bipartit
- Penetapan Frekuensi Radio Seluler
- Membuat tabel waktu, dll.
Grafik Traversal
Traversal graf adalah masalah mengunjungi semua simpul dari sebuah graf dalam beberapa urutan sistematis. Ada dua cara utama untuk melintasi grafik.
- Breadth First Search
- Penelusuran Pertama Kedalaman
Breadth First Search
Breadth First Search (BFS) dimulai dari memulai level-0 simpul $ X $ dari grafik $ G $. Kemudian kita mengunjungi semua simpul yang merupakan tetangga dari $ X $. Setelah mengunjungi, kami menandai simpul sebagai "dikunjungi", dan menempatkannya ke tingkat-1. Kemudian kita mulai dari simpul level-1 dan menerapkan metode yang sama pada setiap simpul level-1 dan seterusnya. BFS traversal berakhir ketika setiap simpul dari grafik telah dikunjungi.
BFS Algorithm
Konsepnya adalah mengunjungi semua simpul tetangga sebelum mengunjungi simpul tetangga lainnya dari simpul tetangga.
Inisialisasi status semua node sebagai "Siap".
Letakkan simpul sumber dalam antrian dan ubah statusnya menjadi "Menunggu".
Ulangi dua langkah berikut sampai antrian kosong -
Hapus simpul pertama dari antrian dan tandai sebagai "Dikunjungi".
Tambahkan ke belakang antrian semua tetangga dari simpul yang dihapus yang statusnya “Siap”. Tandai status mereka sebagai "Menunggu".
Problem
Mari kita ambil sebuah grafik (Simpul sumber adalah 'a') dan terapkan algoritma BFS untuk mengetahui urutan traversal.
Solution -
Inisialisasi status semua simpul ke "Siap".
Masukan yang dalam antrian dan mengubah statusnya menjadi “Waiting”.
Hapus sebuah dari antrian, menandainya sebagai “Dikunjungi”.
Menambahkan sebuah ‘s tetangga di‘Siap’negara b, d dan e untuk mengakhiri antrian dan menandai mereka sebagai‘Waiting’.
Hapus b dari antrian, tandai sebagai "Dikunjungi", letakkan "Siap" di sebelah c di akhir antrian dan tandai c sebagai "Menunggu".
Hapus d dari antrian dan tandai sebagai "Dikunjungi". Tidak ada tetangga dalam kondisi "Siap".
Hapus e dari antrian dan tandai sebagai "Dikunjungi". Tidak ada tetangga dalam kondisi "Siap".
Hapus c dari antrian dan tandai sebagai "Dikunjungi". Tidak ada tetangga dalam keadaan "Siap".
Antrian kosong jadi berhentilah.
Jadi urutan traversal adalah -
$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $
Urutan alternatif traversal adalah -
$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $
Atau, $ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $
Atau, $ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $
Atau, $ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $
Atau, $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $
Application of BFS
- Menemukan jalur terpendek
- Pohon rentang minimum untuk grafik tanpa bobot
- Sistem navigasi GPS
- Mendeteksi siklus dalam grafik yang tidak diarahkan
- Menemukan semua node dalam satu komponen yang terhubung
Complexity Analysis
Misalkan $ G (V, E) $ menjadi grafik dengan $ | V | $ jumlah simpul dan $ | E | $ jumlah sisi. Jika algoritme penelusuran pertama yang luas mengunjungi setiap titik dalam grafik dan memeriksa setiap tepi, kompleksitas waktunya adalah -
$$ O (| V | + | E |). O (| E |) $$
Ini dapat bervariasi antara $ O (1) $ dan $ O (| V2 |) $
Penelusuran Pertama Kedalaman
Algoritma Depth First Search (DFS) dimulai dari simpul $ v $, kemudian melintasi ke simpul yang berdekatan (katakanlah x) yang belum pernah dikunjungi sebelumnya dan tandai sebagai "dikunjungi" dan melanjutkan dengan simpul yang berdekatan $ x $ dan begitu seterusnya.
Jika pada sembarang simpul, ia menemukan bahwa semua simpul yang berdekatan dikunjungi, lalu ia melakukan backtrack sampai ia menemukan simpul pertama yang memiliki simpul bersebelahan yang belum pernah dilintasi sebelumnya. Kemudian, ia melintasi simpul itu, berlanjut dengan simpul yang berdekatan sampai ia melintasi semua simpul yang dikunjungi dan harus mundur lagi. Dengan cara ini, ia akan melintasi semua simpul yang bisa dijangkau dari simpul awal $ v $.
DFS Algorithm
Konsepnya adalah mengunjungi semua simpul tetangga dari simpul tetangga sebelum mengunjungi simpul tetangga lainnya.
Inisialisasi status semua node sebagai "Siap"
Letakkan simpul sumber dalam tumpukan dan ubah statusnya menjadi "Menunggu"
Ulangi dua langkah berikut sampai tumpukan kosong -
Pop verteks atas dari tumpukan dan tandai sebagai "Dikunjungi"
Dorong ke atas tumpukan semua tetangga dari simpul yang dihapus yang statusnya “Siap”. Tandai status mereka sebagai "Menunggu".
Problem
Mari kita ambil sebuah grafik (Simpul sumber adalah 'a') dan terapkan algoritma DFS untuk mengetahui urutan traversal.
Solution
Inisialisasi status semua simpul ke "Siap".
Mendorong sebuah di stack dan mengubah statusnya menjadi “Waiting”.
Pop a dan menandainya sebagai “Dikunjungi”.
Mendorong sebuah tetangga ‘s di‘Siap’negara e, d dan b ke atas tumpukan dan menandai mereka sebagai‘Waiting’.
Pop b dari tumpukan, tandai sebagai "Dikunjungi", dorong tetangga "Siap" c ke tumpukan.
Pop c dari tumpukan dan tandai sebagai "Dikunjungi". Tidak ada tetangga yang "Siap".
Pop d dari tumpukan dan tandai sebagai "Dikunjungi". Tidak ada tetangga yang "Siap".
Pop e dari tumpukan dan tandai sebagai "Dikunjungi". Tidak ada tetangga yang "Siap".
Tumpukan kosong. Jadi berhentilah.
Jadi urutan traversal adalah -
$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $
Urutan alternatif traversal adalah -
$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $
Atau, $ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $
Atau, $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $
Atau, $ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $
Atau, $ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $
Complexity Analysis
Misalkan $ G (V, E) $ menjadi grafik dengan $ | V | $ jumlah simpul dan $ | E | $ jumlah sisi. Jika algoritma DFS mengunjungi setiap simpul dalam grafik dan memeriksa setiap sisi, maka kompleksitas waktunya adalah -
$$ \ circleddash (| V | + | E |) $$
Applications
- Mendeteksi siklus dalam grafik
- Untuk menemukan pengurutan topologi
- Untuk menguji apakah suatu graf adalah bipartit
- Menemukan komponen yang terhubung
- Menemukan jembatan grafik
- Menemukan konektivitas ganda dalam grafik
- Memecahkan masalah Tur Ksatria
- Memecahkan teka-teki hanya dengan satu solusi