Spanning Tree

সব vertex ঢাকে, cycle থাকে না, আর n−1 edge ব্যবহার করে — সংযোগ রাখার তাত্ত্বিক ন্যূনতম।

Edge-এ weight থাকলে minimum spanning tree (MST) হলো সবচেয়ে কম মোট weight-এর spanning tree। Kruskal (Union-Find দিয়ে) বা Prim দিয়ে বের করা হয়।

বাস্তব প্রয়োগ:

• Network design — সবচেয়ে কম তার/খরচে সব node যুক্ত করা
• Spanning Tree Protocol (STP) — Ethernet switch-এ। Switch loop broadcast storm তৈরি করে, তাই STP redundant link গুলো নিষ্ক্রিয় করে একটা tree রাখে। Link fail করলে আবার হিসাব করে একটা নিষ্ক্রিয় link চালু করে
• Clustering — MST কেটে cluster বানানো
• Image segmentation — সংলগ্ন similar pixel দল

Trade-off: tree সবচেয়ে সস্তা কিন্তু সবচেয়ে ভঙ্গুর — একটাও edge গেলে বিচ্ছিন্ন। তাই বাস্তব network-এ ইচ্ছাকৃতভাবে redundant link রাখা হয় (tree-র চেয়ে বেশি edge), আর STP-র মতো protocol runtime-এ কোনটা সক্রিয় থাকবে তা ঠিক করে।