Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 2.2 Pohon

Subbagian Pratinjau Bagian

Selidiki!
Perhatikan graf yang digambar di bawah ini.
🔗
Graf dengan tujuh simpul yang tersusun dalam tiga baris: dua di atas, tiga di tengah, dan dua di bawah. Keempat simpul pada baris atas dan bawah dihubungkan oleh sisi-sisi yang membentuk persegi. Simpul pusat pada baris tengah bertetangga dengan keempat simpul pada baris atas dan bawah. Simpul kiri dan kanan pada baris tengah bertetangga dengan simpul atas dan bawah yang terdekat dengannya.
  1. Temukan subgraf dengan jumlah sisi paling sedikit yang tetap terhubung dan memuat semua simpul.
    🔗
    🔗
  2. Temukan subgraf dengan jumlah sisi paling banyak yang tidak memuat siklus.
    🔗
    🔗
  3. Apa yang Anda perhatikan mengenai jumlah sisi pada contoh-contoh di atas? Apakah hal ini hanya kebetulan?
    🔗
    🔗
🔗
🔗
Salah satu pendekatan yang sangat berguna dan lazim dalam mempelajari teori graf adalah membatasi perhatian pada jenis graf tertentu. Sebagai contoh, Anda dapat mencoba memahami secara mendalam hanya graf lengkap atau hanya graf bipartit, alih-alih mencoba memahami semua graf sekaligus. Itulah yang akan kita lakukan sekarang, dengan mempelajari pohon. Pada akhir bagian ini, semoga kita memahami kelas graf ini dengan lebih baik dan mengetahui mengapa pohon cukup penting untuk dibahas dalam bagian tersendiri.
🔗

Definisi 2.2.1. Pohon dan Hutan.

Pohon adalah graf terhubung yang tidak memuat siklus.
 4 
Definisi ini kadang dinyatakan sebagai “pohon adalah graf terhubung yang asiklik;” kata “asiklik” hanyalah istilah lain untuk “tidak memuat siklus.”
🔗
Hutan adalah graf yang tidak memuat siklus. Perhatikan bahwa hutan yang terhubung merupakan pohon.
🔗
🔗
Apakah definisi di atas sesuai dengan intuisi Anda mengenai graf yang layak disebut pohon? Cobalah memikirkan beberapa contoh pohon dan pastikan semuanya memenuhi definisi tersebut. Perlu diingat bahwa meskipun pohon yang kita pelajari dalam teori graf berkaitan dengan pohon yang mungkin Anda jumpai dalam bidang lain, kesesuaiannya tidak selalu tepat. Sebagai contoh, dalam antropologi, Anda mungkin mempelajari silsilah keluarga seperti berikut,
🔗
Silsilah keluarga dengan “Saya” di bagian atas, bercabang ke kiri bawah menuju “Ibu” dan ke kanan bawah menuju “Ayah”. “Ibu” memiliki cabang menuju “Nenek dari pihak ibu” dan “Kakek dari pihak ibu”. “Ayah” memiliki cabang menuju “Nenek dari pihak ayah” dan “Kakek dari pihak ayah”.
Sejauh ini tidak ada masalah, tetapi walaupun kakek dan nenek Anda (mungkin) tidak memiliki hubungan darah, jika ditelusuri cukup jauh ke masa lampau, kemungkinan besar mereka memiliki suatu leluhur bersama. Jika pohon tersebut ditelusuri dari Anda menuju leluhur bersama itu, lalu turun melalui kakek atau nenek Anda yang lain, akan terbentuk siklus sehingga graf tersebut bukan lagi pohon.
🔗
Anda mungkin juga pernah menjumpai sesuatu yang disebut pohon keputusan (misalnya algoritma untuk menentukan apakah suatu deret konvergen atau divergen). Pohon semacam ini pun terkadang memuat siklus, karena keputusan pada satu simpul dapat membawa Anda kembali ke langkah sebelumnya.
🔗
Kedua contoh pohon di atas juga memiliki ciri lain yang patut disebutkan: simpul-simpul pada pohon memiliki urutan yang jelas. Definisi pohon tidak mencakup struktur tambahan ini, tetapi kita dapat memberlakukannya dengan meninjau pohon berakar, yaitu pohon dengan satu simpul yang ditetapkan sebagai akar. Kita akan membahas pohon semacam ini secara lebih terperinci nanti dalam bagian ini.
🔗
Dalam bagian ini, kita akan menyelidiki beberapa sifat dasar pohon, yang menjadi pengantar yang sangat baik untuk menulis pembuktian tentang graf. Kita juga akan meninjau jenis pohon khusus yang disebut pohon merentang, yaitu pohon yang memuat semua simpul suatu graf terhubung. Terakhir, kita akan meninjau pohon berakar secara singkat.
🔗

Lembar Kerja Kegiatan Pratinjau

1.
Ambillah selembar kertas dan gambarlah 8 simpul yang tersusun melingkar.
🔗
Delapan simpul tersusun melingkar tanpa sisi.
Kita akan menambahkan sisi-sisi pada graf ini sesuai beberapa persyaratan.
🔗
(a)
Pertama, tambahkan sesedikit mungkin sisi agar graf yang dihasilkan terhubung. Artinya, harus terdapat lintasan di antara setiap pasangan simpul (tentu saja sebuah lintasan dapat menggunakan lebih dari satu sisi).
🔗
Berapa banyak sisi pada graf yang Anda gambar?
🔗
🔗
(b)
Apakah graf yang Anda peroleh merupakan pohon?
🔗
  • Ya, karena graf terhubung dan tidak memuat siklus
    🔗
    🔗
  • Tidak, graf memuat siklus
    🔗
    🔗
  • Tidak, graf tidak terhubung
    🔗
    🔗
  • Tidak, graf tidak terhubung dan memuat siklus
    🔗
    🔗
🔗
🔗
(c)
Sekarang mulailah kembali dengan graf kosong. Kali ini, tambahkan sebanyak mungkin sisi dengan syarat graf yang dihasilkan tidak memuat siklus.
🔗
Berapa banyak sisi pada graf yang Anda gambar?
🔗
🔗
(d)
Apakah graf yang Anda peroleh merupakan pohon?
🔗
  • Ya, karena graf terhubung dan tidak memuat siklus
    🔗
    🔗
  • Tidak, graf memuat siklus
    🔗
    🔗
  • Tidak, graf tidak terhubung
    🔗
    🔗
  • Tidak, graf tidak terhubung dan memuat siklus
    🔗
    🔗
🔗
🔗
🔗
🔗
🔗

Subbagian Sifat-Sifat Pohon

Kita ingin benar-benar memahami pohon. Artinya, kita perlu menemukan sifat-sifat pohon: apa yang membuatnya khusus dan hal khusus apa yang dimilikinya.
🔗
Pohon adalah graf terhubung tanpa siklus. Adakah hal lain yang dapat kita katakan? Akan berguna jika terdapat syarat lain yang ekuivalen bagi suatu graf untuk menjadi pohon. Dengan kata lain, kita ingin mengetahui apakah ada sifat teoretis graf yang dimiliki semua pohon, dan mungkin bahkan hanya dimiliki pohon.
🔗
Untuk memperoleh gambaran tentang hal-hal yang dapat kita nyatakan, kita akan meninjau tiga proposisi tentang pohon. Proposisi-proposisi ini juga menggambarkan teknik pembuktian penting yang berlaku bagi graf secara umum, tetapi kebetulan sedikit lebih mudah diterapkan pada pohon.
🔗
Proposisi pertama memberikan definisi alternatif bagi pohon. Artinya, proposisi ini memberikan syarat perlu dan cukup agar suatu graf merupakan pohon.
🔗

Bukti.

Ini merupakan pernyataan “jika dan hanya jika”, sehingga kita harus membuktikan dua implikasi. Kita mulai dengan membuktikan bahwa jika \(T\) merupakan pohon, maka terdapat lintasan tunggal di antara setiap pasangan simpul berbeda.
🔗
Asumsikan \(T\) merupakan pohon, dan misalkan \(u\) serta \(v\) merupakan simpul yang berbeda (jika \(T\) hanya memiliki satu simpul, kesimpulannya terpenuhi secara otomatis). Untuk menunjukkan bahwa terdapat lintasan tunggal di antara \(u\) dan \(v\text{,}\) kita harus menunjukkan dua hal: terdapat suatu lintasan, dan tidak terdapat lebih dari satu lintasan. Hal pertama berlaku secara langsung; karena \(T\) merupakan pohon, pohon tersebut terhubung, sehingga terdapat lintasan di antara setiap pasangan simpul.
🔗
Untuk menunjukkan bahwa lintasan tersebut tunggal, andaikan terdapat dua lintasan di antara \(u\) dan \(v\text{,}\) lalu kita peroleh kontradiksi. Kedua lintasan mungkin berawal dengan cara yang sama, tetapi karena keduanya berbeda, terdapat simpul pertama \(u'\) yang setelahnya kedua lintasan berpisah. Namun, karena kedua lintasan berakhir di \(v\text{,}\) terdapat simpul pertama setelah \(u'\) yang kembali dimiliki keduanya; sebut simpul itu \(v'\text{.}\) Sekarang tinjau kedua lintasan dari \(u'\) ke \(v'\text{.}\) Jika digabungkan, keduanya membentuk siklus, yang bertentangan dengan asumsi bahwa \(T\) merupakan pohon.
🔗
Sekarang kita meninjau konversnya: Jika terdapat lintasan tunggal di antara setiap pasangan simpul berbeda pada \(T\text{,}\) maka \(T\) merupakan pohon. Jadi, asumsikan hipotesis berikut: Terdapat lintasan tunggal di antara setiap pasangan simpul berbeda pada \(T\text{.}\) Untuk membuktikan bahwa \(T\) merupakan pohon, kita harus menunjukkan bahwa pohon tersebut terhubung dan tidak memuat siklus.
🔗
Bagian pertama mudah: \(T\) terhubung karena terdapat lintasan di antara setiap pasangan simpul. Untuk menunjukkan bahwa \(T\) tidak memiliki siklus, demi memperoleh kontradiksi kita asumsikan bahwa graf tersebut memiliki suatu siklus. Misalkan \(u\) dan \(v\) merupakan dua simpul berbeda pada suatu siklus dari \(T\text{.}\) Karena kita dapat berpindah dari \(u\) ke \(v\) dengan mengikuti siklus searah atau berlawanan arah jarum jam, terdapat dua lintasan dari \(u\) ke \(v\text{,}\) yang bertentangan dengan asumsi kita.
🔗
Kita telah membuktikan kedua arah, sehingga pembuktian selesai.
🔗
🔗
Bacalah pembuktian di atas dengan sangat cermat. Perhatikan bahwa kedua arahnya memiliki dua bagian: keberadaan lintasan dan ketunggalan lintasan (yang berkaitan dengan tidak adanya siklus). Dalam kasus ini, kedua bagian tersebut benar-benar terpisah. Bahkan, jika kita hanya meninjau graf tanpa siklus (hutan), kita tetap dapat menjalankan bagian pembuktian yang membahas ketunggalan lintasan di antara simpul-simpul, meskipun lintasan di antara simpul-simpul tersebut mungkin tidak ada.
🔗
Pengamatan ini memungkinkan kita menyatakan korolari berikut.
 5 
Korolari merupakan jenis pernyataan yang dapat dibuktikan, seperti proposisi atau teorema, tetapi mengikuti secara langsung dari pernyataan lain yang telah ditetapkan atau dari pembuktiannya.
🔗
Kita tidak memberikan pembuktian korolari ini (bagaimanapun juga, korolari tersebut seharusnya mengikuti langsung dari proposisi), tetapi sebagai latihan, Anda diminta memberikan pembuktian yang cermat dalam bagian latihan. Ketika melakukannya, cobalah menggunakan pembuktian melalui kontraposisi alih-alih pembuktian dengan kontradiksi.
🔗
Proposisi kedua memberi tahu kita bahwa semua pohon memiliki daun: simpul berderajat satu.
🔗

Bukti.

Kita memberikan pembuktian dengan kontradiksi. Misalkan \(T\) merupakan pohon dengan sedikitnya dua simpul, dan andaikan, bertentangan dengan pernyataan yang hendak dibuktikan, bahwa tidak terdapat dua simpul berderajat satu.
🔗
Misalkan \(P\) merupakan lintasan terpanjang yang mungkin dalam \(T\text{.}\) Misalkan \(u\) dan \(v\) merupakan kedua ujung lintasan tersebut. Karena \(T\) tidak memiliki dua simpul berderajat satu, sedikitnya salah satu dari kedua ujung ini harus berderajat dua atau lebih. Misalkan simpul tersebut adalah \(u\text{.}\) Kita mengetahui bahwa \(u\) bertetangga dengan suatu simpul pada lintasan \(P\text{,}\) tetapi simpul itu juga harus bertetangga dengan simpul lain; sebut simpul tersebut \(u'\text{.}\)
🔗
Di manakah \(u'\text{?}\) Simpul tersebut tidak mungkin merupakan simpul pada \(P\text{,}\) sebab jika demikian, akan terdapat dua lintasan berbeda dari \(u\) ke \(u'\text{:}\) sisi di antara keduanya dan bagian awal \(P\) (hingga \(u'\)). Namun, \(u'\) juga tidak mungkin berada di luar \(P\text{,}\) sebab jika demikian, akan terdapat lintasan dari \(u'\) ke \(v\) yang lebih panjang daripada \(P\text{,}\) padahal lintasan semula memiliki panjang maksimum.
🔗
Kontradiksi ini membuktikan bahwa harus terdapat sedikitnya dua simpul berderajat satu. Bahkan, kita dapat mengatakan lebih banyak: \(u\) dan \(v\) keduanya harus berderajat satu.
🔗
🔗
Proposisi tersebut sangat berguna ketika membuktikan pernyataan tentang pohon, sebab pernyataan mengenai pohon sering kita buktikan dengan induksi. Teknik pembuktian ini akan kita pelajari secara menyeluruh dalam Subbab 4.5, tetapi untuk saat ini kita hanya perlu memahami bahwa membandingkan suatu pohon dengan pohon-pohon yang lebih kecil itu berguna. Untuk menunjukkan bahwa sesuatu berlaku bagi pohon dengan \(v\) simpul, kita akan mengasumsikan bahwa hal tersebut berlaku bagi semua pohon dengan \(v-1\) simpul. Dengan menghapus satu simpul berderajat 1, kita memperoleh pohon yang lebih kecil ini; selanjutnya kita hanya perlu menunjukkan bahwa mengembalikan simpul tersebut tidak merusak sifat yang sedang dibuktikan.
🔗
Adakah pohon yang memiliki tepat 7 simpul dan 7 sisi? Cobalah menggambarnya. Mungkinkah pohon dengan 7 simpul hanya memiliki 5 sisi? Ada alasan kuat mengapa gambar-gambar tersebut tampaknya mustahil dibuat.
🔗
Kita akan membuktikan bahwa proposisi ini benar untuk semua nilai yang mungkin dari \(v \ge 1\text{.}\) Perhatikan bahwa jika \(v = 1\text{,}\) pohon tersebut harus memiliki \(0\) sisi, sehingga memang \(e = v-1\text{.}\) Selanjutnya kita dapat memeriksa pohon dengan \(v=2\) simpul (hanya ada satu, dan pohon itu memiliki \(e = 1 = v-1\) sisi), lalu semua pohon dengan \(v=3\) simpul, kemudian \(v=4\text{,}\) dan seterusnya. Namun, cara itu tidak akan pernah selesai. Benar-benar tidak pernah!
🔗
Sebagai gantinya, kita akan menggunakan suatu bentuk pembuktian dengan kontradiksi yang disebut metode penjahat minimal. Kita akan mengasumsikan bahwa proposisi tersebut tidak benar (seperti ketika memulai pembuktian dengan kontradiksi pada umumnya). Artinya, ada suatu pohon terkecil yang tidak memenuhi proposisi tersebut. Jika contoh penyangkal terkecil ini (yakni, penjahat minimal) memiliki \(v\) simpul, kita memperoleh jaminan bahwa semua pohon dengan \(v-1\) simpul bukan contoh penyangkal. Mari kita lihat bagaimana gagasan ini bekerja.
🔗

Bukti.

Untuk memperoleh kontradiksi, andaikan proposisi tersebut tidak benar bagi semua pohon. Misalkan \(T\) adalah pohon yang tidak memenuhi proposisi itu dan memiliki banyak simpul paling sedikit di antara semua contoh penyangkal. Misalkan \(v\) adalah banyak simpul pada \(T\text{.}\)
🔗
Karena satu-satunya pohon dengan satu simpul memiliki nol sisi, pohon tersebut tidak mungkin merupakan \(T\text{.}\) Jadi, kita dapat mengasumsikan \(v \ge 2\text{.}\) Secara khusus, dari Proposisi 2.2.4 kita mengetahui bahwa \(T\) harus memuat sedikitnya satu simpul berderajat 1; namakan simpul itu \(v_0\text{.}\)
🔗
Misalkan \(T'\) adalah pohon yang diperoleh dengan menghapus \(v_0\) dari \(T\) (beserta sisi yang terkait dengannya). Karena yang kita hapus adalah sebuah daun, \(T'\) tetap merupakan pohon (lintasan unik di antara setiap pasangan simpul pada \(T'\) sama dengan lintasan unik di antara pasangan tersebut pada \(T\)).
🔗
Sekarang \(T'\) memiliki \(v-1\) simpul. Karena \(T\) merupakan pohon terkecil yang tidak memenuhi proposisi, kita mengetahui bahwa proposisi itu benar bagi \(T'\text{.}\) Jadi, banyak sisi pada \(T'\) harus satu lebih sedikit daripada banyak simpulnya; dengan kata lain, \(T'\) memiliki \(v-2\) sisi. Akan tetapi, \(T\) memiliki satu sisi lebih banyak daripada \(T'\text{,}\) sehingga pohon tersebut memiliki \(v-1\) sisi. Hal ini bertentangan dengan asumsi bahwa \(T\) tidak memenuhi proposisi dan dengan demikian menyelesaikan pembuktian kita.
🔗
🔗
🔗

Subbagian Pohon Merentang

Salah satu kelebihan pohon ialah tersedianya beberapa cara sederhana untuk menelusuri simpul-simpulnya. Jika suatu graf terhubung bukan pohon, kita tetap dapat menggunakan algoritma penelusuran ini apabila kita menemukan sebuah subgraf yang merupakan pohon.
🔗
Pertama-tama, kita perlu memastikan bahwa gagasan ini masuk akal. Untuk sembarang graf terhubung \(G\text{,}\) apakah selalu ada subgraf yang merupakan pohon? Sebenarnya, pertanyaan itu terlalu mudah: kita dapat mengambil satu simpul saja dari \(G\text{.}\) Jika subgraf tersebut hendak kita gunakan sebagai panduan untuk mengunjungi semua simpul, kita memerlukan subgraf yang memuat seluruh simpul. Pohon seperti itu disebut pohon merentang.
🔗

Definisi 2.2.6.

Untuk suatu graf terhubung \(G\text{,}\) pohon merentang dari \(G\) adalah subgraf dari \(G\) yang merupakan pohon dan memuat semua simpul \(G\text{.}\)
🔗
🔗
Ternyata setiap graf terhubung memiliki pohon merentang (dan biasanya memiliki banyak pohon merentang).
🔗
Bagaimana kita mengetahuinya? Kita dapat memberikan algoritma untuk menemukan pohon merentang! Mulailah dengan graf terhubung \(G\text{.}\) Jika tidak terdapat siklus, \(G\) sudah merupakan pohon dan kita selesai. Jika terdapat siklus, misalkan \(e\) adalah sembarang sisi pada siklus tersebut dan tinjau graf baru \(G_1 = G - e\) (yakni, graf yang diperoleh dengan menghapus \(e\)). Graf ini tetap terhubung: karena \(e\) merupakan bagian dari suatu siklus, terdapat sedikitnya dua lintasan di antara kedua simpul ujungnya. Sekarang ulangi proses tersebut. Jika \(G_1\) tidak memiliki siklus, kita selesai; jika tidak, definisikan \(G_2\) sebagai \(G_1 - e_1\text{,}\) dengan \(e_1\) suatu sisi pada siklus di \(G_1\text{.}\) Teruskan proses ini. Proses tersebut pada akhirnya harus berhenti karena hanya ada berhingga banyak sisi yang dapat dihapus. Hasilnya merupakan pohon dan, karena tidak ada simpul yang pernah kita hapus, merupakan pohon merentang.
🔗
Ini bukan satu-satunya algoritma untuk menemukan pohon merentang. Kita juga dapat memulai dengan graf kosong, lalu menambahkan sisi-sisi milik \(G\) selama penambahan tersebut tidak membentuk siklus. Ada beberapa pilihan mengenai sisi mana yang ditambahkan terlebih dahulu: kita dapat selalu menambahkan sisi yang bertetangga dengan sisi-sisi yang telah ditambahkan (tentu saja setelah sisi pertama), atau menambahkannya menurut urutan lain. Pohon merentang yang akhirnya diperoleh bergantung pada pilihan-pilihan tersebut.
🔗

Contoh 2.2.8.

Temukan dua pohon merentang yang berbeda dari graf berikut.
🔗
Sebuah graf dengan tujuh simpul yang tersusun dalam tiga baris: dua di atas, tiga di tengah, dan dua di bawah. Keempat simpul pada baris atas dan bawah dihubungkan oleh sisi-sisi yang membentuk persegi. Simpul di pusat baris tengah bertetangga dengan keempat simpul pada baris atas dan bawah. Simpul di sebelah kiri dan kanan baris tengah masing-masing bertetangga dengan simpul atas dan bawah yang terdekat.
Penyelesaian.
Berikut dua pohon merentangnya.
🔗
Sebuah graf dengan tujuh simpul yang tersusun dalam tiga baris: dua di atas, tiga di tengah, dan dua di bawah. Simpul kiri-tengah bertetangga dengan simpul kiri-atas. Simpul kiri-atas bertetangga dengan simpul di pusat baris tengah dan dengan simpul kanan-atas. Simpul kanan-atas bertetangga dengan simpul kanan-tengah, yang bertetangga dengan simpul kanan-bawah, yang selanjutnya bertetangga dengan simpul kiri-bawah. Jadi, seluruhnya terdapat 6 sisi.
Sebuah graf dengan tujuh simpul yang tersusun dalam tiga baris: dua di atas, tiga di tengah, dan dua di bawah. Simpul di pusat baris tengah bertetangga dengan keempat simpul pada baris atas dan bawah. Setiap simpul pada baris atas bertetangga dengan simpul pada sisi yang sama di baris tengah. Jadi, seluruhnya terdapat 6 sisi.
🔗
🔗
Meskipun tidak akan membahasnya secara terperinci, algoritma-algoritma ini biasanya diterapkan pada graf berbobot. Di sini setiap sisi diberi suatu bobot atau biaya. Tujuannya adalah menemukan pohon merentang dengan jumlah bobot sekecil mungkin. Pohon seperti itu disebut pohon merentang minimum. Pada dasarnya, pencarian pohon merentang minimum menggunakan algoritma yang sama dengan yang diuraikan di atas, tetapi ketika memilih sisi untuk ditambahkan, kita selalu memilih sisi dengan bobot terkecil (atau ketika menghapus sisi, kita selalu menghapus sisi dengan bobot terbesar).
 6 
Jika kita menambahkan sisi berbobot terkecil yang bertetangga dengan sisi-sisi yang telah ditambahkan, kita menjalankan algoritma Prim. Jika kita menambahkan sisi berbobot terkecil di seluruh graf, kita mengikuti algoritma Kruskal.
🔗
🔗

Subbagian Pohon Berakar

Sejauh ini, kita hanya memandang pohon sebagai suatu jenis graf. Akan tetapi, penambahan struktur tertentu pada pohon sering membantu kita memecahkan masalah. Data pun sering disusun seperti pohon. Sebagai contoh, buku ini memiliki struktur pohon: gambarlah satu simpul untuk buku itu sendiri. Kemudian gambarlah satu simpul untuk setiap bab, dan hubungkan setiap simpul tersebut dengan simpul buku. Di bawah setiap bab, gambarlah satu simpul untuk setiap subbab, lalu hubungkan simpul itu dengan bab yang memuatnya. Graf tersebut tidak memiliki siklus; graf itu merupakan pohon, tetapi pohon dengan hierarki yang jelas. Hierarki ini tidak akan ada jika kita tidak menetapkan “simpul buku” sebagai bagian “teratas”.
🔗
Begitu salah satu simpul pada pohon ditetapkan sebagai akar, setiap simpul lain pada pohon tersebut dapat dicirikan berdasarkan posisinya terhadap akar. Hal ini dimungkinkan karena terdapat lintasan unik di antara setiap dua simpul pada pohon. Jadi, dari sembarang simpul, kita dapat kembali ke akar melalui tepat satu cara. Struktur ini juga memungkinkan kita menjelaskan hubungan di antara simpul-simpul yang berbeda pada pohon berakar.
🔗
Jika dua simpul bertetangga, salah satunya disebut induk dari simpul yang lain, sedangkan simpul yang lain disebut anak dari simpul induk tersebut. Di antara keduanya, simpul induk adalah simpul yang lebih dekat dengan akar. Jadi, akar suatu pohon merupakan simpul induk, tetapi bukan anak dari simpul mana pun (dan bersifat unik dalam hal ini: setiap simpul bukan-akar memiliki tepat satu induk).
🔗
Tidak mengherankan bahwa anak dari anak suatu simpul disebut cucu dari simpul tersebut (dan simpul tersebut merupakan kakek atau nenek dari cucunya). Secara lebih umum, simpul \(v\) disebut keturunan dari simpul \(u\) apabila \(u\) terletak pada lintasan dari \(v\) menuju akar. Dalam hal ini, \(u\) disebut leluhur dari \(v\text{.}\)
🔗
Pada hampir semua pohon (tepatnya, pada semua pohon kecuali lintasan yang salah satu ujungnya dijadikan akar), akan terdapat pasangan simpul yang tidak satu pun merupakan keturunan dari yang lain. Kita dapat menganggapnya sebagai sepupu atau saudara. Tepatnya, simpul \(u\) dan \(v\) disebut saudara apabila keduanya memiliki induk yang sama. Perhatikan bahwa simpul-simpul saudara tidak pernah bertetangga (dapatkah Anda menjelaskan alasannya?).
🔗

Contoh 2.2.9.

Perhatikan pohon berikut.
🔗
Sebuah pohon berlabel. Di tengah gambar terdapat simpul e, yang bertetangga dengan f (kanan-atas), g (kanan-bawah), d (kiri-bawah), c (kiri-tengah), dan b (kiri-atas). Simpul c juga bertetangga dengan simpul a di sebelah kirinya. Simpul f bertetangga dengan h di sebelah kanannya dan i di sebelah kanan-bawahnya.
Jika simpul \(f\) kita tetapkan sebagai akar, maka \(e\text{,}\) \(h\text{,}\) dan \(i\) adalah anak-anak dari \(f\) dan saling bersaudara. Hal lain yang dapat kita katakan, antara lain, ialah bahwa \(a\) merupakan anak dari \(c\) dan keturunan dari \(f\text{.}\) Simpul \(g\) merupakan keturunan dari \(f\text{;}\) bahkan, simpul tersebut adalah cucu dari \(f\text{.}\) Simpul \(g\) dan \(d\) bersaudara karena keduanya memiliki induk yang sama, yaitu \(e\text{.}\)
🔗
Perhatikan bagaimana hubungan-hubungan ini berubah jika kita memilih simpul lain sebagai akar. Jika \(a\) merupakan akar, satu-satunya anaknya adalah \(c\text{,}\) yang juga hanya memiliki satu anak, yaitu \(e\text{.}\) Dengan demikian, \(f\) menjadi anak dari \(e\) (bukan sebaliknya), dan \(f\) merupakan keturunan dari \(a\text{,}\) bukan leluhurnya. Sekarang \(f\) dan \(g\) bersaudara.
🔗
🔗
Seluruh istilah kekerabatan ini membantu kita menjelaskan cara menelusuri sebuah pohon. Penelusuran pohon—mengunjungi setiap simpul menurut suatu urutan—merupakan langkah penting dalam banyak algoritma. Meskipun suatu pohon belum berakar, kita selalu dapat membentuk pohon berakar dengan memilih sembarang simpul sebagai akar. Contoh berikut menunjukkan manfaatnya.
🔗

Contoh 2.2.10.

Jelaskan mengapa setiap pohon merupakan graf bipartit.
🔗
Penyelesaian.
Untuk menunjukkan bahwa suatu graf bersifat bipartit, kita harus membagi simpul-simpulnya ke dalam dua himpunan, \(A\) dan \(B\text{,}\) sedemikian sehingga tidak ada dua simpul dalam himpunan yang sama yang bertetangga. Algoritma berikut melakukan tepat hal tersebut.
🔗
Tetapkan sembarang simpul sebagai akar dan masukkan simpul tersebut ke dalam himpunan \(A\text{.}\) Selanjutnya, masukkan semua anak dari akar ke dalam himpunan \(B\text{.}\) Tidak ada dua simpul anak ini yang bertetangga (mereka saling bersaudara), sehingga sejauh ini pembagian kita benar. Sekarang masukkan ke dalam \(A\) setiap anak dari setiap simpul dalam \(B\) (yakni, setiap cucu dari akar). Lanjutkan hingga semua simpul telah dimasukkan ke dalam salah satu himpunan, dengan bergantian antara \(A\) dan \(B\) pada setiap “generasi”. Dengan kata lain, suatu simpul berada dalam himpunan \(B\) jika dan hanya jika simpul tersebut merupakan anak dari simpul dalam himpunan \(A\text{.}\)
🔗
🔗
🔗
Kunci pembagian pohon pada contoh tersebut adalah mengetahui simpul mana yang selanjutnya harus dimasukkan ke suatu himpunan. Kita memilih untuk mengunjungi semua simpul pada generasi yang sama sebelum mengunjungi simpul mana pun pada generasi berikutnya. Cara ini biasanya disebut pencarian melebar. Istilah “pencarian” digunakan karena penelusuran pohon sering dilakukan untuk mencari simpul dengan sifat tertentu.
🔗
Sebaliknya, kita juga dapat membagi pohon menurut urutan yang berbeda. Mulailah dari akar dan masukkan akar ke dalam \(A\text{.}\) Kemudian cari salah satu anak akar untuk dimasukkan ke dalam \(B\text{.}\) Selanjutnya, cari satu anak dari simpul tersebut untuk dimasukkan ke dalam \(A\text{,}\) lalu cari anaknya untuk dimasukkan ke dalam \(B\text{,}\) dan seterusnya. Ketika kita mencapai simpul tanpa anak, mundurlah ke simpul induknya dan periksa apakah simpul induk tersebut memiliki anak lain. Jadi, kita bergerak menjauhi akar secepat mungkin, lalu menelusuri kembali lintasan hingga dapat bergerak maju lagi. Cara ini disebut pencarian mendalam.
🔗
Penjelasan algoritmis ini dapat berfungsi sebagai pembuktian bahwa setiap pohon bersifat bipartit, meskipun kita tetap harus membuktikan dengan teliti bahwa algoritmanya benar. Latihan-latihan akan meminta Anda menggunakan pendekatan lain, yaitu induksi, untuk membuktikan bahwa semua pohon bersifat bipartit.
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Misalkan \(T\) adalah pohon dengan 10 simpul. Manakah di antara pernyataan berikut yang harus benar mengenai \(T\text{?}\) Pilih semua jawaban yang berlaku.
🔗
  • \(T\) memiliki lintasan unik di antara setiap pasangan simpul.
    🔗
  • Jika sembarang sisi dihapus dari \(T\text{,}\) graf yang dihasilkan menjadi tidak terhubung.
    🔗
  • Jika sembarang sisi ditambahkan di antara dua simpul pada \(T\) yang sebelumnya tidak bertetangga, graf yang dihasilkan memiliki siklus.
    🔗
  • \(T\) memiliki tepat dua simpul berderajat satu.
    🔗
🔗

2.

Jika suatu pohon memiliki 20 simpul, berapa banyak sisi yang dimilikinya?
🔗
Banyak sisi:
🔗
🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca subbab ini? Tuliskan sedikitnya satu pertanyaan mengenai isi subbab ini yang membuat Anda ingin tahu lebih jauh.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Apakah pernyataan-pernyataan berikut benar atau salah?
🔗
  1. Terdapat graf terhubung yang memiliki tepat satu pohon merentang.
    🔗
    🔗
  2. Jika suatu graf memiliki dua simpul lebih banyak daripada sisinya, maka graf tersebut tidak terhubung.
    🔗
    🔗
  3. Setiap graf bipartit merupakan pohon.
    🔗
    🔗
  4. Setiap hutan terhubung merupakan pohon.
    🔗
    🔗
  5. Jika suatu graf memiliki tepat satu simpul lebih banyak daripada sisinya, maka graf tersebut merupakan pohon.
    🔗
    🔗
🔗
🔗

2.

Sebuah hutan memiliki 50 simpul dan 44 sisi. Berapa banyak komponen terhubung yang dimiliki graf tersebut?
🔗
🔗

3.

Sebuah graf terhubung dengan 12 simpul memiliki 17 sisi. Tanpa mengetahui graf khusus yang dimaksud, berapakah jumlah sisi minimum dan maksimum yang dapat Anda hapus untuk memperoleh sebuah pohon merentang?
🔗
Jumlah sisi minimum yang harus dihapus:
🔗
Jumlah sisi maksimum yang harus dihapus:
🔗
🔗

4.

Derajat rata-rata sebuah pohon adalah 1.96 (artinya, jika Anda menjumlahkan derajat semua simpul lalu membaginya dengan banyaknya simpul, hasilnya adalah 1.96).
🔗
Berapa banyak simpul yang dimiliki pohon tersebut?
🔗
🔗

5.

Sebuah pohon memiliki sejumlah daun (simpul berderajat 1) dan empat simpul bukan daun. Derajat keempat simpul bukan daun tersebut adalah 10, 7, 4, dan 2. Berapa banyak daun yang dimiliki pohon tersebut?
🔗
Jumlah daun minimum yang mungkin:
🔗
Jumlah daun maksimum yang mungkin:
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Manakah di antara graf-graf berikut yang merupakan pohon?
  1. \(G = (V, E)\) dengan \(V = \{a, b, c, d, e\}\) dan \(E = \{\{a, b\}, \{a,e\}, \{b, c\}, \{c,d\}, \{d,e\} \}\)
    🔗
    🔗
  2. \(G = (V, E)\) dengan \(V = \{a, b, c, d, e\}\) dan \(E = \{\{a, b\}, \{b, c\}, \{c,d\}, \{d,e\}\}\)
    🔗
    🔗
  3. \(G = (V, E)\) dengan \(V = \{a, b, c, d, e\}\) dan \(E = \{\{a, b\}, \{a, c\}, \{a,d\}, \{a,e\}\}\)
    🔗
    🔗
  4. \(G = (V, E)\) dengan \(V = \{a, b, c, d, e\}\) dan \(E = \{\{a, b\}, \{a, c\}, \{d,e\}\}\)
    🔗
    🔗
🔗
🔗

2.

Untuk setiap barisan derajat di bawah ini, tentukan apakah barisan tersebut selalu merupakan, tidak mungkin merupakan, atau mungkin merupakan barisan derajat suatu pohon. Ingatlah bahwa barisan derajat mencantumkan derajat (banyaknya sisi yang berinsiden dengan simpul) dari semua simpul dalam graf menurut urutan tak naik.
  1. \(\displaystyle (4,1,1,1,1)\)
    🔗
    🔗
  2. \(\displaystyle (3,3,2,1,1)\)
    🔗
    🔗
  3. \(\displaystyle (2,2,2,1,1)\)
    🔗
    🔗
  4. \(\displaystyle (4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1)\)
    🔗
    🔗
🔗
🔗

3.

Untuk setiap barisan derajat di bawah ini, tentukan apakah barisan tersebut selalu merupakan, tidak mungkin merupakan, atau mungkin merupakan barisan derajat suatu pohon. Berikan alasan bagi jawaban Anda.
  1. \(\displaystyle (3, 3, 2, 2, 2)\)
    🔗
    🔗
  2. \(\displaystyle (3, 2, 2, 1, 1, 1)\)
    🔗
    🔗
  3. \(\displaystyle (3, 3, 3, 1, 1, 1)\)
    🔗
    🔗
  4. \(\displaystyle (4, 4, 1, 1, 1, 1, 1, 1)\)
    🔗
    🔗
🔗
Petunjuk.
Berhati-hatilah: graf-graf tersebut mungkin tidak terhubung.
🔗
🔗
🔗

4.

Misalkan Anda memiliki graf dengan \(v\) simpul dan \(e\) sisi yang memenuhi \(v = e+1\text{.}\) Apakah graf tersebut harus merupakan pohon? Buktikan jawaban Anda.
🔗
Petunjuk.
Cobalah gunakan Latihan 2.
🔗
🔗
🔗

5.

Buktikan bahwa sembarang graf (tidak harus berupa pohon) dengan \(v\) simpul dan \(e\) sisi yang memenuhi \(v \gt e+1\) TIDAK akan terhubung.
🔗
Petunjuk.
Cobalah bukti dengan kontradiksi dan tinjau suatu pohon merentang dari graf tersebut.
🔗
🔗
🔗

6.

Jika graf \(G\) dengan \(v\) simpul dan \(e\) sisi terhubung serta memenuhi \(v \lt e+1\text{,}\) apakah graf tersebut harus memuat siklus? Buktikan jawaban Anda.
🔗
🔗

7.

Kita mendefinisikan hutan sebagai graf yang tidak memiliki siklus.
  1. Jelaskan mengapa istilah ini tepat. Artinya, jelaskan mengapa hutan merupakan gabungan dari pohon-pohon.
    🔗
    🔗
  2. Misalkan \(F\) adalah hutan yang terdiri atas \(m\) pohon dan \(v\) simpul. Berapa banyak sisi yang dimiliki \(F\text{?}\) Jelaskan.
    🔗
    🔗
  3. Buktikan bahwa sembarang graf \(G\) dengan \(v\) simpul dan \(e\) sisi yang memenuhi \(v \lt e+1\) harus memuat siklus (yaitu, bukan hutan).
    🔗
    🔗
🔗
Petunjuk.
Untuk bagian (b), mencoba beberapa contoh sederhana seharusnya membantu Anda menemukan rumusnya. Setelah itu, Anda hanya perlu membuktikan bahwa rumus tersebut benar.
🔗
🔗
🔗

8.

Berikan bukti yang cermat untuk Akibat 2.2.3: Suatu graf merupakan hutan jika dan hanya jika terdapat paling banyak satu lintasan di antara setiap pasangan simpul. Gunakan bukti melalui kontraposisi (bukan bukti dengan kontradiksi) untuk kedua arah.
🔗
Petunjuk.
Dengan mencermati bukti Proposisi 2.2.2, Anda akan memperoleh hampir semua hal yang diperlukan. Namun, pastikan Anda hanya memberikan bagian-bagian yang relevan dan berhati-hatilah agar tidak menggunakan bukti dengan kontradiksi.
🔗
🔗
🔗

9.

Berikan bukti penjahat minimal yang cermat bahwa setiap pohon bersifat bipartit.
🔗
Petunjuk.
Minimalitas di sini harus dinyatakan dalam banyaknya simpul. Jika Anda memiliki contoh penyangkal minimal dan menghapus suatu simpul daun, graf yang dihasilkan akan menjadi pohon yang lebih kecil, sehingga...
🔗
🔗
🔗

10.

Perhatikan pohon yang digambar di bawah ini.
🔗
Sebuah pohon berlabel dengan sembilan simpul yang diberi label a sampai i. Simpul a, b, e, f, dan i terletak pada satu baris dan bertetangga sepanjang suatu lintasan dalam urutan tersebut dari kiri ke kanan. Simpul b bertetangga dengan c dan d yang berada di atasnya. Simpul f bertetangga dengan g dan h yang berada di atasnya.
  1. Misalkan kita menetapkan simpul \(e\) sebagai akar. Daftarkan anak, induk, dan saudara kandung dari setiap simpul. Apakah ada simpul selain \(e\) yang memiliki cucu?
    🔗
    🔗
  2. Misalkan \(e\) tidak dipilih sebagai akar. Apakah pemilihan simpul akar mengubah banyaknya anak yang dimiliki \(e\text{?}\) Bagaimana dengan banyaknya cucu? Berapa banyak masing-masing?
    🔗
    🔗
  3. Sebenarnya, pilihlah sembarang simpul pada pohon dan misalkan simpul tersebut bukan akar. Jelaskan mengapa banyaknya anak dari simpul tersebut tidak bergantung pada simpul lain mana yang menjadi akar.
    🔗
    🔗
  4. Apakah hasil pada bagian sebelumnya berlaku bagi pohon lain? Berikan contoh pohon berbeda yang memenuhi hasil tersebut. Kemudian, buktikan bahwa hasil tersebut selalu berlaku atau berikan contoh pohon yang tidak memenuhinya.
    🔗
    🔗
🔗
Petunjuk.
Jika \(e\) merupakan akar, maka \(b\) akan memiliki tiga anak (\(a\text{,}\) \(c\text{,}\) dan \(d\)); ketiganya merupakan saudara kandung dan memiliki \(b\) sebagai induk. \(a\) tidak akan memiliki anak.
🔗
Secara umum, bagaimana Anda dapat menentukan banyaknya anak yang dimiliki suatu simpul jika simpul tersebut bukan akar?
🔗
🔗
🔗

11.

Misalkan \(T\) adalah pohon berakar yang memuat simpul \(u\text{,}\) \(v\text{,}\) dan \(w\) (serta mungkin simpul-simpul lain). Buktikan bahwa jika \(w\) merupakan keturunan dari \(u\) dan \(v\text{,}\) maka \(u\) merupakan keturunan dari \(v\) atau \(v\) merupakan keturunan dari \(u\text{.}\)
🔗
🔗

12.

Kecuali jika sudah berupa pohon, suatu graf \(G\) akan memiliki beberapa pohon merentang. Seberapa mirip atau berbedakah pohon-pohon merentang tersebut?
  1. Apakah semua pohon merentang dari suatu graf harus saling isomorfik? Jelaskan alasannya atau berikan contoh penyangkal.
    🔗
    🔗
  2. Apakah semua pohon merentang dari suatu graf harus memiliki jumlah sisi yang sama? Jelaskan alasannya atau berikan contoh penyangkal.
    🔗
    🔗
  3. Apakah semua pohon merentang dari suatu graf harus memiliki jumlah daun (simpul berderajat 1) yang sama? Jelaskan alasannya atau berikan contoh penyangkal.
    🔗
    🔗
🔗
🔗

13.

Carilah semua pohon merentang dari graf di bawah ini. Berapa banyak pohon merentang berbeda yang ada? Berapa banyak pohon merentang berbeda hingga isomorfisme (artinya, jika Anda mengelompokkan semua pohon merentang berdasarkan keisomorfikannya, berapa banyak kelompok yang diperoleh)?
🔗
Sebuah graf dengan enam simpul yang diberi label a sampai f. Simpul a, b, dan c membentuk segitiga (beserta sisi-sisinya), dengan a tepat di atas b dan c di sebelah kanan keduanya. Simpul c bertetangga dengan simpul d, f, dan e, dengan d tepat di atas f dan e lebih jauh di sebelah kanan. Simpul d dan f juga bertetangga dengan e.
🔗

14.

Berikan contoh graf yang memiliki tepat 7 pohon merentang berbeda. Perhatikan bahwa beberapa atau semua pohon merentang tersebut boleh saling isomorfik.
🔗
Petunjuk.
Terdapat contoh dengan 7 sisi.
🔗
🔗
🔗

15.

Buktikan bahwa setiap graf terhubung yang bukan merupakan pohon harus memiliki setidaknya tiga pohon merentang berbeda (meskipun mungkin saling isomorfik).
🔗
Petunjuk.
Latihan sebelumnya akan membantu.
🔗
🔗
🔗

16.

Perhatikan sisi-sisi yang harus terdapat dalam setiap pohon merentang suatu graf. Apakah setiap graf harus memiliki sisi semacam itu? Berikan contoh graf yang memiliki tepat satu sisi semacam itu.
🔗
Petunjuk.
Perhatikan bahwa jika sisi semacam itu dihapus, graf akan menjadi tidak terhubung. Graf yang memiliki sisi seperti ini disebut graf terhubung-1.
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik