Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Pratinjau cetak

Ukuran kertas

Lembar Kerja Aktivitas Pratinjau

Untuk memahami graf dan jenis pertanyaan yang ingin kita ajukan mengenainya, mari kita pelajari empat contoh graf.
🔗
\(G_1\text{:}\)
🔗
\(G_2\text{:}\)
🔗
Graf Petersen: sepuluh simpul yang masing-masing memiliki tiga sisi. Lima simpul membentuk bintang bersudut lima, lima lainnya membentuk segilima, dengan sisi-sisi yang menghubungkan simpul-simpul bintang dan segilima.
Sebuah graf dengan enam simpul yang tersusun dalam dua baris, masing-masing berisi tiga simpul. Simpul-simpul atas diberi label v1, v2, v3 dari kiri ke kanan. Simpul-simpul bawah diberi label v6, v5, v4 dari kiri ke kanan. Tiga sisi menghubungkan setiap simpul pada baris atas dengan simpul di bawahnya. Empat sisi lainnya menghubungkan simpul-simpul pada baris atas dan baris bawah dalam dua konfigurasi berbentuk X.
\(G_3\text{:}\)
🔗
\(G_4\text{:}\)
🔗
simpul bertetangga dengan
\(a\) \(b, c\)
\(b\) \(a,f\)
\(c\) \(a, d, e\)
\(d\) \(c,e,f\)
\(e\) \(c,d\)
\(f\) \(b,d\)
\begin{equation*} \begin{pmatrix} 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \\ 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \end{pmatrix} \end{equation*}
🔗
Graf \(G_3\) disajikan sebagai daftar ketetanggaan, yaitu setiap simpul diberi daftar simpul-simpul lain yang bertetangga dengannya. Graf \(G_4\) disajikan sebagai matriks ketetanggaan, yaitu baris dan kolom berpadanan dengan simpul-simpul, dan entrinya bernilai 1 jika kedua simpul bertetangga dan 0 jika tidak. Sebelum menjawab pertanyaan-pertanyaan di bawah, mungkin akan membantu jika Anda menggambar representasi yang lebih lazim dari graf-graf ini.
🔗
1.
Pertama, mari kita hitung banyaknya simpul dan sisi pada setiap graf.
🔗
Banyaknya simpul: \(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
🔗
Banyaknya sisi: \(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
🔗
🔗
2.
Banyaknya sisi yang bersisian dengan suatu simpul tertentu (yaitu, banyaknya sisi yang “keluar dari” simpul tersebut) disebut derajat simpul itu. Daftar derajat semua simpul dalam urutan tak-menaik disebut barisan derajat graf. Tentukan barisan derajat untuk setiap graf.
🔗
\(G_1\) memiliki barisan derajat: .
🔗
\(G_2\) memiliki barisan derajat: .
🔗
\(G_3\) memiliki barisan derajat: .
🔗
\(G_4\) memiliki barisan derajat: .
🔗
🔗
3.
Kita sering memperhatikan lintasan di antara simpul-simpul dalam graf. Suatu graf disebut terhubung jika terdapat lintasan di antara setiap pasangan simpul. Kadang-kadang terdapat lintasan yang berawal di suatu simpul dan akhirnya kembali ke simpul itu sendiri; lintasan demikian disebut siklus.
🔗
(c)
Graf yang terhubung dan tidak memuat siklus disebut pohon. Untuk setiap graf, berapa banyak sisi yang harus dihapus agar graf tersebut menjadi pohon? (Jika graf itu sudah merupakan pohon, jawabannya adalah 0.)
🔗
\(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
🔗
🔗
🔗
4.
Graf mana saja yang dapat digambar sedemikian rupa sehingga tidak ada sisi yang berpotongan?
🔗
🔗
🔗
5.
Misalkan setiap simpul suatu graf kita warnai sedemikian rupa sehingga simpul-simpul yang bertetangga selalu memiliki warna berbeda. Banyaknya warna paling sedikit yang diperlukan disebut bilangan kromatik graf tersebut. Tentukan bilangan kromatik untuk setiap graf.
🔗
\(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
🔗
Catatan: Jika graf-graf tersebut merepresentasikan hubungan pertemanan antarorang, bilangan kromatik akan memberi tahu kita banyaknya kelompok minimum yang diperlukan apabila kita ingin membagi semua orang ke dalam kelompok-kelompok yang anggotanya belum saling berteman.
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik