知识卡片

普通读书笔记卡 · 3624.a.1.c

区间图把冲突表示为边

理解等级:初级

区间图把活动作为顶点、时间重叠的互斥活动作为边。

若要用最少教室安排全部活动,就是给图顶点着色,使相邻顶点颜色不同,并最小化颜色数;颜色对应教室。

它与只选最多兼容活动的目标不同。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [15000, 20000))。 - 结论依据:练习明确给出区间图的顶点、边与教室颜色映射。 - 原始内容:It is modeled by an interval graph whose vertices are the given activities and whose edges connect incompatible activities.