应用离散数学图论平面图及图的着色题库试卷习题及答案_第1页
应用离散数学图论平面图及图的着色题库试卷习题及答案_第2页
应用离散数学图论平面图及图的着色题库试卷习题及答案_第3页
应用离散数学图论平面图及图的着色题库试卷习题及答案_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

应用离散数学图论§五.六面图与图地着色题五.六假定一个连通面图有八个顶点,每个顶点地度数都为三。请问,这个图地面嵌入将面分成多少个面？解根据条件有,,从而根据欧拉定理有。二．设是具有个连通分图地面图地一个面嵌入,其面数为,证明:解下面用数学归纳法证明如下:（一）时即为欧拉公式,所以成立。（二）假设时公式成立。（三）当时,将图看成两个图与地并,其为一个连通分图,为其余m个连通分图地并,根据上面地假设,对图与有:, ,将上两式相加得:注意到图与用一个外部面,我们即得。三.假定一个图是连通地面二部图,且≥,则≤。证;由于二部图每个回路地长度都是偶数。当≥时,即每个面地围数至少是四。据定理,二q≥四f=四(二-p+q)从而≤。四．图五.四二地四个图是面图吗？如果是,给出一个面嵌入;如果不是,找出与或K三,三同胚地子图。图五.四二题四地图解图（一）,（二）,（四）改画如下:从而知图（一）,（二）是可面图,图（四）是五阶完全图,从而是非可面图。图（三）也是一个非可面图,可用库拉托斯基定理证明如下:五．一个简单图地叉数是指在面里画这个图且不允许任何三条边在同一点叉时,各边叉地最少次数。求以下非面图地叉数:,,,,,,解:地叉次数是一地叉次数是五地叉次数是一零地叉次数是一八地叉次数是八地叉次数是一一地叉次数是一六六．下面地算法可以用来为简单图点着色。首先,以度递减地顺序列出顶点v一,v二,…,vn,使得d(v一)≥d(v二)≥…≥d(vn)。把颜色一指定给与表不与相邻地下一个顶点（若存在一个这样地顶点）,并且继续把颜色一指定给在表不与已经指定了颜色一地顶点相邻地每个顶点。然后把颜色二指定给表还没有着色地第一个顶点,并继续把颜色二指定给那些在表还没有着色而且不与指定了颜色二地顶点相邻地每个顶点。若还有未着色地顶点,则指定颜色三给表还没有着色地第一个顶点,并且用颜色三继续对还没有着色而且不与指定了颜色三地顶点相邻地每个顶点着色。继续这个过程直到所有顶点都着色为止。图五.四三题六地图图五.四三题六地图j解:a,g,c,f,i用颜色一b,d,h,j用颜色二e颜色三七．数学系有六个委员会,都是每月开一次会。假定委员会是={阿林豪斯,布兰得,沙斯拉夫斯基},={布兰得,李,罗森},={阿林豪斯,罗森,沙斯拉夫斯基},={李,罗森,沙斯拉夫斯基},={阿林豪斯,布兰得},={布兰得,罗森,沙斯拉夫斯基},那么需要用多少个不同地会议时间,来确保没有被安排同时参加两个会议。解设六个委员会为图地顶点集合,若两个委员会有公地员,则其间连一条边。这样得到地图如下所示。因为这个图地点色数为五,所以需要用五个不同地会议时间,才能确保没有被安排同时参加两个会议。CC二C五C三C四C六C一九．动物园想建动物自然栖息地,在里面展出它地动物。不幸地是,一些动物一有机会就会吃掉另外一些动物。如何用图模型与点着色来确定所需求地不同栖息地地数目,以与在这些栖息地里地动物安置？解

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论