Sebuah graf \(G\) terdiri atas suatu himpunan simpul \(V\) dan suatu koleksi \(E\) yang terdiri atas himpunan-himpunan bagian berukuran \(2\) dari \(V\text{.}\) Unsur-unsur \(E\) disebut sisi. Dalam mata kuliah ini, kita akan (hampir selalu) menggunakan konvensi bahwa \(V=\{1,2,3,\dots,n\}\) untuk suatu bilangan bulat positif \(n\text{.}\) Dengan konvensi ini, graf dapat dideskripsikan secara tepat menggunakan sebuah berkas teks:
Baris pertama berkas memuat satu bilangan bulat \(n\text{,}\) yaitu banyaknya simpul dalam graf.
Diagram graf dengan sembilan simpul yang sesuai dengan berkas data di sebelahnya. Graf memiliki dua komponen: simpul 2, 6, dan 8 berada pada satu komponen, sedangkan enam simpul lainnya berada pada komponen yang lain.
Sebagian besar notasi dan terminologi graf cukup alami. Cobalah menafsirkan pernyataan-pernyataan berikut yang berlaku untuk graf \(G\) yang didefinisikan di atas:
Misalkan kita memberikan kepada kelas sebuah berkas data teks untuk graf dengan \(1500\) simpul dan menanyakan apakah graf tersebut memuat siklus dengan panjang sekurang-kurangnya \(500\text{.}\) Raoul menjawab ya dan Carla menjawab tidak. Bagaimana kita menentukan siapa yang benar?
Sebagai gantinya, misalkan kita menanyakan apakah graf tersebut memiliki klik berukuran \(500\text{.}\) Helene mengatakan bahwa menurutnya tidak, tetapi ia tidak yakin. Wajarkah jika teman-teman sekelasnya mendesak agar ia mengambil keputusan, ya atau tidak? Apakah menentukan bahwa graf ini memiliki klik berukuran \(500\) lebih sulit, lebih mudah, atau kurang lebih sama dengan menentukan bahwa graf tersebut memiliki siklus dengan panjang \(500\text{?}\)
Dalam Gambar 1.6, kami menunjukkan lokasi sejumlah stasiun radio pada bidang beserta skala yang menunjukkan jarak \(200\) mil. Stasiun radio yang terpisah kurang dari \(200\) mil harus memancar pada frekuensi berbeda untuk menghindari gangguan.
Diagram lokasi sejumlah stasiun radio pada bidang. Setiap stasiun ditandai dengan sebuah titik dan angka frekuensi 1 sampai 6; sebuah garis skala menunjukkan jarak 200 mil.
Dapatkah Anda menemukan \(4\) stasiun yang masing-masing berjarak kurang dari \(200\) mil dari \(3\) stasiun lainnya? Dapatkah Anda menemukan \(8\) stasiun yang masing-masing berjarak lebih dari \(200\) mil dari \(7\) stasiun lainnya? Adakah cara alami untuk mendefinisikan graf yang berkaitan dengan masalah ini?
Berapa banyak mahasiswa yang harus ada dalam suatu kelas kombinatorika terapan agar terdapat (a) enam mahasiswa yang setiap pasangnya pernah bersama-sama mengikuti sekurang-kurangnya satu mata kuliah lain, atau (b) enam mahasiswa yang setiap pasangnya baru pertama kali berada dalam satu kelas bersama? Apakah ini benar-benar masalah yang sulit, atau dapatkah kita menyelesaikannya hanya dalam beberapa menit sambil mencoret-coret serbet?
