10410: 学习系列 —— 树上问题 —— 树上最大独立集问题 和 树上最小支配集问题
[Creator : ]
Description
树上最大独立集问题（Maximum Independent Set Problem on Trees）
在给定的树中，找到一个具有最大节点数量的独立集。独立集是指在树中选择一组节点，使得这些节点两两之间没有边相连。换句话说，任何两个选择的节点之间都不存在直接连接。
树上最小支配集问题（Minimum Dominating Set Problem on Trees）
在给定的树中，找到一个具有最小节点数量的支配集。支配集是指在树中选择一组节点，使得每个未选择的节点要么与选择的节点相邻，要么本身就是选择的节点。换句话说，每个未选择的节点要么被选择的节点支配（与之相邻），要么本身就是选择的节点。
在给定的树中，找到一个具有最大节点数量的独立集。独立集是指在树中选择一组节点，使得这些节点两两之间没有边相连。换句话说，任何两个选择的节点之间都不存在直接连接。
树上最小支配集问题（Minimum Dominating Set Problem on Trees）
在给定的树中，找到一个具有最小节点数量的支配集。支配集是指在树中选择一组节点，使得每个未选择的节点要么与选择的节点相邻，要么本身就是选择的节点。换句话说，每个未选择的节点要么被选择的节点支配（与之相邻），要么本身就是选择的节点。
Input
两个问题的目标相反：最大独立集问题追求选择尽可能多的节点，而最小支配集问题追求选择尽可能少的节点。
需要注意的是，在一棵树上，最小支配集的补集即为最大独立集。也就是说，最小支配集中的节点是覆盖了整个树的节点，而最大独立集中的节点则是不相互连接的节点。
需要注意的是，在一棵树上，最小支配集的补集即为最大独立集。也就是说，最小支配集中的节点是覆盖了整个树的节点，而最大独立集中的节点则是不相互连接的节点。