Teori graf

Abstract

Buku ini disusun untuk memenuhi kebutuhan bahan ajar mata kuliah Teori Graf di perguruan tinggi. Materi disajikan secara bertahap, dimulai dari pengenalan sejarah hingga penerapan algoritma pada kasus nyata. Penyusunan buku ini didasarkan pada pengalaman mengajar penulis selama beberapa tahun, dengan memperhatikan kesulitan-kesulitan yang umum dihadapi mahasiswa.

Bab pertama memaparkan sejarah dan perkembangan teori graf. Pemaparan sejarah tidak dimaksudkan sebagai materi tambahan yang bersifat ornamentik. Sejarah memperlihatkan akar masalah yang melatarbelakangi lahirnya konsep-konsep dasar, seperti yang ditunjukkan oleh Euler dalam menyelesaikan masalah jembatan Königsberg pada tahun 1736.

Bab kedua membahas konsep dasar. Bab ini mencakup definisi graf, terminologi dasar, operasi-operasi pada graf, representasi graf, dan isomorfisme graf. Penguasaan bab ini menjadi prasyarat mutlak untuk memahami bab-bab selanjutnya. Setiap istilah didefinisikan secara eksplisit dan dilengkapi dengan contoh.

Bab ketiga menyajikan klasifikasi graf berdasarkan beberapa kriteria: aturan busur, arah busur, bentuk atau struktur, dan sifat khusus. Klasifikasi ini penting karena setiap jenis graf memiliki karakteristik yang mempengaruhi pilihan algoritma yang akan digunakan.

Bab keempat membahas pewarnaan graf dan pelabelan graf. Kedua topik ini sering dikacaukan oleh mahasiswa. Pewarnaan graf berkaitan dengan pemberian warna pada simpul atau sisi dengan syarat simpul atau sisi yang bertetangga tidak memiliki warna yang sama. Pelabelan graf berkaitan dengan pemetaan simpul atau sisi ke bilangan bulat positif dengan pola tertentu. Bab ini menempatkan kedua topik secara berdampingan untuk memperjelas perbedaan keduanya.

Bab kelima berisi algoritma dasar dalam teori graf: pencarian lintasan, pencarian jalur terpendek, dan pencarian pohon merentang minimum. Algoritma yang dibahas meliputi algoritma Dijkstra, algoritma Bellman-Ford, algoritma Prim, dan algoritma Kruskal. Setiap algoritma disajikan dengan langkah-langkah prosedural dan analisis kompleksitas waktu.

Bab keenam membahas aplikasi teori graf pada tiga bidang: jaringan komputer, transportasi dan rute, serta penjadwalan sederhana. Pemilihan ketiga bidang ini didasarkan pada frekuensi kemunculannya dalam persoalan yang dihadapi mahasiswa di lapangan kerja.

Setiap bab dilengkapi dengan tujuan pembelajaran di bagian awal dan soal latihan di bagian akhir. Tujuan pembelajaran dirumuskan dalam bentuk perilaku yang terukur. Soal latihan disusun secara bertingkat, mulai dari tingkat pemahaman konsep hingga tingkat penerapan.

ISBN: 978-634-262-313-8