离散数学图论-西安电子科技大学.pdf

离散数学 西安电子科技大学 软件学院 第四篇 图论 第6章 图论 第27－28课时 6.1 图的基本概念 第29课时 6.2 路径与回路 第30课时 6.3 图的矩阵表示 第31－32课时 6.4 欧拉图与汉密尔顿图 第33课时 6.5 平面图 第34课时 6.6 图的着色 第35－36课时 6.7 树 第37 －38课时 6.8 图的应用 西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 图的色数 西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 证明：设图G中结点的最大度等于k，构造G的一个k＋1种 颜色的正常着色。 对于图G中度数最大的结点v，由于它邻接的结点个数最大为 k，若这k个结点均着上了不同的颜色，那么也可以用第k+1 种颜色对v进行正常着色。 西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 证明：若G是二部图，由于G中的结点集V可以划分为两个子 集X和Y，且X和Y中的结点间均不邻接。这样，我们可以使 用两种颜色，分别对X和Y中结点着色，即得到G的一种正常 着色。所以G的色数等于2。 若G的色数等于2，那么图G中至少有两个结点和一条边。若 我们用A、B两种颜色对G进行正常着色，那么可以将着A的 结点和着B的结点是图G的结点集合V的一个划分。并且A中 结点内部不可能存在边，同理B中结点内部也不可能存在 边。故G是二部图。 西安电子科技大学 §6.6.2 平面图的着色 软件学院 西安电子科技大学 §6.6.2 平面图的着色 软件学院 §6.6.2 平面图的着