图的基本概念
标签: 数据结构
学习人数: 5346


全屏播放
赞赏支持

 

一、顶点(vertex)

上图中黑色的带数字的点就是顶点,表示某个事物或对象。由于图的术语没有标准化,因此,称顶点为点、节点、结点、端点等都是可以的。叫什么无所谓,理解是什么才是关键。

 

二、边(edge)

上图中顶点之间蓝色的线条就是边,表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系,粗细长短都无所谓的。包括上面的顶点也一样,表示逻辑事物或对象,画的时候大小形状都无所谓。

 

三、同构(Isomorphism )

先看看下面2张图:

首先你的感觉是这2个图肯定不一样。但从图(graph)的角度出发,这2个图是一样的,即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系,不管顶点的位置在哪,边的粗细长短如何,只要不改变顶点代表的事物本身,不改变顶点之间的逻辑关系,那么就代表这些图拥有相同的信息,是同一个图。同构的图区别仅在于画法不同。

 

四、有向/无向图(Directed Graph/ Undirect...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】用有向无环图描述表达式(x+y)*((x+y)/x),需要的顶点个数至少是
A. 5       B. 6        C. 8       D. 9

参考答案:A

 

【2017年真题】已知无向图G含有16条边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点的度均小于3。图G所含的顶点个数至少是()
A.10        B.11        C.13        D.15

参考答案:B

 

【2010年真题】若无向图 G=(V, E)中含有 7 个顶点,要保证图 G 在任何情况下都是连通的,则需要的边数最少是()。 
A.6         B.15         C.16         D.21 

参考答案:C
答案解析:考查图的连通性。 
要保证无向图 G 在任何情况下都是连通的,即任意变动图 G 中的边,G 始终保持连通,首先需要 G的任意六个结点构成完全连通子图 G1,需 15 条边,然后再添一条边将第 7 个结点与 G1 连接起来,共需 16 条边。 

 

【2009年真题】下列关于无向连通图特性的叙述中,正确的是()。 
I. 所有顶点的度之和为偶数 
II. 边数大于顶点个数减 1 
III. 至少有一个顶点的度为 1 
A. 只有Ⅰ 
B.只有Ⅱ 
C.Ⅰ和Ⅱ 
D.Ⅰ和Ⅲ

参考答案:A
答案解析:考查无向连通图的特性。 
每条边都连接了两个结点,则在计算顶点的度之时,这条边都被计算了两次,故所有顶点的度之和为边数的两倍,显然必为偶数。而 ii 和 iii 则不一定正确,如:对顶点数 N≥1 无向完全图不存在一个顶点的度为 1,并且边数与顶点数的差要大于 1。 


登录后发布评论

暂无评论,来抢沙发