离散数学c图论.docVIP

《 离散数学 》 同步测试卷10:图的基本概念 一．填空： 1．一个无向图表示为G=V, E，其中V是 结点 的集合，E是 边 的集合， 并且要求E中的任何一条边必须和G中的两个结点 相关联 。 2．设无向图G中有12条边，已知G中度为3的结点有6个，其余的结点度均 小于3，则G中至少有 9 个结点。 3．设G=(n,m)是简单图，v是G中一个度为k的结点，e是G中的一条边，则G – v中有个结点，条边；G – e中有个结点，条边。 4．设G是个有向图，当且仅当G中有一条经过每一个结点的路径时，G才是 单向 连通图。 5．设图G=V, E，则：若E中的每条边都是_无向边 _，则称图G为无向图；若E中的每条边都是_有向边__，则称图G为有向图。 6．设图G中 无自环 和 无平行边 ，则称图G为简单图。 7．设G是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2，有6条边。则G中共有_ 4 个结点。因此，G是个多重边_图。 8．一个无向图G有16条边，若G中每一个结点的度均为2，则G有16个结点。 9．设G是个具有5个结点的简单无向完全图，则G有__10_条边。 10．设G是个具有5个结点的简单有向完全图，则G有_20_条边。 11．设G是个n阶简单有向图，是G的子图，已知的边数，则G的边数m为。 12．35条边，每个结点的度数至少是3的图最多有__23_个结点。 13、3个结点可构成 4 个不同构的简单无向图，可构成 16 个不同构的简单有向图。 14、设为无向连通图，则从中能找到 1 条回路 15、的点连通度为 4 ，边连通度为 4 。 16、设图G=V, E，，若G的邻接矩阵，则 3 ， 1 ，，从到长度为2的通路有 1 条。 17、右图的点连通度为 1 ，边连通度为 1 。 18、当为 奇 数时，必为欧拉图。 19、为哈密顿图，当且仅当 20、若连通平面图G有4个结点，3个面，则G有 5 条边。 21、仅当 4 时，为平面图。 22、设图G=7,15为简单平面图，则G一定是 连通的 ，且每个面均为 。 23、图A所示的图G的色数 3 。 24、图B所示的图G的点连通度2，G的边连通度3，点色数4 。 25、的生成子图中，有 6 个非同构的连通图。 26、平面图的对偶图同构于，则称为自对偶图，若一个图是自对偶的，则其结点数与边数的关系为 27、设D是阶有向简单（若连通）图，则D的可达矩阵的所有元素之和至少为 28、完全二部图的点覆盖数 29、设为轮图，则的点色数为 4 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 设图G=V, E，则V中所含的结点数称为图G的阶。 （ √ ） 2． 设图G=V, E，若，则称G为零图。 （ × ） 3、 设图G=V, E，若，则称G为平凡图。 （ × ） 4. 在简单有向图G的邻接矩阵中，结点所对应的行中1的个数等于的出度。.(√) 5. 在简单无向图G的邻接矩阵中，结点所对应的行中1的个数等于的度。.(√) 6． 若无向图中恰有两个奇结点，则这两个奇结点比相互可达。.(√) 7. 若有向图中恰有两个奇结点，则必有从一个结点到另一个结点可达或相互可达。.(×) 8． 对任何一个图，其奇结点的个数一定是偶数。.(√) 9． 在有向图中，结点间的可达关系一定是个等价关系。.(×) 10． 割边（或桥）一定是悬挂边。.(×) 11． 悬挂边一定是割边（或桥）。.(√) 12． 悬挂点一定是割点。(×) 13． 割点一定是悬挂点。 (×) 14． 有向图中的每个结点都恰处于一个单向分图中。(×) 15． 在完全无向图中，任意两个点都是邻接结点。(√) 16． 如果无向图G的邻接矩阵中所有元素均为零，则G必为零图。(√) 17． 如果简单无向图G的邻接矩阵中除主对角线外所有元素均为“1”，则G一定是完全图。(×) 18．如果G是一个非连通无向图，则G的一个连通子图称为G的一个分支。(×) 19．如果一个简单无向图G连通且无回路，则G中的每条边必为割边。(√) 20．具有n个结点的连通图中，至少有n条边。(×) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内(多选不给分)。 1．在具有n个结点的无向连通图中，( B ) A．恰好有n条边 B．至少有条边 C．最多有n条边 D．至少有n条边 2．设G=V, E为无自环的无向图，如果，则G是( D ) A．完全图 B．正则图 C．简单图 D．多重边图 3．设G=V, E为简单完全有向图，如果，则G中有(