南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第10周 独立、覆盖和支配

阿有京大赞 NANJING UNIVERSITY 第8章独立、覆盖和支配 程龚 2023/4/17

第8章 独立、覆盖和支配 程龚 2023/4/17 2

加油站选址原则测 ■选择城镇间的若干条道路，每条道路中段建一座加油站 ·赵专家：尽可能多选道路，但为避免浪费，相邻的道路原则上至多选 一条 ·钱专家：尽可能少选道路，但为确保够用，每座城镇关联的道路原则侧 上至少选一条 ●孙专家：尽可能少选道路，但每条未被选中的道路原则上至少与一条 被选中的道路相邻 eo e14 e e 6 10 e15 es e12 e1o e16 2023/4/17

n 选择城镇间的若干条道路，每条道路中段建一座加油站 l 赵专家：尽可能多选道路，但为避免浪费，相邻的道路原则上至多选 一条 l 钱专家：尽可能少选道路，但为确保够用，每座城镇关联的道路原则 上至少选一条 l 孙专家：尽可能少选道路，但每条未被选中的道路原则上至少与一条 被选中的道路相邻 2023/4/17 3 加油站选址原则

加油站选址原则 ■选择若干座城镇，每座城镇内部建一座加油站 ·李专家：尽可能多选城镇，但为避免浪费，相邻的城镇原则上至多选 一座 ·周专家：尽可能少选城镇，但为确保够用，每条道路关联的城镇原则 上至少选一座 ● 吴专家：尽可能少选城镇，但每座未被选中的城镇原则上至少与一座 被选中的城镇相邻 V4 e e e e 10 eis e es ex e12 e10 e16 11 2023/4/17

n 选择若干座城镇，每座城镇内部建一座加油站 l 李专家：尽可能多选城镇，但为避免浪费，相邻的城镇原则上至多选 一座 l 周专家：尽可能少选城镇，但为确保够用，每条道路关联的城镇原则 上至少选一座 l 吴专家：尽可能少选城镇，但每座未被选中的城镇原则上至少与一座 被选中的城镇相邻 2023/4/17 4 加油站选址原则

加油站选址原则 ■选择若干座城镇，每座城镇内部建一座加油站 ● 李专家：尽可能多选城镇，但为避免浪费，相邻的城镇原侧上至多选 一座 一独立 ·周专家：尽可能少选城镇，但为确保够用，每条道路关联的城镇原则 上至少选一座 一盖 ●吴专家：尽可能少选城镇，但每座未被选中的城镇原则上至少与一座 被选中的城镇相邻一支配 eo e14 V4 9 e e e11 3 V6 e13 e15 10 es e12 e10 e16 2023/4/17

n 选择若干座城镇，每座城镇内部建一座加油站 l 李专家：尽可能多选城镇，但为避免浪费，相邻的城镇原则上至多选 一座 ——独立 l 周专家：尽可能少选城镇，但为确保够用，每条道路关联的城镇原则 上至少选一座 ——覆盖 l 吴专家：尽可能少选城镇，但每座未被选中的城镇原则上至少与一座 被选中的城镇相邻 ——支配 2023/4/17 5 加油站选址原则

本次课的主要内容 8.1边的独立、覆盖和支配 8.2顶点的独立、覆盖和支配 2023/4/17 6

8.1 边的独立、覆盖和支配 8.2 顶点的独立、覆盖和支配 2023/4/17 6 本次课的主要内容

本次课的主要内容 8.1边的独立、覆盖和支配 8.2顶点的独立、覆盖和支配 2023/4/17

8.1 边的独立、覆盖和支配 8.2 顶点的独立、覆盖和支配 2023/4/17 7 本次课的主要内容

边的独立、覆盖和支配 ■边独立集 ●匹配 e14 V4 e 10 10 e12 2 e12 Vs e10 2023/4/17

n 边独立集 l 匹配 2023/4/17 8 边的独立、覆盖和支配

边的独立、覆盖和支配 ■边独立集 。匹配 ■极大边独立集 ●极大匹配 e14 11 e e V10 e12 e12 Vs e10 Vs v8e16 2023/4/17

n 边独立集 l 匹配 n 极大边独立集 l 极大匹配 2023/4/17 9 边的独立、覆盖和支配

边的独立、覆盖和支配 ■边独立集 ●匹配 ■极大边独立集 。极大匹配 ■最大边独立集 ●最大匹配 10 e12 e12 Vs e10 v8e16 2023/4/17 10

n 边独立集 l 匹配 n 极大边独立集 l 极大匹配 n 最大边独立集 l 最大匹配 2023/4/17 10 边的独立、覆盖和支配

边的独立、覆盖和支配 ■边独立集 ·匹配 ■ 极大边独立集 ●极大匹配 ■最大边独立集 。最大匹配 边独立数 。最大边独立集的大小，记作a(G e14 VA 11 e1s e12 e12 e10 Vs 2023/4/17 11

n 边独立集 l 匹配 n 极大边独立集 l 极大匹配 n 最大边独立集 l 最大匹配 n 边独立数 l 最大边独立集的大小，记作α’(G) 2023/4/17 11 边的独立、覆盖和支配