Spanning Tree

Video ini membahas tentang konsep Spanning Tree atau pohon rentangan dalam Matematika Diskrit. Spanning Tree merupakan subgraf dari graf G yang berbentuk pohon, menghubungkan semua simpul dari G dengan menggunakan busur yang diperlukan saja. Terdapat beberapa cara untuk mengkonstruksi Spanning Tree, yaitu Building Up Method dengan memilih busur satu per satu tanpa membentuk sirkuit, dan Cutting Down dengan menghilangkan busur yang membentuk lingkaran hingga membentuk pohon. Konsep ini penting karena setiap graf terhubung jika memiliki pohon rentangan, dan dapat memiliki lebih dari satu pohon rentangan.