Masalah dan Definisi

Subbab 2.1 Masalah dan Definisi

Tujuan Pembelajaran

Setelah menyelesaikan bagian ini, Anda diharapkan mampu melakukan hal-hal berikut.

Menggunakan bahasa teori graf untuk mendeskripsikan sifat-sifat graf.
🔗

🔗
Menggunakan berbagai representasi graf.
🔗

🔗
Menerapkan Lema Jabat Tangan untuk menjawab pertanyaan tentang graf dan masalah yang direpresentasikannya.
🔗

🔗

Subbagian Pratinjau Bagian

Selidiki!

Pada masa Euler, di kota Königsberg, Prusia, terdapat sebuah sungai dengan dua pulau. Pulau-pulau tersebut terhubung dengan tepian sungai melalui tujuh jembatan (seperti terlihat di bawah). Jembatan-jembatan itu sangat indah, dan pada hari libur, warga kota menghabiskan waktu dengan berjalan melintasinya. Seiring berjalannya waktu, muncul sebuah pertanyaan: Dapatkah direncanakan suatu perjalanan yang melintasi setiap jembatan tepat satu kali? Euler berhasil menjawab pertanyaan ini. Dapatkah Anda?

🔗

$Gambar sebuah sungai (berwarna biru) yang mengalir dari kiri ke kanan dengan dua pulau. Terdapat 7 jembatan di atas sungai: dua dari tepi atas ke pulau kiri, dua dari pulau kiri ke tepi bawah, serta satu jembatan dari pulau kanan ke masing-masing tepi atas, tepi bawah, dan pulau kiri.$

🔗

Teori graf merupakan bidang matematika yang relatif baru, yang pertama kali dipelajari oleh matematikawan sangat terkenal Leonhard Euler pada tahun 1735. Sejak saat itu, teori graf berkembang menjadi alat yang ampuh dan digunakan di hampir setiap cabang ilmu pengetahuan, serta kini menjadi bidang penelitian matematika yang aktif.

🔗

Masalah di atas, yang dikenal sebagai Tujuh Jembatan Königsberg, merupakan masalah yang mula-mula mengilhami teori graf. Perhatikan suatu masalah yang “berbeda”: Di bawah ini terdapat gambar empat titik yang dihubungkan oleh beberapa garis. Dapatkah setiap garis ditelusuri tepat satu kali (tanpa mengangkat pensil, dengan mulai dan berakhir pada sebuah titik)?

🔗

$Tiga titik tersusun vertikal di sebelah kiri sebuah titik tunggal di kanan. Garis-garis menghubungkan titik di kanan dengan setiap titik di kiri. Di antara titik-titik di kiri, dua garis lengkung menghubungkan titik bawah dengan titik tengah, dan dua garis lengkung lainnya menghubungkan titik tengah dengan titik atas.$

Terdapat hubungan yang jelas antara kedua masalah ini. Setiap lintasan pada gambar titik dan garis berpadanan tepat dengan suatu lintasan melalui jembatan-jembatan Königsberg.

🔗

Gambar seperti gambar titik dan garis ini disebut graf (meskipun secara teknis, gambar di atas adalah sebuah multigraf). Graf tersusun atas sekumpulan titik yang disebut simpul dan garis yang menghubungkan titik-titik tersebut, yang disebut sisi. Ketika dua simpul dihubungkan oleh sebuah sisi, kita mengatakan bahwa keduanya bertetangga. Keuntungan mengamati graf alih-alih gambar sungai, pulau, dan jembatan adalah bahwa sekarang kita memiliki objek matematis untuk dipelajari. Kita telah menyaring bagian-bagian yang “penting” dari gambar jembatan bagi masalah tersebut. Tidak menjadi persoalan seberapa besar pulau-pulaunya, dari bahan apa jembatan-jembatannya dibuat, apakah sungainya berisi buaya, dan sebagainya. Yang penting hanyalah daratan mana yang terhubung dengan daratan lainnya, dan berapa kali. Inilah wawasan penting Euler.

🔗

Kita akan kembali membahas pencarian lintasan dalam graf pada Subbab 2.4. Pada bagian ini, kita akan mengeksplorasi berbagai cara graf dapat digunakan untuk merepresentasikan, atau memodelkan, masalah dunia nyata. Dalam prosesnya, kita akan memperkenalkan beberapa definisi, istilah, dan notasi dasar yang akan digunakan pada bagian-bagian selanjutnya dalam bab ini.

🔗

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.

🔗

(a)

Graf mana saja yang terhubung?

🔗

$\displaystyle G_1$
🔗

🔗
$\displaystyle G_2$
🔗

🔗
$\displaystyle G_3$
🔗

🔗
$\displaystyle G_4$
🔗

🔗
Tidak satu pun di atas
🔗

🔗

🔗

(b)

Graf mana saja yang memuat siklus?

🔗

$\displaystyle G_1$
🔗

🔗
$\displaystyle G_2$
🔗

🔗
$\displaystyle G_3$
🔗

🔗
$\displaystyle G_4$
🔗

🔗
Tidak satu pun di atas
🔗

🔗

🔗

(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?

🔗

$\displaystyle G_4$
🔗

🔗
$\displaystyle G_1$
🔗

🔗
$\displaystyle G_3$
🔗

🔗
$\displaystyle G_2$
🔗

🔗
Tidak satu pun di atas
🔗

🔗

🔗

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.

🔗

Subbagian Apa Itu Graf?

Sebelum mulai mempelajari graf, kita perlu menyepakati apa yang dimaksud dengan graf. Meskipun kita hampir selalu membayangkan graf sebagai gambar (titik-titik yang dihubungkan oleh garis), gambaran ini cukup ambigu. Haruskah garis-garisnya lurus? Apakah panjang garis atau besar titik berpengaruh? Dapatkah ada dua garis yang menghubungkan pasangan titik yang sama? Dapatkah satu garis menghubungkan tiga titik?

🔗

Cara kita menghindari ambiguitas dalam matematika adalah dengan memberikan definisi yang konkret dan cermat. Merumuskan definisi yang baik tidaklah mudah, tetapi sangat penting. Definisi merupakan titik awal yang disepakati dan menjadi landasan bagi semua kebenaran dalam matematika. Adakah graf tanpa sisi? Kita harus melihat definisinya untuk mengetahui apakah hal ini mungkin.

🔗

Kita menginginkan definisi yang tepat dan tidak ambigu, tetapi definisi itu juga harus selaras dengan intuisi kita tentang objek yang dipelajari. Definisi tersebut harus berguna: Kita dapat saja mendefinisikan graf sebagai mamalia berkaki enam, tetapi definisi itu tidak akan membantu kita menyelesaikan masalah tentang jembatan. Sebagai gantinya, berikut adalah definisi graf yang kini menjadi standar.

🔗

Definisi 2.1.1. Graf.

Sebuah graf adalah pasangan terurut $G = (V, E)$ yang terdiri atas himpunan tak kosong $V$ (disebut himpunan simpul) dan himpunan $E$ (disebut himpunan sisi) yang anggotanya merupakan subhimpunan dua unsur dari $V\text{.}$

🔗

Aneh. Definisi tersebut sama sekali tidak menyebut titik atau garis. Berdasarkan definisi itu, sebuah graf dapat berupa

\begin{equation*} (\{a,b,c,d\}, \{\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}\})\text{.} \end{equation*}

Di sini kita memiliki graf dengan empat simpul (huruf-huruf $a, b, c, d$) dan lima sisi (pasangan-pasangan $\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\})$).

🔗

Mengamati himpunan dan himpunan yang beranggotakan himpunan dua unsur sulit dipahami. Karena itu, kita sering menggambar representasi himpunan-himpunan tersebut. Kita menempatkan satu titik untuk setiap simpul dan menghubungkan dua titik dengan garis tepat ketika kedua simpul itu merupakan salah satu subhimpunan dua unsur dalam himpunan sisi kita. Jadi, salah satu cara menggambar graf yang dideskripsikan di atas adalah sebagai berikut:

🔗

$Empat simpul tersusun membentuk persegi, dengan sisi-sisi pada batas persegi dan satu sisi yang menghubungkan simpul kiri bawah dengan simpul kanan atas. Simpul-simpul diberi label a (kiri atas), b (kanan atas), c (kiri bawah), dan d (kanan bawah).$

Namun, kita juga dapat menggambar graf tersebut dengan cara berbeda. Misalnya, salah satu dari dua gambar berikut:

🔗

$Empat simpul tersusun membentuk persegi. Simpul-simpul diberi label a (kiri atas), d (kanan atas), c (kiri bawah), dan b (kanan bawah). Sisi-sisi menghubungkan a dengan c dan b, d dengan b dan c, serta c dengan b.$

$Empat simpul tersusun dalam satu baris horizontal, diberi label a, b, c, dan d dari kiri ke kanan. Sisi-sisi menghubungkan setiap simpul dengan simpul di kanannya. Sebuah sisi lengkung menghubungkan a dengan c, dan sisi lengkung lainnya menghubungkan b dengan d.$

Kita perlu berhati-hati mengenai arti dua graf yang “sama.” Sebenarnya, berdasarkan definisi kita, hal ini mudah: Apakah himpunan simpulnya sama? Apakah himpunan sisinya sama? Kita mengetahui arti kesamaan dua himpunan, dan graf tidak lain adalah pasangan dari dua jenis himpunan khusus.

🔗

Contoh 2.1.2.

Apakah graf-graf di bawah ini sama?

\begin{equation*} G_1 = (\{a,b,c\}, \{\{a,b\}, \{b,c\}\}); \qquad G_2 = (\{a,b,c\}, \{\{a,c\}, \{c, b\}\})\text{.} \end{equation*}

🔗

Penyelesaian.

Tidak. Di sini himpunan simpul kedua graf sama, yang merupakan awal yang baik. Selain itu, kedua graf memiliki dua sisi. Pada graf pertama, kita memiliki sisi $\{a,b\}$ dan $\{b,c\}\text{,}$ sedangkan pada graf kedua kita memiliki sisi $\{a,c\}$ dan $\{c,b\}\text{.}$ Tentu saja, $\{b,c\} = \{c,b\}\text{,}$ jadi itu bukan masalahnya. Masalahnya adalah $\{a,b\} \ne \{a,c\}\text{.}$ Karena himpunan sisi kedua graf tidak sama (sebagai himpunan), graf-graf tersebut tidak sama (sebagai graf).

🔗

Meskipun dua graf tidak sama, keduanya mungkin pada dasarnya sama. Graf-graf pada contoh sebelumnya dapat digambar seperti berikut:

🔗

$Dua graf yang masing-masing memiliki tiga simpul tersusun dalam baris horizontal. Sisi-sisi menghubungkan setiap simpul dengan simpul di sebelahnya. Graf di kiri (G1) memiliki simpul berlabel a, b, c dari kiri ke kanan. Graf di kanan (G2) memiliki simpul berlabel a, c, b dari kiri ke kanan.$

Graf-graf yang pada dasarnya sama (tetapi mungkin tidak setara) disebut isomorfik. Kita akan memberikan definisi tepat bagi istilah ini setelah sebuah contoh singkat:

🔗

Contoh 2.1.3.

Perhatikan graf-graf berikut:

\begin{equation*} G_1 = (V_1, E_1) \text{ dengan } V_1 = \{a, b, c\} \text{ dan } E_1 = \{\{a,b\}, \{a,c\}, \{b,c\}\}; \end{equation*}

\begin{equation*} G_2 = (V_2, E_2) \text{ dengan } V_2 = \{u,v,w\} \text{ dan }E_2 = \{\{u,v\}, \{u,w\}, \{v,w\}\}. \end{equation*}

🔗

Apakah graf-graf ini sama?

🔗

Penyelesaian.

Kedua graf tersebut TIDAK sama. Cukup perhatikan bahwa $V_1 \ne V_2$ karena $a \in V_1\text{,}$ tetapi $a \notin V_2\text{.}$ Namun, kedua graf tersebut terdiri atas tiga simpul dengan sisi yang menghubungkan setiap pasangan simpul. Kita dapat menggambarnya sebagai berikut:

🔗

$Sebuah graf dengan tiga simpul yang tersusun membentuk segitiga, dengan sisi-sisi di sepanjang batas segitiga. Simpul-simpulnya diberi label a, b, dan c.$

$Sebuah graf dengan tiga simpul yang tersusun membentuk segitiga, dengan sisi-sisi di sepanjang batas segitiga. Simpul-simpulnya diberi label u, v, dan w.$

Jelas bahwa kita ingin mengatakan kedua graf ini pada dasarnya sama; jadi meskipun tidak setara, keduanya isomorfik. Kita dapat mengganti nama simpul-simpul pada satu graf dan memperoleh graf kedua sebagai hasilnya.

🔗

Secara intuitif, graf-graf disebut isomorfik jika pada dasarnya sama, atau lebih tepatnya, jika keduanya sama kecuali nama simpul-simpulnya. Untuk merumuskan konsep penggantian nama simpul secara tepat, kita memberikan definisi berikut:

🔗

Definisi 2.1.4.

Sebuah isomorfisme antara dua graf $G_1$ dan $G_2$ adalah bijeksi $f:V_1 \to V_2$ antara simpul-simpul kedua graf sedemikian sehingga $\{a,b\}$ merupakan sisi di $G_1$ jika dan hanya jika $\{f(a), f(b)\}$ merupakan sisi di $G_2\text{.}$

🔗

Dua graf disebut isomorfik jika terdapat isomorfisme di antara keduanya. Dalam hal ini kita menulis $G_1 \isom G_2\text{.}$

🔗

Isomorfisme tidak lain adalah fungsi yang mengganti nama simpul-simpul. Fungsi tersebut harus berupa bijeksi agar setiap simpul memperoleh nama baru. Simpul-simpul yang baru dinamai ini harus dihubungkan oleh sisi tepat ketika simpul-simpul tersebut dihubungkan oleh sisi saat menggunakan nama lamanya.

🔗

Contoh 2.1.5.

Tentukan apakah graf $G_1 = (V_1, E_1)$ dan $G_2 = (V_2, E_2)$ sama atau isomorfik.

🔗

$V_1 = \{a,b,c,d\}\text{,}$ $E_1 = \{\{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\}$

🔗

$V_2 = \{a,b,c,d\}\text{,}$ $E_2 = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$

🔗

Penyelesaian.

Kedua graf TIDAK sama, karena $\{a,d\} \in E_1\text{,}$ tetapi $\{a,d\} \notin E_2\text{.}$ Namun, karena kedua graf memuat banyak simpul dan sisi yang sama, keduanya mungkin isomorfik (hal ini belum cukup dalam kebanyakan kasus, tetapi merupakan awal yang baik).

🔗

Kita dapat mencoba membangun sebuah isomorfisme. Misalkan kita menetapkan $f(a) = b\text{,}$ $f(b) = c\text{,}$ $f(c) = d\text{,}$ dan $f(d) = a\text{.}$ Fungsi ini jelas merupakan bijeksi, tetapi untuk memastikan bahwa fungsi tersebut merupakan isomorfisme, kita harus memastikan bahwa fungsi itu mempertahankan relasi sisi. Di $G_1\text{,}$ simpul $a$ dan $b$ dihubungkan oleh sebuah sisi. Di $G_2\text{,}$ $f(a) = b$ dan $f(b) = c$ dihubungkan oleh sebuah sisi. Sejauh ini baik, tetapi kita harus memeriksa tiga sisi lainnya. Sisi $\{a,c\}$ di $G_1$ berpadanan dengan $\{f(a), f(c)\} = \{b,d\}\text{,}$ tetapi di sini timbul masalah. Tidak ada sisi antara $b$ dan $d$ di $G_2\text{.}$ Jadi, $f$ BUKAN isomorfisme.

🔗

Namun, harapan belum hilang. Hanya karena $f$ bukan isomorfisme, bukan berarti sama sekali tidak ada isomorfisme. Kita dapat mencoba lagi. Pada tahap ini, menggambar graf-graf tersebut mungkin membantu untuk melihat bagaimana keduanya seharusnya dipadankan.

🔗

$Graf G1 dengan empat simpul yang tersusun membentuk belah ketupat. Simpul atas (a) terhubung dengan tiga simpul lainnya (d di kiri, b di kanan, dan c di bawah). Terdapat satu sisi tambahan antara d dan c.$

$Graf G2 dengan empat simpul yang tersusun membentuk belah ketupat. Simpul atas (a) terhubung dengan simpul c di bawah dan b di kanan. Terdapat dua sisi tambahan: antara d (di kiri) dan c, serta antara b dan c.$

Sebagai alternatif, perhatikan bahwa di $G_1\text{,}$ simpul $a$ bertetangga dengan setiap simpul lainnya. Di $G_2\text{,}$ juga terdapat simpul dengan sifat ini, yaitu $c\text{.}$ Jadi, bangun bijeksi $g:V_1 \to V_2$ dengan terlebih dahulu mendefinisikan $g(a) = c\text{.}$ Selanjutnya, ke mana $b$ harus dipetakan? Di $G_1\text{,}$ simpul $b$ hanya bertetangga dengan simpul $a\text{.}$ Tepat ada satu simpul seperti ini di $G_2\text{,}$ yaitu $d\text{.}$ Jadi tetapkan $g(b) = d\text{.}$ Untuk dua simpul terakhir, dalam contoh ini kita bebas memilih: tetapkan $g(c) = b$ dan $g(d) = a$ (menukar keduanya juga tidak menjadi masalah).

🔗

Kita perlu memeriksa bahwa fungsi ini benar-benar merupakan isomorfisme. Fungsi ini jelas bijektif. Kita harus memastikan bahwa sisi-sisinya dipertahankan. Empat sisi di $G_1$ adalah

\begin{equation*} \{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\text{.} \end{equation*}

🔗

Di bawah isomorfisme yang diusulkan, sisi-sisi tersebut menjadi

\begin{equation*} \{g(a), g(b)\}, \{g(a), g(c)\}, \{g(a), g(d)\}, \{g(c), g(d)\} \end{equation*}

\begin{equation*} \{c,d\}, \{c,b\}, \{c,a\}, \{b,a\}\text{,} \end{equation*}

yang tepat merupakan sisi-sisi di $G_2\text{.}$ Jadi, $g$ adalah isomorfisme, sehingga $G_1 \cong G_2$

🔗

Kadang-kadang kita akan membahas graf dengan nama khusus (seperti $K_n$ atau graf Petersen) atau mungkin menggambar graf tanpa label. Dalam hal ini, sebenarnya kita merujuk pada semua graf yang isomorfik dengan setiap salinan graf khusus tersebut. Kumpulan graf yang isomorfik sering disebut kelas isomorfisme.

Hal ini serupa dengan geometri, di mana kita mungkin memiliki lebih dari satu salinan suatu segitiga tertentu. Dalam geometri, alih-alih isomorfik, kita mengatakan kongruen.

🔗

Ada hubungan lain di antara graf yang kita perhatikan, selain kesamaan dan sifat isomorfik. Sebagai contoh, bandingkan pasangan graf berikut:

🔗

$Sebuah graf dengan enam simpul yang tersusun membentuk segienam, dengan sisi di antara setiap pasangan simpul yang mungkin.$

$Empat simpul tersusun membentuk belah ketupat, dengan sisi di antara setiap pasangan simpul yang mungkin.$

Kedua graf ini jelas tidak isomorfik, tetapi perhatikan bahwa graf di kanan tampak seperti bagian dari graf di kiri, khususnya jika kita menggambarnya seperti berikut:

🔗

$Sebuah graf dengan enam simpul yang tersusun membentuk segienam, dengan sisi di antara setiap pasangan simpul. Enam sisi digambar tebal, membentuk persegi panjang miring dengan sebuah X di dalamnya.$

Kita ingin mengatakan bahwa graf yang lebih kecil merupakan subgraf dari graf yang lebih besar.

🔗

Kita perlu memberikan definisi yang cermat mengenai hal ini. Sebenarnya, terdapat dua pengertian yang masuk akal tentang makna subgraf.

🔗

Definisi 2.1.6. Subgraf.

Kita mengatakan bahwa $G' = (V', E')$ merupakan subgraf dari $G = (V, E)\text{,}$ dan menulis $G' \subseteq G\text{,}$ jika $V' \subseteq V$ dan $E' \subseteq E\text{.}$

🔗

Kita mengatakan bahwa $G' = (V', E')$ merupakan subgraf terinduksi dari $G = (V, E)$ jika $V' \subseteq V$ dan setiap sisi di $E$ yang simpul-simpulnya masih berada di $V'$ juga merupakan sisi di $E'\text{.}$

🔗

Perhatikan bahwa setiap subgraf terinduksi juga merupakan subgraf biasa, tetapi kebalikannya tidak selalu berlaku. Bayangkan subgraf sebagai hasil penghapusan beberapa simpul dan sisi dari graf yang lebih besar. Agar subgraf tersebut merupakan subgraf terinduksi, kita masih dapat menghapus simpul, tetapi sekarang kita hanya menghapus sisi-sisi yang memuat simpul yang dihapus.

🔗

Contoh 2.1.7.

Perhatikan graf-graf berikut:

🔗

$Graf G1 terdiri atas enam simpul yang tersusun membentuk segitiga. Dimulai dari simpul kiri bawah dan bergerak mengelilingi segitiga searah jarum jam, simpul-simpul diberi label a, d, f, e, c, b. Sisi-sisi menghubungkan simpul di sudut-sudut segitiga dengan simpul di sepanjang sisinya. Simpul-simpul tengah ini juga saling terhubung satu sama lain.$

$Graf G2 dengan empat simpul: tiga simpul dalam baris horizontal berlabel a, b, c, dan sebuah simpul berlabel d yang berada di tengah, di atas a dan b. Sisi-sisi menghubungkan a, b, dan d (membentuk segitiga), sedangkan sisi keempat menghubungkan b dengan c.$

$Graf G3 dengan lima simpul. Simpul a, b, dan c tersusun dalam baris horizontal. Simpul a, d, dan f membentuk garis yang miring ke kanan atas. Terdapat sisi antara a dan d, antara d dan f, antara d dan b, serta antara b dan c.$

$Graf G4 dengan lima simpul: a, b, dan c membentuk baris horizontal, sedangkan a, d, dan f terletak pada sebuah garis yang miring ke kanan atas. Simpul-simpul tersebut membentuk segitiga, dan sisi-sisinya tersusun mengisi batas luar segitiga. Simpul d dan b juga dihubungkan oleh sebuah sisi.$

Di sini $G_2$ dan $G_3$ merupakan subgraf dari $G_1\text{.}$ Namun, hanya $G_2$ yang merupakan subgraf terinduksi. Setiap sisi di $G_1$ yang menghubungkan simpul-simpul dalam $G_2$ juga merupakan sisi di $G_2\text{.}$ Di $G_3\text{,}$ sisi $\{a,b\}$ berada di $E_1\text{,}$ tetapi tidak di $E_3\text{,}$ meskipun simpul $a$ dan $b$ berada di $V_3\text{.}$

🔗

Graf $G_4$ BUKAN subgraf dari $G_1\text{,}$ meskipun tampaknya kita hanya menghapus simpul $e\text{.}$ Alasannya, di $E_4$ terdapat sisi $\{c,f\}\text{,}$ tetapi sisi ini bukan anggota $E_1\text{,}$ sehingga syarat $E_4 \subseteq E_1$ tidak terpenuhi.

🔗

Kembali ke beberapa definisi dasar teori graf. Perhatikan bahwa semua graf yang telah kita gambar di atas memiliki sifat bahwa tidak ada pasangan simpul yang dihubungkan lebih dari satu kali, dan tidak ada simpul yang terhubung dengan dirinya sendiri. Graf seperti ini kadang-kadang disebut sederhana, meskipun kita cukup menyebutnya graf. Hal ini karena definisi graf kita menyatakan bahwa sisi-sisi membentuk suatu himpunan subhimpunan dua unsur dari himpunan simpul. Ingat bahwa tidak masuk akal mengatakan suatu himpunan memuat sebuah unsur lebih dari satu kali. Jadi, tidak ada pasangan simpul yang dapat dihubungkan oleh sisi lebih dari satu kali. Selain itu, karena setiap sisi harus berupa himpunan yang memuat dua simpul, satu simpul tidak dapat dihubungkan dengan dirinya sendiri oleh sebuah sisi.

🔗

Meskipun demikian, ada kalanya kita ingin mempertimbangkan sisi rangkap (atau lebih) dan gelang berupa satu sisi. Sebagai contoh, “graf” yang kita gambar untuk masalah Jembatan Königsberg memiliki sisi rangkap karena memang ada dua jembatan yang menghubungkan suatu pulau tertentu dengan tepi sungai terdekat. Objek-objek ini kita sebut multigraf. Nama ini tepat: Multihimpunan adalah himpunan yang memperbolehkan satu unsur dicantumkan beberapa kali.

🔗

Graf-graf di atas juga terhubung: Anda dapat berpindah dari satu simpul ke simpul lainnya dengan mengikuti suatu lintasan sisi. Graf yang tidak terhubung dapat dianggap sebagai dua graf terpisah yang digambar berdekatan. Sebagai contoh, graf berikut TIDAK terhubung karena tidak ada lintasan dari $a$ ke $b\text{:}$

🔗

$Sebuah graf yang terdiri atas delapan simpul yang tersusun menjadi dua belah ketupat yang saling bertumpang tindih, dengan sisi-sisi membentuk batas kedua belah ketupat tersebut. Simpul paling kiri diberi label a dan simpul paling kanan diberi label b.$

Simpul-simpul dalam suatu graf tidak selalu memiliki sisi di antaranya. Jika kita menambahkan semua sisi yang mungkin, graf yang dihasilkan disebut lengkap. Artinya, suatu graf lengkap jika setiap pasangan simpul dihubungkan oleh sebuah sisi. Karena suatu graf sepenuhnya ditentukan oleh simpul mana yang bertetangga dengan simpul lainnya, hanya ada satu graf lengkap dengan banyak simpul tertentu. Kita memberi graf-graf tersebut nama khusus: $K_n$ adalah graf lengkap dengan $n$ simpul.

🔗

Setiap simpul di $K_n$ bertetangga dengan $n-1$ simpul lainnya. Kita menyebut banyaknya sisi yang memancar dari suatu simpul sebagai derajat simpul tersebut. Jadi, setiap simpul di $K_n$ berderajat $n-1\text{.}$ Berapa banyak sisi yang dimiliki $K_n\text{?}$ Orang mungkin menduga jawabannya $n(n-1)\text{,}$ karena kita menghitung $n-1$ sisi sebanyak $n$ kali (satu kali untuk setiap simpul). Namun, setiap sisi bersisian dengan 2 simpul, sehingga kita menghitung setiap sisi tepat dua kali. Jadi, terdapat $n(n-1)/2$ sisi di $K_n\text{.}$ Sebagai alternatif, kita dapat mengatakan terdapat ${n \choose 2}$ sisi, karena untuk menggambar sebuah sisi kita harus memilih 2 dari $n$ simpul.

🔗

Secara umum, jika kita mengetahui derajat semua simpul dalam suatu graf, kita dapat menentukan banyaknya sisi. Jumlah derajat semua simpul akan selalu sama dengan dua kali banyaknya sisi, karena setiap sisi menambah derajat dua simpul. Perhatikan bahwa hal ini berarti jumlah derajat semua simpul dalam setiap graf harus genap!

🔗

Ini adalah contoh pertama kita tentang hasil umum yang berlaku bagi semua graf. Hasil ini tampak sederhana, tetapi kita akan menggunakannya untuk membuktikan berbagai pernyataan lain. Jadi, mari kita beri nama dan nyatakan hasil tersebut secara formal.

🔗

Lema 2.1.8. Lema Jabat Tangan.

Dalam setiap graf, jumlah derajat simpul-simpul dalam graf selalu sama dengan dua kali banyaknya sisi.

🔗

Lema jabat tangan

Sebuah lema adalah pernyataan matematis yang penting terutama karena digunakan untuk menetapkan hasil-hasil lain.

kadang-kadang disebut rumus jumlah derajat, dan dapat ditulis secara simbolis sebagai

\begin{equation*} \sum_{v\in V} d(v) = 2e\text{.} \end{equation*}

Di sini kita menggunakan notasi $d(v)$ untuk derajat simpul $v\text{.}$

🔗

Salah satu kegunaan lema ini adalah menentukan banyaknya sisi dalam suatu graf. Untuk melakukannya, Anda harus diberi barisan derajat graf tersebut (atau dapat menentukannya dari informasi lain). Barisan ini memuat derajat setiap simpul dalam graf, dan umumnya ditulis dalam urutan tak-menaik.

🔗

Contoh 2.1.9.

Berapa banyak simpul dan sisi yang harus dimiliki suatu graf jika barisan derajatnya adalah

\begin{equation*} (4, 4, 3, 3, 3, 2, 1)\text{?} \end{equation*}

🔗

Penyelesaian.

Banyaknya simpul mudah ditentukan. Nilainya sama dengan banyaknya derajat dalam barisan, yaitu 7. Untuk menentukan banyaknya sisi, kita menghitung jumlah derajat

\begin{equation*} 4 + 4 + 3 + 3 + 3 + 2 + 1 = 20\text{,} \end{equation*}

sehingga banyaknya sisi adalah setengah dari nilai tersebut, yaitu 10.

🔗

Lema jabat tangan juga memberi tahu kita apa yang tidak mungkin.

🔗

Contoh 2.1.10.

Dalam suatu seminar matematika baru-baru ini, 9 matematikawan saling menyapa dengan berjabat tangan. Mungkinkah setiap matematikawan berjabat tangan dengan tepat 7 orang dalam seminar tersebut?

🔗

Penyelesaian.

Tampaknya hal ini mungkin. Setiap matematikawan memilih satu orang yang tidak diajak berjabat tangan. Namun, hal ini tidak dapat terjadi. Kita sedang menanyakan apakah suatu graf dengan 9 simpul dapat memiliki setiap simpul berderajat 7. Jika graf semacam itu ada, jumlah derajat simpul-simpulnya adalah $9\cdot 7 = 63\text{.}$ Nilai ini seharusnya dua kali banyaknya sisi (jabat tangan), sehingga graf tersebut memiliki $31.5$ sisi. Hal itu mustahil. Jadi, setidaknya satu (bahkan sejumlah ganjil) matematikawan pasti berjabat tangan dengan orang dalam jumlah genap dalam seminar tersebut.

🔗

Kita dapat menggeneralisasi contoh sebelumnya untuk memperoleh proposisi berikut.

Sebuah proposisi adalah pernyataan umum dalam matematika, serupa dengan teorema, meskipun umumnya dianggap kurang penting.

🔗

Proposisi 2.1.11.

Dalam setiap graf, banyaknya simpul yang berderajat ganjil harus genap.

🔗

Bukti.

Misalkan terdapat graf dengan banyak simpul berderajat ganjil yang ganjil. Maka jumlah derajat dalam graf tersebut akan ganjil, yang mustahil menurut lema jabat tangan.

🔗

Kita akan membahas penerapan lebih lanjut dari lema jabat tangan dalam latihan.

🔗

Satu definisi terakhir: Kita mengatakan suatu graf bipartit jika simpul-simpulnya dapat dibagi menjadi dua himpunan, $A$ dan $B\text{,}$ dengan tidak ada dua simpul di $A$ yang bertetangga dan tidak ada dua simpul di $B$ yang bertetangga. Simpul-simpul di $A$ dapat bertetangga dengan sebagian atau seluruh simpul di $B\text{.}$ Jika setiap simpul di $A$ bertetangga dengan seluruh simpul di $B\text{,}$ graf tersebut merupakan graf bipartit lengkap dan diberi nama khusus: $K_{m,n}\text{,}$ dengan $|A| = m$ dan $|B| = n\text{.}$

🔗

Graf Bernama.

Beberapa graf digunakan lebih sering daripada graf lainnya dan diberi nama khusus.

$K_n$ 🔗: Graf lengkap dengan $n$ simpul.
🔗
$K_{m,n}$ 🔗: Graf bipartit lengkap dengan himpunan yang masing-masing memiliki $m$ dan $n$ simpul.
🔗
$C_n$ 🔗: Siklus pada $n$ simpul, yakni satu putaran besar.
🔗
$P_n$ 🔗: Lintasan pada $n+1$ simpul (jadi memiliki $n$ sisi), yakni satu lintasan panjang.
🔗

🔗

$Graf K5: lima simpul tersusun membentuk segilima. Setiap simpul dihubungkan dengan setiap simpul lainnya oleh sebuah sisi.$

$Graf K2,3: dua simpul pada baris atas dan tiga simpul pada baris bawah. Setiap simpul pada baris atas dihubungkan dengan setiap simpul pada baris bawah.$

$Graf C6: siklus yang terdiri atas enam simpul yang dihubungkan oleh enam sisi dan tersusun membentuk segienam.$

$Graf P5: enam simpul yang dihubungkan oleh lima sisi. Simpul pertama dan terakhir masing-masing memiliki satu sisi, sedangkan setiap simpul lainnya memiliki dua sisi (yang menghubungkannya dengan simpul sebelum dan sesudahnya pada lintasan).$

🔗

Definisi Teori Graf.

Ada banyak definisi yang perlu diingat dalam teori graf. Berikut adalah glosarium istilah yang telah kita gunakan dan akan segera kita jumpai.

Graf 🔗: Kumpulan simpul, yang sebagian di antaranya dihubungkan oleh sisi. Lebih tepatnya, pasangan himpunan $V$ dan $E\text{,}$ dengan $V$ sebagai himpunan simpul dan $E$ sebagai himpunan subhimpunan dua unsur dari $V\text{.}$
🔗
Bertetangga 🔗: Dua simpul bertetangga jika keduanya dihubungkan oleh sebuah sisi. Dua sisi bertetangga jika keduanya berbagi sebuah simpul.
🔗
Graf bipartit 🔗: Graf yang simpul-simpulnya dapat dibagi menjadi dua himpunan saling lepas sedemikian sehingga tidak ada sisi di antara dua simpul dalam himpunan yang sama.
🔗
Graf bipartit lengkap 🔗: Graf bipartit yang setiap simpul dalam himpunan pertama bertetangga dengan setiap simpul dalam himpunan kedua.
🔗
Graf lengkap 🔗: Graf yang setiap pasangan simpulnya bertetangga.
🔗
Terhubung 🔗: Suatu graf disebut terhubung jika terdapat lintasan dari setiap simpul ke setiap simpul lainnya.
🔗
Bilangan kromatik 🔗: Banyaknya warna minimum yang diperlukan dalam pewarnaan simpul yang tepat pada graf.
🔗
Siklus 🔗: Lintasan (lihat di bawah) yang berawal dan berakhir pada simpul yang sama, tetapi tidak memuat simpul berulang lainnya.
🔗
Derajat simpul 🔗: Banyaknya sisi yang bersisian dengan sebuah simpul.
🔗
Jejak Euler 🔗: Perjalanan yang menggunakan setiap sisi tepat satu kali.
🔗
Sirkuit Euler 🔗: Jejak Euler yang berawal dan berakhir pada simpul yang sama.
🔗
Multigraf 🔗: Sebuah multigraf serupa dengan graf, tetapi dapat memuat beberapa sisi di antara dua simpul serta gelang satu sisi (yaitu sisi dari suatu simpul ke dirinya sendiri).
🔗
Lintasan 🔗: Sebuah lintasan adalah perjalanan yang tidak mengulangi simpul (atau sisi) apa pun, kecuali mungkin simpul pertama dan terakhir. Jika suatu lintasan berawal dan berakhir pada simpul yang sama, lintasan itu disebut siklus.
🔗
Planar 🔗: Graf yang dapat digambar (pada bidang) tanpa ada sisi yang berpotongan.
🔗
Subgraf 🔗: Kita mengatakan bahwa $H$ merupakan subgraf dari $G$ jika setiap simpul dan sisi $H$ juga merupakan simpul atau sisi $G\text{.}$ Kita mengatakan $H$ merupakan subgraf terinduksi dari $G$ jika setiap simpul $H$ merupakan simpul $G$ dan setiap pasangan simpul di $H$ bertetangga di $H$ jika dan hanya jika keduanya bertetangga di $G$ .
🔗
Pohon 🔗: Graf terhubung tanpa siklus. (Jika kita menghilangkan syarat bahwa graf harus terhubung, graf tersebut disebut hutan.) Simpul-simpul dalam pohon yang berderajat 1 disebut daun.
🔗
Pewarnaan simpul 🔗: Pemberian warna kepada setiap simpul suatu graf. Pewarnaan simpul disebut tepat jika simpul-simpul yang bertetangga selalu diberi warna berbeda.
🔗
Perjalanan 🔗: Barisan simpul sedemikian sehingga simpul-simpul yang berurutan (dalam barisan) bertetangga (dalam graf). Perjalanan yang tidak mengulangi sisi disebut jejak, dan jejak yang tidak mengulangi simpul (kecuali mungkin simpul pertama dan terakhir) disebut lintasan.
🔗

🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Adakah lebih dari satu graf dengan lima simpul dan enam sisi? Jelaskan apa sebenarnya arti pertanyaan ini dan bagaimana Anda akan menjawabnya.

🔗

2.

Jika suatu graf memiliki 10 simpul yang masing-masing berderajat 4, berapa banyak sisi yang dimilikinya?

🔗

Banyaknya sisi:

🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu lebih lanjut.

🔗

Latihan Soal Latihan

1.

Perhatikan graf $\Gamma$ berikut:

🔗

Manakah di antara graf-graf di bawah ini yang isomorfik dengan $\Gamma\text{?}$

🔗


A	B	C 🔗

Nyatakan isomorfismenya dengan menuliskan simpul-simpul yang dipisahkan oleh koma, sesuai urutan korespondensinya dengan A,B,C,D,E,F.

🔗

2.

Manakah di antara graf-graf berikut yang saling isomorfik?

🔗


A	B


C	D 🔗

🔗

3.

Graf $G_1$ memiliki 7 simpul yang semuanya berderajat 4. Berapa banyak sisi yang dimiliki $G_1\text{?}$ Jawaban:

🔗

Graf $G_2$ memiliki 8 simpul yang semuanya berderajat $k\text{.}$ Selain itu, $G_2$ memiliki 20 sisi. Berapakah $k\text{?}$ Jawaban:

🔗

Graf $G_3$ memiliki $v$ simpul yang semuanya berderajat 4. Selain itu, $G_3$ memiliki 16 sisi. Berapakah $v\text{?}$ Jawaban:

🔗

4.

Saya memikirkan sebuah graf yang memiliki barisan derajat $(8,8,8,8,8,7,7,7,7)$. Berapa banyak sisi yang harus dimiliki graf tersebut?

🔗

5.

1. Berapakah $n$ terbesar sehingga $P_n$ merupakan subgraf dari $K_{7}\text{?}$

🔗

2. Berapakah $n$ terbesar sehingga $C_n$ merupakan subgraf dari $K_{7}\text{?}$

🔗

3. Berapakah $n$ terbesar sehingga $P_n$ merupakan subgraf terinduksi dari $K_{7}\text{?}$

🔗

4. Berapakah $n$ terbesar sehingga $C_n$ merupakan subgraf terinduksi dari $K_{7}\text{?}$

🔗

Petunjuk.

Ingatlah bahwa $P_n$ adalah lintasan yang memuat $n$ sisi dan $n+1$ simpul.

🔗

Latihan Latihan Tambahan

1.

Jika 10 orang masing-masing berjabat tangan dengan setiap orang lainnya, berapa banyak jabat tangan yang terjadi? Apa kaitan pertanyaan ini dengan teori graf?

🔗

2.

Dalam sekelompok 5 orang, mungkinkah setiap orang berteman dengan tepat 2 orang lain dalam kelompok tersebut? Bagaimana jika tepat 3 orang?

🔗

3.

Mungkinkah dua graf yang berbeda (tidak isomorfik) memiliki jumlah simpul dan jumlah sisi yang sama? Bagaimana jika derajat simpul-simpul pada kedua graf juga sama (misalnya, kedua graf memiliki simpul-simpul berderajat 1, 2, 2, 3, dan 4)? Gambarkan dua graf semacam itu atau jelaskan mengapa tidak mungkin.

🔗

Petunjuk.

Kedua situasi tersebut mungkin terjadi. Carilah beberapa contohnya.

🔗

4.

Apakah kedua graf di bawah ini sama? Apakah keduanya isomorfik? Jika isomorfik, berikan isomorfismenya. Jika tidak, jelaskan.

🔗

Graf 1: $V = \{a,b,c,d,e\}\text{,}$ $E = \{\{a,b\}, \{a,c\}, \{a,e\}, \{b,d\}, \{b,e\}, \{c,d\}\}$ .

🔗

Graf 2:

🔗

$Graf dengan lima simpul yang tersusun membentuk segilima, berlabel a sampai e mulai dari simpul paling atas dan berlanjut searah jarum jam. Sisi-sisi di antara simpul a, c, dan d membentuk segitiga. Sisi-sisi di antara simpul b, c, d, dan e membentuk segiempat.$

🔗

5.

Perhatikan kedua graf berikut:

$G_1$ 🔗: $V_1=\{a,b,c,d,e,f,g\}$
🔗

$E_1=\{\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{b,e\},$
🔗

$\quad\{b,f\},\{c,g\},\{d,e\}, \{e,f\},\{f,g\}\}\text{.}$
🔗
$G_2$ 🔗: $V_2=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\text{,}$
🔗

$E_2=\{\{v_1,v_4\},\{v_1,v_5\},\{v_1,v_7\},\{v_2,v_3\},\{v_2,v_6\},$
🔗

$\quad\{v_3,v_5\},\{v_3,v_7\},\{v_4,v_5\},\{v_5,v_6\},\{v_5,v_7\}\}\text{.}$
🔗

Misalkan $f:G_1 \rightarrow G_2$ adalah fungsi yang memetakan simpul-simpul graf 1 ke simpul-simpul graf 2. Fungsi tersebut diberikan oleh tabel berikut:
🔗

$x$ $a$ $b$ $c$ $d$ $e$ $f$ $g$

$f(x)$ $v_4$ $v_5$ $v_1$ $v_6$ $v_2$ $v_3$ $v_7$

Apakah $f$ mendefinisikan suatu isomorfisme antara graf 1 dan graf 2?
🔗

🔗
Definisikan fungsi baru $g$ (dengan $g \ne f$) yang mendefinisikan suatu isomorfisme antara graf 1 dan graf 2.
🔗

🔗
Apakah graf yang digambarkan di bawah ini isomorfik dengan graf 1 dan graf 2? Jelaskan.
🔗

$Graf dengan tujuh simpul. Enam simpul tersusun membentuk persegi panjang dalam dua baris yang masing-masing berisi tiga simpul, dengan sisi-sisi di sepanjang kelilingnya. Simpul ketujuh berada di tengah, dengan sisi-sisi yang menghubungkannya ke simpul tepat di atas dan di bawahnya, serta ke dua simpul terluar pada baris bawah.$

🔗

🔗

6.

Berapa jumlah sisi terbesar yang mungkin pada graf dengan 10 simpul? Berapa jumlah sisi terbesar yang mungkin pada graf bipartit dengan 10 simpul? Berapa jumlah sisi terbesar yang mungkin pada pohon dengan 10 simpul?

🔗

Petunjuk.

Bagian graf bipartit sedikit lebih rumit. Anda tentu memerlukan graf bipartit lengkap, tetapi grafnya dapat berupa $K_{5,5}\text{,}$ mungkin $K_{1,9}\text{,}$ atau …

🔗

7.

Manakah di antara graf di bawah ini yang bipartit? Jelaskan alasan jawaban Anda.

🔗

$Graf yang terdiri atas enam simpul yang tersusun membentuk segienam. Sisi-sisi menghubungkan setiap simpul ke dua simpul lain, tetapi tidak membentuk siklus di sepanjang keliling segienam. Meskipun demikian, penelusuran sepanjang sisi-sisinya mengunjungi setiap simpul.$

$Graf yang terdiri atas tujuh simpul yang tersusun membentuk segitujuh, dengan sisi-sisi yang membentuk keliling segitujuh tersebut.$

$Graf yang terdiri atas satu simpul pusat dengan delapan sisi yang menghubungkannya ke delapan simpul yang tersusun melingkar di sekelilingnya.$

Petunjuk.

Graf pertama bipartit, sebagaimana terlihat dengan memberi label berikut.

🔗

$Graf dengan lima simpul. Empat simpul menempati sudut-sudut belah ketupat; simpul terakhir berada di tengah. Sisi-sisi membentuk keliling belah ketupat dan menghubungkan simpul tengah ke dua sudut di sebelah kiri dan kanan. Simpul di kiri dan kanan berlabel A, sedangkan ketiga simpul pada kolom tengah masing-masing berlabel B.$

Dua dari tiga graf lainnya juga bipartit.

🔗

8.

Untuk nilai $n \ge 3$ manakah graf $C_n$ bipartit?

🔗

Petunjuk.

$C_4$ bipartit, sedangkan $C_5$ tidak. Bagaimana dengan semua nilai $n$ lainnya?

🔗

9.

Untuk setiap kasus berikut, berikan dua graf tak berlabel yang berbeda dengan sifat-sifat yang diberikan, atau jelaskan mengapa hal tersebut mustahil.

Dua pohon berbeda dengan jumlah simpul dan jumlah sisi yang sama. Pohon adalah graf terhubung yang tidak memiliki siklus.
🔗

🔗
Dua graf berbeda dengan 8 simpul yang semuanya berderajat 2.
🔗

🔗
Dua graf berbeda dengan 5 simpul yang semuanya berderajat 4.
🔗

🔗
Dua graf berbeda dengan 5 simpul yang semuanya berderajat 3.
🔗

🔗

🔗

10.

Tentukan apakah pernyataan-pernyataan tentang subgraf di bawah ini benar atau salah. Untuk pernyataan yang benar, jelaskan alasannya secara singkat (1 atau 2 kalimat). Untuk setiap pernyataan yang salah, berikan contoh penyangkal.

Setiap subgraf dari graf lengkap juga lengkap.
🔗

🔗
Setiap subgraf terinduksi dari graf lengkap juga lengkap.
🔗

🔗
Setiap subgraf dari graf bipartit juga bipartit.
🔗

🔗
Setiap subgraf dari pohon juga merupakan pohon.
🔗

🔗

🔗

11.

Kita sering mendefinisikan konsep-konsep teori graf menggunakan teori himpunan. Sebagai contoh, untuk graf $G = (V, E)$ dan simpul $v \in V\text{,}$ kita mendefinisikan

\begin{equation*} N(v) = \{u \in V \st \{v,u\} \in E\}\text{.} \end{equation*}

Kita mendefinisikan $N[v] = N(v) \cup \{v\}\text{.}$ Tujuan soal ini adalah memahami makna semua definisi tersebut.

Misalkan $G$ adalah graf dengan himpunan simpul $V$ dan himpunan sisi $E$ yang diberikan oleh

\begin{equation*} V = \{a,b,c,d,e,f\},~~E = \{\{a,b\}, \{a,e\},\{b, c\}, \{b,e\}, \{c,d\}, \{c, f\}, \{d, f\}, \{e,f\}\}\text{.} \end{equation*}

Tentukan $N(a)\text{,}$ $N[a]\text{,}$ $N(c)\text{,}$ dan $N[c]\text{.}$

🔗

🔗
Berapakah nilai terbesar dan terkecil yang mungkin bagi $|N(v)|$ dan $|N[v]|$ (ukuran himpunan-himpunan tersebut) untuk graf pada bagian (a)? Jelaskan.
🔗

🔗
Berikan contoh graf $G = (V, E)$ (kemungkinan berbeda dari graf di atas) yang memenuhi $N[v] = V$ untuk suatu simpul $v \in V\text{.}$ Adakah graf yang memenuhi $N[v] = V$ untuk setiap $v \in V\text{?}$ Jelaskan.
🔗

🔗
Berikan contoh graf $G = (V,E)$ yang memenuhi $N(v) = \emptyset$ untuk suatu $v \in V\text{.}$ Adakah contoh graf semacam itu yang juga memenuhi $N[u] = V$ untuk suatu simpul lain $u \in V\text{?}$ Jelaskan.
🔗

🔗
Jelaskan dengan kata-kata makna umum $N(v)$ dan $N[v]\text{.}$
🔗

🔗

🔗

Petunjuk.

Anda seharusnya dapat menyimpulkan semuanya langsung dari definisi. Namun, mungkin akan membantu jika diketahui bahwa $N$ melambangkan lingkungan.

🔗

12.

Graf merupakan salah satu cara untuk merepresentasikan relasi di antara elemen-elemen suatu himpunan: sisi di antara simpul $x$ dan $y$ menunjukkan bahwa $x$ berelasi dengan $y$ (yang dapat ditulis sebagai $x \sim y$). Namun, tidak semua jenis relasi dapat direpresentasikan oleh graf. Untuk setiap relasi yang dijelaskan di bawah ini, gambarkan grafnya atau jelaskan mengapa relasi tersebut tidak dapat direpresentasikan oleh graf.

Himpunan $V = \{1,2, \ldots, 9\}$ dan relasi $x \sim y$ ketika $x-y$ merupakan kelipatan 3 yang tidak nol.
🔗

🔗
Himpunan $V = \{1,2, \ldots, 9\}$ dan relasi $x \sim y$ ketika $y$ merupakan kelipatan $x\text{.}$
🔗

🔗
Himpunan $V = \{1,2,\ldots, 9\}$ dan relasi $x \sim y$ ketika $0 \lt |x-y| \lt 3\text{.}$
🔗

🔗

🔗

Petunjuk.

Pastikan bahwa sisi-sisinya tidak “berarah.” Dalam graf, jika $a$ bertetangga dengan $b\text{,}$ maka $b$ bertetangga dengan $a\text{.}$ Dalam bahasa relasi, kita mengatakan bahwa relasi sisi bersifat simetris.

🔗

13.

Perhatikan graf-graf dengan $n$ simpul. Ingatlah bahwa graf tidak harus terhubung.

Berapa banyak sisi yang harus dimiliki graf untuk menjamin bahwa sedikitnya satu simpul berderajat dua atau lebih? Buktikan jawaban Anda.
🔗

🔗
Berapa banyak sisi yang harus dimiliki graf untuk menjamin bahwa semua simpul berderajat dua atau lebih? Buktikan jawaban Anda.
🔗

🔗

🔗

Petunjuk.

Anda mungkin perlu menjawab pertanyaan-pertanyaan tersebut untuk beberapa nilai khusus $n$ agar memahami polanya, tetapi jawaban akhir harus dinyatakan dalam $n\text{.}$

🔗

14.

Buktikan bahwa setiap graf dengan sedikitnya dua simpul pasti memiliki dua simpul dengan derajat yang sama.

🔗

Petunjuk.

Cobalah contoh kecil terlebih dahulu: setiap graf dengan 8 simpul pasti memiliki dua simpul dengan derajat yang sama. Jika tidak demikian, seperti apakah barisan derajatnya?

🔗

15.

Misalkan $G$ adalah graf terhubung dengan $n > 1$ simpul dan $n-1$ sisi. Buktikan bahwa $G$ memiliki simpul berderajat 1.

🔗

Petunjuk.

Gunakan lema jabat tangan 2.1.8. Apa yang akan terjadi jika semua simpul berderajat 2?

🔗

16.

Manakah (jika ada) di antara graf-graf di bawah ini yang sama?

🔗

$Graf dengan lima simpul yang tersusun dalam dua baris: dua simpul di atas dan tiga simpul di bawah. Sisi-sisi menghubungkan setiap simpul pada baris atas ke setiap simpul pada baris bawah.$

$Graf dengan lima simpul yang tersusun membentuk segilima. Setiap simpul dihubungkan oleh sisi ke dua simpul tetangganya di sepanjang segilima.$

$Graf dengan lima simpul yang tersusun membentuk belah ketupat dengan satu simpul di tengah. Simpul atas terhubung ke dua simpul terluar di bawahnya, yang masing-masing terhubung ke simpul bawah. Simpul tengah terhubung ke dua simpul di sebelah kiri dan kanannya.$

$Graf dengan lima simpul yang tersusun membentuk segilima, dengan sisi-sisi yang menghubungkan setiap simpul ke dua simpul yang paling jauh darinya (membentuk bintang bersudut lima).$

$Lima simpul tersusun membentuk belah ketupat dengan satu simpul di tengah. Simpul tengah dihubungkan oleh sisi ke setiap simpul lainnya.$

Graf-graf di atas tidak berlabel. Biasanya kita memandang graf sebagai objek yang memiliki himpunan simpul tertentu. Manakah (jika ada) di antara graf-graf di bawah ini yang sama?

🔗

$Graf dengan enam simpul yang tersusun dalam dua baris, masing-masing berisi tiga simpul. Simpul-simpul pada baris atas berlabel b, d, f dari kiri ke kanan. Simpul-simpul pada baris bawah berlabel a, c, e dari kiri ke kanan. Tiga sisi menghubungkan setiap simpul pada baris atas ke simpul di bawahnya. Empat sisi lainnya menyilang dari suatu simpul atas ke simpul bawah yang tepat berada di sebelah kiri atau kanannya (membentuk dua huruf X).$

$Graf dengan enam simpul yang tersusun dalam dua baris, masing-masing berisi tiga simpul. Simpul-simpul pada baris atas berlabel b, c, f dari kiri ke kanan. Simpul-simpul pada baris bawah berlabel a, d, e dari kiri ke kanan. Tiga sisi menghubungkan setiap simpul pada baris atas ke simpul di bawahnya. Empat sisi lainnya menghubungkan simpul-simpul di sepanjang baris atas dan baris bawah. Secara keseluruhan, bentuknya tampak seperti dua persegi yang berdampingan.$

$Graf dengan enam simpul yang tersusun dalam dua baris, masing-masing berisi tiga simpul. Simpul-simpul pada baris atas berlabel c, b, f dari kiri ke kanan. Simpul-simpul pada baris bawah berlabel a, e, d dari kiri ke kanan. Tiga sisi menghubungkan setiap simpul pada baris atas ke simpul di bawahnya. Empat sisi lainnya menyilang dari suatu simpul atas ke simpul bawah yang tepat berada di sebelah kiri atau kanannya (membentuk dua huruf X).$

$Graf dengan enam simpul yang tersusun dalam dua baris, masing-masing berisi tiga simpul. Simpul-simpul pada baris atas berlabel v1, v2, v3 dari kiri ke kanan. Simpul-simpul pada baris bawah berlabel v6, v5, v4 dari kiri ke kanan. Tiga sisi menghubungkan setiap simpul pada baris atas ke simpul di bawahnya. Empat sisi lainnya menghubungkan simpul-simpul di sepanjang baris atas dan baris bawah. Secara keseluruhan, bentuknya tampak seperti dua persegi yang berdampingan.$

Sebenarnya, semua graf di atas hanyalah gambar graf. Graf sesungguhnya merupakan objek matematika abstrak yang terdiri atas dua himpunan $V$ dan $E\text{,}$ dengan $E$ sebagai himpunan yang elemen-elemennya merupakan himpunan bagian beranggota 2 dari $V\text{.}$ Apakah graf-graf di bawah ini sama atau berbeda?

Graf 1: 🔗: $V = \{a, b, c, d, e\}\text{,}$
🔗

$E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}$ .
🔗
Graf 2: 🔗: $V = \{v_1, v_2, v_3, v_4, v_5\}\text{,}$
🔗

$E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{.}$
🔗

🔗

Sblm Top Lnjt

simpul	bertetangga dengan
\(a\)	\(b, c\)
\(b\)	\(a,f\)
\(c\)	\(a, d, e\)
\(d\)	\(c,e,f\)
\(e\)	\(c,d\)
\(f\)	\(b,d\)

\(x\)	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)	\(g\)
\(f(x)\)	\(v_4\)	\(v_5\)	\(v_1\)	\(v_6\)	\(v_2\)	\(v_3\)	\(v_7\)

Subbab 2.1 Masalah dan Definisi

Tujuan Pembelajaran

Subbagian Pratinjau Bagian

Selidiki!

Lembar Kerja Aktivitas Pratinjau

1.

2.

3.

(a)

(b)

(c)

4.

5.

Subbagian Apa Itu Graf?

Definisi 2.1.1. Graf.

Contoh 2.1.2.

Contoh 2.1.3.

Definisi 2.1.4.

Contoh 2.1.5.

Definisi 2.1.6. Subgraf.

Contoh 2.1.7.

Lema 2.1.8. Lema Jabat Tangan.

Contoh 2.1.9.

Contoh 2.1.10.

Proposisi 2.1.11.

Bukti.

Graf Bernama.

Definisi Teori Graf.

Pertanyaan Bacaan Pertanyaan Bacaan

1.

2.

3.

Latihan Soal Latihan

1.

2.

3.

4.

5.

Latihan Latihan Tambahan

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

Lembar Kerja Aktivitas Pratinjau