好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

电子科技大学图论总复习PPT.ppt

47页
  • 卖家[上传人]:cn****1
  • 文档编号:590862220
  • 上传时间:2024-09-15
  • 文档格式:PPT
  • 文档大小:1.03MB
  • / 47 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 图论及其应用图论及其应用复习课件复习课件数学科学学院数学科学学院1 本次课主要内容本次课主要内容(二二)、重要结论、重要结论期末复习期末复习(一一)、重点概念、重点概念(三三)、应用、应用2 (一一)、重点概念、重点概念1、图、简单图、图的同构与自同构、度序列与图序列、、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图;补图与自补图、两个图的联图、两个图的积图、偶图;(1) 图:一个图是一个序偶图:一个图是一个序偶,记,记为为G=(V,E),其中:其中:1) V是一个有限的非空集合,称为顶点集合是一个有限的非空集合,称为顶点集合,其元素称为顶点或点其元素称为顶点或点用用|V||V|表示顶点数;表示顶点数;2) E是由是由V中的点组成的无序对构成的集合,称为边集,其元素称中的点组成的无序对构成的集合,称为边集,其元素称为边,且同一点对在为边,且同一点对在E中可以重复出现多次用中可以重复出现多次用|E||E|表示边数表示边数2) 简单图:无环无重边的图称为简单图简单图:无环无重边的图称为简单图3 (3) 图的度序列:图的度序列: 一个图一个图G的各个点的度的各个点的度d1, d2,…, dn构成的非负整数组构成的非负整数组(d1, d2,…, dn)称为称为G的度序列的度序列 。

      注:度序列的判定问题是重点注:度序列的判定问题是重点4) 图的图序列:图的图序列: 一个非负数组如果是某简单图的度序列,我们称它为可图序列,简一个非负数组如果是某简单图的度序列,我们称它为可图序列,简称图序列称图序列 注:图序列的判定问题是重点注:图序列的判定问题是重点5) 图的同构:图的同构:4 设有两个图设有两个图G1=(V1,E1)和和G2=(V2,E2),若在其顶点集合间存在双射,使得边若在其顶点集合间存在双射,使得边之间存在如下关系:设之间存在如下关系:设u1↔u2v1↔v2, u1,v1 V1, u2,v2 V2; u1v1 E1,当当且且仅当当u2v2 E2,且且u1v1与与u2v2的重数相同称的重数相同称G1与与G2同构,同构,记为:: 例例1 指出指出4个顶点的非同构的所有简单图个顶点的非同构的所有简单图分析:四个顶点的简单图最少边数为分析:四个顶点的简单图最少边数为0,最多边数为,最多边数为6,所以,所以可按边数进行枚举可按边数进行枚举5 (6) 补图与自补图补图与自补图1) 对于一个于一个简单图G =((V, E),令集合),令集合则图H =((V,,E1\E))称为称为G的补图,记为的补图,记为 2) 对于一个于一个简单图G =((V, E),若),若 ,称,称G为自自补图。

      注:要求掌握自注:要求掌握自补图的性的性质6 (7) 联图联图 设设G1,G2是两个不相交的图,作是两个不相交的图,作G1+G2,并且将,并且将G1中每个顶点和中每个顶点和G2中的每个顶点连接,这样得到的新图称为中的每个顶点连接,这样得到的新图称为G1与与G2的联图记为的联图记为 ::(8) 积图积图设设 是两个图对点集是两个图对点集的任意两个点的任意两个点u=(u1,u2)与与v=(v1,v2),当当(u1=v1和和u2adjv2)或或(u2=v2和和u1adjv1)时,时,把把u与与v相连如此得到的新图称为相连如此得到的新图称为G1与与G2的积图记的积图记为为7 (9) 偶图偶图 所谓具有二分类(所谓具有二分类(X, Y)的偶图(或二部图)是指一个图,它的点)的偶图(或二部图)是指一个图,它的点集可以分解为两个集可以分解为两个(非空非空)子集子集X和和Y,使得每条边的一个端点在中,另,使得每条边的一个端点在中,另一个端点在一个端点在Y中中. 注注: 掌握偶图的判定。

      掌握偶图的判定2、树、森林,生成树,最小生成树、根树、完全、树、森林,生成树,最小生成树、根树、完全m元树1) 树树 不含圈的图称为无圈图,树是连通的无圈图不含圈的图称为无圈图,树是连通的无圈图2) 森林森林 称无圈图称无圈图G为森林8 (3) 生成树生成树 图图G的一个生成子图的一个生成子图T如果是树,称它为如果是树,称它为G的一棵生成树;若的一棵生成树;若T为森林,称它为为森林,称它为G的一个生成森林的一个生成森林 生成树的边称为树枝,生成树的边称为树枝,G中非生成树的边称为弦中非生成树的边称为弦4) 最小生成树最小生成树 在连通边赋权图在连通边赋权图G中求一棵总权值最小的生成树该生成树称中求一棵总权值最小的生成树该生成树称为最小生成树或最小代价树为最小生成树或最小代价树 注:要求熟练掌握最小生成树的求法注:要求熟练掌握最小生成树的求法5) 根树根树 一棵非平凡的有向树一棵非平凡的有向树T,如果恰有一个顶点的入度为,如果恰有一个顶点的入度为0,而其余所有顶,而其余所有顶点的入度为点的入度为1,这样的的有向树称为根树其中入度为,这样的的有向树称为根树。

      其中入度为0的点称为树根,的点称为树根,出度为出度为0的点称为树叶,入度为的点称为树叶,入度为1,出度大于,出度大于1的点称为内点又将内点和的点称为内点又将内点和树根统称为分支点树根统称为分支点9 (6) 完全完全m元树元树 对于根树对于根树T,若每个分支点至多,若每个分支点至多m个儿子,称该根树为个儿子,称该根树为m元根树;元根树;若每个分支点恰有若每个分支点恰有m个儿子,称它为完全个儿子,称它为完全m元树注:对于完全注:对于完全m元树,要弄清其结构元树,要弄清其结构3、途径、途径(闭途径闭途径),迹,迹(闭迹闭迹), 路路(圈圈), 最短路,连通图,连最短路,连通图,连通分支,点连通度与边连通度通分支,点连通度与边连通度注:上面概念分别在注:上面概念分别在1和和3章章4、欧拉图,欧拉环游,欧拉迹,哈密尔顿圈,哈密尔顿、欧拉图,欧拉环游,欧拉迹,哈密尔顿圈,哈密尔顿图,哈密尔顿路,中国邮路问题,最优图,哈密尔顿路,中国邮路问题,最优H圈10 (1) 欧拉图与欧拉环游欧拉图与欧拉环游(2) 欧拉迹欧拉迹 对于连通图对于连通图G,如果,如果G中存在经过每条边的闭迹,则称中存在经过每条边的闭迹,则称G为欧拉为欧拉图,简称图,简称G为为E图。

      欧拉闭迹又称为欧拉环游,或欧拉回路欧拉闭迹又称为欧拉环游,或欧拉回路 对于连通图对于连通图G,如果,如果G中存在经过每条边的迹,则称该迹为中存在经过每条边的迹,则称该迹为G的的一条欧拉迹一条欧拉迹3) 哈密尔顿图与哈密尔顿圈哈密尔顿图与哈密尔顿圈 如果经过图如果经过图G的每个顶点恰好一次后能够回到出发点,称这样的每个顶点恰好一次后能够回到出发点,称这样的图为哈密尔顿图,简称的图为哈密尔顿图,简称H图所经过的闭途径是图所经过的闭途径是G的一个生成圈,的一个生成圈,称为称为G的哈密尔顿圈的哈密尔顿圈4) 哈密尔顿路哈密尔顿路 图图G的经过每个顶点的路称为哈密尔顿路的经过每个顶点的路称为哈密尔顿路11 5、匹配、最大匹配、完美匹配、最优匹配、因子分解匹配、最大匹配、完美匹配、最优匹配、因子分解1) 匹配匹配 匹配匹配 M--- 如果如果M是图是图G的边子集的边子集(不含环),且不含环),且M中的任意两条边没有中的任意两条边没有共同顶点,则称共同顶点,则称M是是G的一个匹配或对集或边独立集的一个匹配或对集或边独立集2) 最大匹配与完美匹配最大匹配与完美匹配最大匹配最大匹配 M--- 如果如果M是图是图G的包含边数最多的匹配,称的包含边数最多的匹配,称M是是G的一个的一个最大匹配。

      特别是,若最大匹配饱和了最大匹配特别是,若最大匹配饱和了G的所有顶点,称它为的所有顶点,称它为G的一的一个完美匹配个完美匹配3) 最优匹配最优匹配 设设G=(X, Y)是边赋权完全偶图,是边赋权完全偶图,G中的一个权值最大的完美匹配称为中的一个权值最大的完美匹配称为G的最优匹配的最优匹配12 (4) 因子分解因子分解 所谓一个图所谓一个图G的因子分解,是指把图的因子分解,是指把图G分解为若干个边不重的因子之分解为若干个边不重的因子之并 注:要弄清楚因子分解和完美匹配之间的联系与区别注:要弄清楚因子分解和完美匹配之间的联系与区别6、平面图、极大平面图、极大外平面图、平面图的对偶、平面图、极大平面图、极大外平面图、平面图的对偶图 (1) 平面图:平面图: 如果能把图如果能把图G画在平面上,使得除顶点外,边与边之间画在平面上,使得除顶点外,边与边之间没有交叉,称没有交叉,称G可以嵌入平面,或称可以嵌入平面,或称G是可平面图可平面图是可平面图可平面图G的边不的边不交叉的一种画法,称为交叉的一种画法,称为G的一种平面嵌入,的一种平面嵌入,G的平面嵌入表示的图称为的平面嵌入表示的图称为平面图。

      平面图13 (2) 极大平面图极大平面图: 设设G是简单可平面图,如果是简单可平面图,如果G是是Ki (1≦≦i≦≦4),或者在或者在G的任意非邻接顶点间添加一条边后,得到的图均是非可平面图,则的任意非邻接顶点间添加一条边后,得到的图均是非可平面图,则称称G是极大可平面图是极大可平面图 极大可平面图的平面嵌入称为极大平面图极大可平面图的平面嵌入称为极大平面图3) 极大外平面图:若一个可平面图极大外平面图:若一个可平面图G存在一种平面嵌入,使得其所有存在一种平面嵌入,使得其所有顶点均在某个面的边界上,称该图为外可平面图外可平面图的一种顶点均在某个面的边界上,称该图为外可平面图外可平面图的一种外平面嵌入,称为外平面图外平面嵌入,称为外平面图 (4) 平面图的对偶图:给定平面图平面图的对偶图:给定平面图G,,G的对偶图的对偶图G*如下构造:如下构造: 1) 在在G的每个面的每个面fi内取一个点内取一个点vi*作为作为G*的一个顶点;的一个顶点; 2) 对对G的一条边的一条边e, 若若e是面是面 fi 与与 fj 的公共边,则连接的公共边,则连接vi*与与vj*,且连线,且连线穿过边穿过边e;若若e是面是面fi中的割边,则以中的割边,则以vi为顶点作环,且让它与为顶点作环,且让它与e相交相交。

      14 7、边色数、点色数、色多项式、边色数、点色数、色多项式(1)、边色数、边色数 设设G是图,对是图,对G进行正常边着色需要的最少颜色数,称为进行正常边着色需要的最少颜色数,称为G的边色的边色数,记为:数,记为:(2)、点色数、点色数 对图对图G正常顶点着色需要的最少颜色数,称为图正常顶点着色需要的最少颜色数,称为图G的点色数图的点色数图G的点色数用的点色数用 表示3)、色多项式、色多项式 对图进行正常顶点着色,其方式数对图进行正常顶点着色,其方式数Pk(G)是是k的多项式,称为图的多项式,称为图G的的色多项式色多项式15 8、强连通图、单向连通图、弱连通图、强连通图、单向连通图、弱连通图(1)、强连通图、强连通图(2)、弱连通图、弱连通图(3)、单向连通图、单向连通图 若若D的基础图是连通的,称的基础图是连通的,称D是弱连通图;是弱连通图; 若若D的中任意两点是单向连通的,称的中任意两点是单向连通的,称D是单向连通图是单向连通图 若若D的中任意两点是双向连通的,称的中任意两点是双向连通的,称D是强连通图;是强连通图;16 (二二)、重要结论、重要结论1、握手定理及其推论、握手定理及其推论定理定理1:: 图图G= (V, E)中所有顶点的度的和等于边数中所有顶点的度的和等于边数m的的2倍,即:倍,即:推论推论1 在任何图中,奇点个数为偶数。

      在任何图中,奇点个数为偶数推论推论2 正则图的阶数和度数不同时为奇数正则图的阶数和度数不同时为奇数 17 2、托兰定理、托兰定理定理定理2 若若n阶简单图阶简单图G不包含不包含Kl+1,则,则G度弱于某个完全度弱于某个完全 l 部图部图 H,且若,且若G具有与具有与 H 相同的度序列,则相同的度序列,则: 定理定理3 设设T是是(n, m)树,则:树,则:3、树的性质、树的性质4、最小生成树算法、最小生成树算法18 5、偶图判定定理、偶图判定定理定理定理4 图图G是偶图当且仅当是偶图当且仅当G中没有奇回路中没有奇回路6、敏格尔定理、敏格尔定理 定理定理5 (1) 设设x与与y是图是图G中的两个不相邻点,则中的两个不相邻点,则G中分离中分离点点x与与y的最小点数等于独立的的最小点数等于独立的(x, y)路的最大数目;路的最大数目; (2)设设x与与y是图是图G中的两个不相邻点,则中的两个不相邻点,则G中分离点中分离点x与与y的最小边数等于的最小边数等于G中边不重的中边不重的(x, y)路的最大数目路的最大数目7、欧拉图、欧拉迹的判定、欧拉图、欧拉迹的判定19 定理定理6 下列陈述对于非平凡连通图下列陈述对于非平凡连通图G是等价的:是等价的: (1) G是欧拉图;是欧拉图; (2) G的顶点度数为偶数;的顶点度数为偶数; (3) G的边集合能划分为圈。

      的边集合能划分为圈 推论:推论: 连通非欧拉图连通非欧拉图G存在欧拉迹当且仅当存在欧拉迹当且仅当G中只有两中只有两个顶点度数为奇数个顶点度数为奇数8、、H图的判定图的判定 定理定理7 (必要条件必要条件) 若若G为为H图,则对图,则对V(G)的任一非空的任一非空顶点子集顶点子集S,有:,有:20 定理定理8 (充分条件充分条件) 对于对于n≧3≧3的单图的单图G G,如果,如果G G中有:中有: 定理定理9 (充分条件充分条件) 对于对于n≧3≧3的单图的单图G G,如果,如果G G中的任意中的任意两个不相邻顶点两个不相邻顶点u u与与v v,有:,有: 定理定理10 (帮迪帮迪——闭包定理闭包定理) 图图G是是H图当且仅当它的闭图当且仅当它的闭包是包是H图21 定理定理11(Chvátal——度序列判定法度序列判定法) 设简单图设简单图G的度序列的度序列是是(d1,d2,…,dn), 这里,这里,d1≦d≦d2 2≦≦……≦≦d dn n, ,并且并且n≧3.n≧3.若对任意的若对任意的mm,>m,或者或者d dn-mn-m ≧ ≧ n-mn-m, ,则则G G是是H H图。

      图 定理定理12 设设G是是n阶单图若阶单图若n≧3≧3且且 则则G是是H图;并且,具有图;并且,具有n个顶点个顶点 条边的非条边的非H图图只有只有C1,n以及以及C2,5.22 8、偶图匹配与因子分解、偶图匹配与因子分解 定理定理13 (Hall定理)设定理)设G=(X, Y)是偶图,则是偶图,则G存在饱和存在饱和X每个每个顶点的匹配的充要条件是:顶点的匹配的充要条件是: 推论:若推论:若G是是k (k>0)正则偶图,则正则偶图,则G存在完美匹配存在完美匹配 定理定理14 (哥尼,哥尼,1931) 在偶图中,最大匹配的边数等于最小在偶图中,最大匹配的边数等于最小覆盖的顶点数覆盖的顶点数 定理定理15 K2n可一因子分解可一因子分解23 定理定理16 具有具有H圈的三正则图可一因子分解圈的三正则图可一因子分解 定理定理17 K2n+1可可2因子分解因子分解 定理定理18 K2n可分解为一个可分解为一个1因子和因子和n-1个个2因子之和因子之和 定理定理19 每个没有割边的每个没有割边的3正则图是一个正则图是一个1因子和因子和1个个2因因子之和。

      子之和 最优匹配算法最优匹配算法(见教材)见教材)9、平面图及其对偶图、平面图及其对偶图 1)、平面图的次数公式、平面图的次数公式24 2)、平面图的欧拉公式、平面图的欧拉公式 定理定理20 设设G=(n, m)是平面图,则:是平面图,则: 定理定理21(欧拉公式欧拉公式) 设设G=(n, m)是连通平面图,是连通平面图,фф是是G G的面的面数,则:数,则: 3)、几个重要推论、几个重要推论25 推论推论1 设设G是具有是具有n n个点个点m m条边条边фф个面的连通平面图,如个面的连通平面图,如果对果对G G的每个面的每个面f f , ,有:有:deg (deg (f f) ≥ ) ≥ l ≥3,≥3,则:则: 推论推论2 设设G是具有是具有n n个点个点m m条边条边фф个面的简单平面图,个面的简单平面图,则:则: 推论推论3 设设G是具有是具有n n个点个点m m条边的简单平面图,则:条边的简单平面图,则:26 注:掌握证明方法注:掌握证明方法 4)、对偶图的性质、对偶图的性质 定理定理22 平面图平面图G的对偶图必然连通的对偶图必然连通. 5)、极大平面图的性质、极大平面图的性质 定理定理23 设设G是至少有是至少有3个顶点的平面图,则个顶点的平面图,则G是极大平是极大平面图,当且仅当面图,当且仅当G的每个面的次数是的每个面的次数是3且为单图。

      且为单图 10、着色问题、着色问题 1)、边着色、边着色27 定理定理24 定理定理25 (哥尼,哥尼,1916)若若G是偶图,则是偶图,则 定理定理26 (维津定理,维津定理,1964) 若若G是单图,则:是单图,则: 定理定理27 设设G是单图且是单图且ΔΔ(G)>0(G)>0若G G中只有一个最大度中只有一个最大度点或恰有两个相邻的最大度点,则:点或恰有两个相邻的最大度点,则:28 定理定理28 设设G是单图若点数是单图若点数n=2k+1且边数且边数m>kΔΔ, ,则:则: 定理定理29 设设G是奇数阶是奇数阶ΔΔ正则正则单图单图, ,若若ΔΔ>0,>0,则:则: 2)、点着色、点着色 定理定理30 对任意的图对任意的图G,有:,有:29 定理定理31(布鲁克斯,布鲁克斯,1941) 若若G是连通的单图,并且它是连通的单图,并且它既不是奇圈,又不是完全图,则:既不是奇圈,又不是完全图,则: 3)、色多项式、色多项式 定理定理32 设设G为简单图,则对任意为简单图,则对任意 有:有: 1)、递推计数法、递推计数法 2)、理想子图计数方法、理想子图计数方法30 (1) 画出画出G的补图的补图 (2) 求出关于补图的求出关于补图的 (3) 写出关于补图的伴随多项式写出关于补图的伴随多项式 (4) 将将 代入伴随多项式中得到代入伴随多项式中得到Pk(G)。

      11、根树问题、根树问题定理定理32 在完全在完全m元树元树T中,若树叶数为中,若树叶数为t , 分支点数为分支点数为i , 则:则:31 (三三)、图论应用、图论应用1、、 偶图匹配问题偶图匹配问题 例例1 有有7名研究生名研究生 A, B, C, D, E, F, G毕业寻找工作就业处毕业寻找工作就业处提供的公开职位是:会计师提供的公开职位是:会计师(a) ,咨询师咨询师(b),编辑编辑(c ),程序员程序员(d), 记者记者(e), 秘书秘书(f)和教师和教师(g)每名学生申请的职位如下:每名学生申请的职位如下: A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F : c, e ; G : d, e, f, g ; 问:学生能找到理想工作吗?问:学生能找到理想工作吗? 重点掌握如下两方面应用重点掌握如下两方面应用32 问题转化为是否有饱和问题转化为是否有饱和X每个顶点的一个匹配每个顶点的一个匹配。

      FEDCBAGabcdefg 解:如果令解:如果令X={{A, B, C, D, E, F, G}},Y={{a, b, c, d, e, f , g}},X中顶点与中顶点与Y中顶点连线当且仅当学生申请了该工作于中顶点连线当且仅当学生申请了该工作于是,得到反映学生和职位之间的状态图:是,得到反映学生和职位之间的状态图:33 当当S取取X中四元点集时,若取中四元点集时,若取S={{A,C,D,F}},则有则有3=|N(S)|<|S|=4 所以,不存在饱和所以,不存在饱和X每个顶点的匹配每个顶点的匹配2、、 着色问题着色问题1)、、 边着色问题边着色问题 例例2 (排课表问题排课表问题) 在一个学校中,有在一个学校中,有7个教师个教师12个班个班级在每周级在每周5天教学日条件下,教课的要求由如下矩阵天教学日条件下,教课的要求由如下矩阵给出:给出:34 x1x2x3x4x6x5x7y2y1y8y7y6y5y4y3y10y9y11y12 其中,其中,pij表示表示xi必须教必须教yj班的节数求:班的节数求: (1) 一天分成几节课,才能满足所提出的要求?一天分成几节课,才能满足所提出的要求? (2) 若安排出每天若安排出每天8节课的时间表,需要多少间教室?节课的时间表,需要多少间教室?35 x1x2x3x4x6x5x7y2y1y8y7y6y5y4y3y10y9y11y12 解:问题可模型为一个偶图。

      解:问题可模型为一个偶图 一节课对应边正常着色的一一节课对应边正常着色的一个色组由于个色组由于G是偶图,所以边是偶图,所以边色数为色数为G的最大度的最大度35这样,最这样,最少总课时为少总课时为35节课平均每天节课平均每天要安排要安排7节课 如果每天安排如果每天安排8节课,因为节课,因为G的总边数为的总边数为240,所以需要,所以需要的教室数为的教室数为240/40=636 例例3 (比赛安排问题比赛安排问题) Alvin (A)曾邀请曾邀请3对夫妇到他的避暑别对夫妇到他的避暑别墅住一个星期他们是:墅住一个星期他们是:Bob和和Carrie , David和和Edith, Frank和和Gena由于这6人都喜欢网球运动,所以他们决定进行网球人都喜欢网球运动,所以他们决定进行网球比赛6位客人的每一位都要和其配偶之外的每位客人比赛位客人的每一位都要和其配偶之外的每位客人比赛另外,另外,Alvin将分别和将分别和David,, Edith,, Frank,, Gena进行一进行一场比赛若没有人在同一天进行场比赛若没有人在同一天进行2场比赛,则要在最少天数完场比赛,则要在最少天数完成比赛,如何安排?成比赛,如何安排? 解:用点表示参赛人,两点连线当且仅当两人有比赛。

      这解:用点表示参赛人,两点连线当且仅当两人有比赛这样得到比赛状态图样得到比赛状态图 问题对应于求状态图的一种最优边着色问题对应于求状态图的一种最优边着色(用最少色数进行正用最少色数进行正常边着色常边着色)37 状态图为:状态图为:FDAGCEB图图G 由于由于n=2×3+1, 所以所以k=3而Δ=5 ,,m=16>3×5=kΔ,所以由定所以由定理理5知:知:38 最优着色为:最优着色为:FDAGCEB图图G39 例例4 课程安排问题:某大学数学系要为这个夏季安排课程安排问题:某大学数学系要为这个夏季安排课程表所要开设的课程为:图论课程表所要开设的课程为:图论(GT), 统计学统计学(S),线性线性代数代数(LA), 高等微积分高等微积分(AC), 几何学几何学(G), 和近世代数和近世代数(MA)现有现有10名学生名学生(如下所示如下所示)需要选修这些课程根据这些信需要选修这些课程根据这些信息,确定开设这些课程所需要的最少时间段数,使得学息,确定开设这些课程所需要的最少时间段数,使得学生选课不会发生冲突生选课不会发生冲突学生用学生用Ai表示)表示) A1: LA, S ; A2: MA, LA, G ; A3: MA, G, LA; A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA;2)、、 点着色问题点着色问题40 A10: GT, S。

      解:把课程模型为图解:把课程模型为图G的顶点,两顶点连线当且仅当的顶点,两顶点连线当且仅当有某个学生同时选了这两门课程有某个学生同时选了这两门课程GTMAGACLAS选课状态图选课状态图41 如果我们用同一颜色给同一时段的课程顶点染色,那如果我们用同一颜色给同一时段的课程顶点染色,那么,问题转化为在状态图中求对应于点色数的着色么,问题转化为在状态图中求对应于点色数的着色 (1) 求点色数求点色数 一方面,因图中含有奇圈一方面,因图中含有奇圈(红红色边色边), 所以,点色数至少为所以,点色数至少为3又因为点因为点LA与该圈上每一个点均邻与该圈上每一个点均邻接,所以,点色数至少为接,所以,点色数至少为4.GTMAGACLAS选课状态图选课状态图 另一方面,我们用另一方面,我们用4种色实现了种色实现了G的正常点着色,所以,的正常点着色,所以,图的点色数为图的点色数为4.42 (2) 求安排求安排----具体着色具体着色GTMAGACLAS选课状态图选课状态图43 例例5 交通灯的相位设置问题:如图所示,列出了繁华街道交通灯的相位设置问题:如图所示,列出了繁华街道路口处的交通车道路口处的交通车道L1,L2,…,L9。

      在此路口处安置了交通灯在此路口处安置了交通灯当交通灯处于某个相位时,亮绿灯的车道上的车辆就可以安当交通灯处于某个相位时,亮绿灯的车道上的车辆就可以安全通过路口为了全通过路口为了(最终最终)让所有的车辆的灯都能够安全通过让所有的车辆的灯都能够安全通过路口,对于交通灯来说,所需要的相位的最小数是多少?路口,对于交通灯来说,所需要的相位的最小数是多少?L5L4L3L2L1L9L8L7L644 解:车道模型为顶点,两点连线当且仅当两个车道上的解:车道模型为顶点,两点连线当且仅当两个车道上的车不能同时安全地进入路口车不能同时安全地进入路口L9L8L7L6L5L4L3L2L1G 问题转化为求问题转化为求G的点色数一方面,的点色数一方面,G中含有中含有K4,所以,点所以,点色数至少为色数至少为4;;L9L8L7L6L5L4L3L2L1G45 另一方面,通过尝试,用另一方面,通过尝试,用4种色实现了正常点着色种色实现了正常点着色 所以,最小相位为所以,最小相位为4L9L8L7L6L5L4L3L2L1G21122434346 Thank You !47 。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.