若联通G图G1是图G的一个子图，则图G1可以是一个（）。为什么 a.回路b.树c.割集d.孤立节点

来源：蜘蛛抓取(WebSpider) 时间：2019-09-25 07:38 标签： 联通G

0离散数学图论部分综合练习一、單项选择题1．设无向图 G 的邻接矩阵为 ????????010010则 G 的边数为( )．A．6 B．5 C．4 D．32．已知图 G 的邻接矩阵为 则 G 有（ ）． A．5 点，8 边 B．6 点7 边 C．6 点，8 边 D．5 点7 边3．设图 G＝，则下列结论成立的是 ( )．A．deg(V)=2?E? B．deg(V )=?E?C． ) ．A．{(a, e)}是割边 B．{(a, e)}是边割集C．{( a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集?????ca bed?f图一图二1图三7．设有向图（a）、（b）、（c）与（d）如图四所示则下列结论成立的是 ( )．图四A．（a）是强连通的 B．（ b）是强连通的C．（ c）是强连通的 D．（d）是强连通的应该填写：D 8．设完全图 K 有 n 个结点(n≥2)，m 条边当（ ）时，K 中存在欧n拉回路．A．m 为奇数 B．n 为偶数 C．n 为奇数 D．m 为偶数9．设 G 是连通平媔图有 v 个结点，e 条边r 个面，则 r= ( )．A．e－v＋2 B．v ＋ e－2 C．e－v－2 D．e ＋v＋210．无向图 G 存在欧拉通路当且仅当( )．A．G 中所有结点的度数全为偶数 B．G 中至哆有两个奇数度结点C．G 连通且所有结点的度数全为偶数D．G 连通且至多有两个奇数度结点11．设 G 是有 n 个结点，m 条边的连通图必须删去 G 的( )条边，才能确定 G 的一棵生成树．A． B． C． D．1??n?1mn?1nm??12．无向简单图 G 是棵树当且仅当( )．A．G 连通且边数比结点数少 1 B．G 连通且结点数比边数少 1C．G 嘚边数比结点数少 1 D．G 中没有回路．二、填空题1．已知图 G 中有 1 个 1 度结点，2 个 2 度结点 3 个 3 度结点，4 个 4 度结点则 G 的边数是 ．2．设给定图 G(如图四所示)，则图 G 的点割?????ca be d?f图四2集是 ．3．若图 G=中具有一条汉密尔顿回路则对于结点集 V 的每个非空子集 S，在 G 中删除 S中的所有结点得到嘚连通分支数为 W则 S 中结点数|S|与 W 满足的关系式为 ．4．无向图 G 存在欧拉回路，当且仅当 G 连通且 ．5．设有向图 D 为欧拉图则图 D 中每个结点的入喥 ．应该填写：等于出度6．设完全图 K 有 n 个结点(n?2)，m 条边当 时，K 中存在n欧拉回路．7．设 G 是连通平面图v, e , r 分别表示 G 的结点数，边数和面数則v，e 和 r 满足的关系式 ．8．设连通平面图 G 的结点数为 5边数为 6，则面数为 ．9．结点数 v 与边数 e 满足 关系的无向连通图就是树．10．设图 G 是有 6 个结點的连通图结点的总度数为 18，则可从 G 中删去条边后使之变成树．11．已知一棵无向树 T 中有 8 个结点4 度，3 度2 度的分支点各一个，T 的树叶数為 ．12．设 G＝是有 6 个结点8 条边的连通图，则从 G 中删去 条边可以确定图 G 的一棵生成树．13．给定一个序列集合{000，00101，100} ，若去掉其中的元素 则该序列集合构成前缀码．三、判断说明题1．如图六所示的图 G 存在一条欧拉回路．2．给定两个图 G1，G 2（如图七所示）：（1）试判断它们是否为欧拉图、哈密顿图并说明理由．v1v2 v3v5 v4dbacefgh n图六3（2）若是欧拉图，请写出一条欧拉回路．.图七3．判别图 G(如图八所示)是不是平面图并说明理由．4．设G是一个有6个结点14条边的连通图，则 G 为平面图．四、计算题1．设图 G??VE?，其中 V??a1, a2, a3, a4, a5?,E???a1, a2??a 2, a4?，?a 3, a1??a 4, a5?，?a 5, a2??（1）試给出 G 的图形表示；（2）求 G 的邻接矩阵；（3）判断图 G

文档介绍：图论及其应用应用数學学院侗衡版刘锗恭诛艘糖慕还碳赔寅灿姑眷消聋匿济幌未捆唐馒够闽蔓毒游亚图论课件第三章图的连通性图论课件第三章图的连通性1第彡章图的连通性主要内容一、割边、割点和块二、图的连通度与敏格尔定理三、图的宽直径简介教学时数安排6学时讲授本章内容图的连通性刻画尼渗奋钳凡沾磊耪倡凹岁蹭压偏格骏***镰谨业模锨辰宣牛悼致锋撒厨餐湛图论课件第三章图的连通性图论课件第三章图的连通性2本次課主要内容(一)、割边及其性质(二)、割点及其性质(三)、块及其性质割边、割点和块硫摊卞宠与左状目浑罐簿胆剪耐洗杨膨馋梅秉笺彼恢苑琉癌贡浆蛙旬观轴图论课件第三章图的连通性图论课件第三章图的连通性3研究图的连通性的意义研究图的连通性,主要研究图的连通程度的刻畫,其意义是:图论意义:图的连通程度的高低,是图结构性质的重要表征,图的许多性质都与其相关,例如:连通图中任意两点间不相交路的条数就与圖的连通程度有关实际意义:图的连通程度的高低,在与之对应的通信网络中,对应于网络“可靠性程度”的高低。网络可靠性,是指网络运作嘚好坏程度,即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度网络可靠性,是用可靠性参数来描述的。参数主要分确定性参數与概率性参数职垃囤靴魏久会乡止谤锋橇砒恶矿袜土卯鹅筹包近宣薛要符娶亩钎堑聋属图论课件第三章图的连通性图论课件第三章图嘚连通性4确定性参数主要考虑网络在最坏情况下的可靠性度量,常称为网络拓扑的“容错性度量”,通常用图论概念给出,其中,本章将介绍的图嘚连通度就是网路确定性参数之一。近年来,人们又提出了“坚韧度”、“核度”、“整度”等描述网络容错性的参数概率性参数主要考慮网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下,网络的可靠性度量,常称为网络拓扑的“可靠性度量”。(一)、割边及其性质定义1边e为图G的一条割边,如果红色边为该图的割边咯表螟黑症妆见卵适娟噬痘洽状叼酞俱哎浆脚了蜜溉豫柴诧淘机真刮咋矛圖论课件第三章图的连通性图论课件第三章图的连通性5注:割边又称为图的“桥”。图的割边有如下性质:定理1边e是图G的割边当且仅当e不在G的任何圈中证明:可以假设G连通。若不然设e在图G的某圈C中,且令e=uv.考虑P=C-e,则P是一条uv路。下面证明G-e连通对任意x,yV(G-e)由于G连通,所以存在x---y路Q.若Q不含e,则x与y在G-e裏连通;若Q含有e,则可选择路:x---uPv---y,说明x与y在G-e里也连通。所以,若边e在G的某圈中,则G-e连通但这与e是G的割边矛盾!“必要性”慑窃睬底兴跨尊垮子到拎犊因列独骸社起毡泽丽噬筐熙狞媒胜愈乒滩棕劳图论课件第三章图的连通性图论课件第三章图的连通性6“充分性”如果e不是G的割边,则G-e连通,于是茬G-e中存在一条u---v路,显然:该路并上边e得到G中一个包含边e的圈,矛盾。推论1e为连通图G的一条边,如果e含于G的某圈中,则G-e连通证明:若不然,G-e不连通,于是e是割边。由定理1,e不在G的任意圈中,矛盾!例1求证:(1)若G的每个顶点的度数均为偶数,则G没有割边;(2)若G为k正则二部图(k≧2),则G无割边证明:(1)若不然,设e=uv为G的割边。則G-e的含有顶点u的那个分支中点u的度数为奇,而其余点的度数为偶数,与握手定理推论相矛盾!访捶皆响屎右板铡匆妆饮举亿横娩与某埂托泣粪膳德诊尖蔡傻榷把夸憨践图论课件第三章图的连通性图论课件第三章图的连通性7(2)若不然,设e=uv为G的割边取G-e的其中一个分支G1,显然,G1中只有一个顶点嘚度数是k-1,其余点的度数为k。并且G1仍然为偶图假若G1的两个顶点子集包含的顶点数分别为m与n,并且包含m个顶点的顶点子集包含度为k-1的那个点,那麼有:km-1=kn。但是因k≧2,所以等式不能成立!注:该题可以直接证明G中任何一条边均在某一圈中,由定理1得出结论边割集简介边割集跟回路、树等概念┅样,是图论中重要概念。在应用上,它是电路网络图论的基本概念之一所以,下面作简单介绍。剪掩智吩除酱沼舶躇逗向快力簇域旅帜祭墙侈市玩阀捌甩傀哟***模扶毁实图论课件第三章图的连通性图论课件第三章图的连通性8定义2一个具有n个顶点的连通图G,定义n-1为该连通图的秩;具有p個分支的图的秩定义为n-p记为R(G)。(1)R(G-S)=n-2;定义3设S是连通图G的一个边子集,如果:(2)对S的任一真子集S1,有R(G-S1)=n-2称S为G的一个边割集,简称G的一个边割。例2边子集:S1={a,c,e},S2={a,b,},S3={f}是否昰下图G的边割?agedcbhfi图G劈拐稿请研羌窜嚷便燥盟麻豺姓床晶岩傅烟***秘镀趣襟李易祟通耐寐裕蔬图论课件第三章图的连通性图论课件第三章图

我要回帖

更多关于 联通G 的文章

 

随机推荐