-
- 素材大小:
- 873.1 KB
- 素材授权:
- 免费下载
- 素材格式:
- .ppt
- 素材上传:
- lipeier
- 上传时间:
- 2019-09-11
- 素材编号:
- 240771
- 素材类别:
- 课件PPT
-
素材预览
这是ppt区间图,包括了图的基本概念,弦图的概念,弦图的判定,求完美消除序列,LexBFS算法,MCS算法,弦图的极大团,弦图的点染色问题,区间图,区间图的判定等内容,欢迎点击下载。
ppt区间图是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
清华大学 陈丹琦 图的基本概念 子图 (subgraph) 图 为图G的子图 图的基本概念 诱导子图(induced subgraph) 图 称为图G的诱导子图 图的基本概念 团(clique) 图G的一个子图 , 为关于 的完全图。 图的基本概念 团(clique) 图G的一个子图 , 为关于 的完全图。 图的基本概念 团(clique) 图G的一个子图 , 为关于 的完全图。 图的基本概念 最小染色(minimum coloring) 用最少的颜色给点染色使相邻点颜色不同。 图的基本概念 最大独立集(maximum independent set) 最大的一个点的子集使任何两个点不相邻。 图的基本概念 最小团覆盖(minimum clique cover) 用最少个数的团覆盖所有的点。 图的基本概念 团数 ≤ 色数 图的基本概念 团数 ≤ 色数 弦图的概念 弦(chord):连接环中不相邻的两个点的边。 弦图的概念 弦(chord):连接环中不相邻的两个点的边。 弦图的概念 弦(chord):连接环中不相邻的两个点的边。 弦图的判定 [例题 ] Zju1015 Fishing net 给定一个无向图,判定它是否为弦图。 弦图的判定 [例题 ] Zju1015 Fishing net 给定一个无向图,判定它是否为弦图。 弦图的判定 [例题 ] Zju1015 Fishing net 给定一个无向图,判定它是否为弦图。 弦图的判定 完美消除序列(perfect elimination ordering) 定义:一个点的序列(每个点出现且恰好出现一次)v1, v2, …, vn满足vi在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。 弦图的判定 完美消除序列(perfect elimination ordering) 定义:一个点的序列(每个点出现且恰好出现一次)v1, v2, …, vn满足vi在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。 弦图的判定 定理:一个无向图是弦图当且仅当它有一个完美消除序列。 弦图的判定 定理:一个无向图是弦图当且仅当它有一个完美消除序列。 证明: 充分性 由引理知任何一个弦图都至少有一个单纯点以及弦图的诱导子图都是弦图。可以使用数学归纳法假设当点数
中职数学2.2.2-不等式的解集与区间课件PPT模板:这是一个关于中职数学2.2.2-不等式的解集与区间课件PPT模板,这节课主要是了解1.理解不等式的解与解集的意义2.掌握不等式的解集的数轴表示 不等式的解集—内容全解等等介绍。由不等式的所有解组成的集合,我们把它叫做不等式的解集。求不等式解集的过程叫做解不等式,欢迎点击下载中职数学2.2.2-不等式的解集与区间课件PPT模板哦。