第五章 图的基本概念 5.1 无向图及有向图
5.1 无向图及有向图
我们分为无向图和有向图来介绍。
这里(,)出现两次表示与之间有两条无向边。
注意,无向图中用圆括号“()”
有向图中用尖括号“<>”,尖括号里的第一个元素表示起点,第二个表示终点。
下面铺一些基础概念:
注意:这里跟关联两次。
再来看有向图:
注意:
- 和是邻接的,而和不邻接。
- 和是平行的,而和不平行。
辨析:
- 空图是没有结点
- 零图是没有边
- 平凡图是只有一个孤立的结点
这里我们用(大写德尔塔)来表示最大的意思,(小写德尔塔)来表示最小的意思。
再来看有向图的:
易知以下握手定理:
我们来看他的推论:
这个很容易理解,只有当奇度数的顶点为偶数个才能保证其总度数为偶数。
再来看有向图中的一个定理:
来看一道例题:
根据握手定理我们可以判断哪些度数列可以构成图。
刚才按图有没有方向我们把其分成了有向图和无向图。现在我们再引入一种分类方式。
在无向简单图中有一类特殊的图:
同理,在有向简单图中也有一类特殊的图:
在一个无向简单图中,一个点的最大度数为。即除自身为与所有的点相连。根据这个我们可以用来判断哪个度数序列可以构成无向简单图。
我们再来看正则图的概念:
易得:在n阶无向简单图中,若其是n正则图那么其是n阶无向完全图。
下边我们来看子图和补图:
生成子图就是在原图的基础上去边。
导出子图我们分为以点集导出子图和以边集导出子图。分别如下:
再来看补图:
同构:
简单来讲:
因为画图时我们对点和边的布局不同,所以同一个图可能有差别很大的画法。我们通过空间想象来进行图的变幻,如果两个图可以变成同一个形状我们称其为同构。(可以类比三角形中全等的概念)
例如:
注意:
这些都是充分条件。至今还没有找到便于判断的图的同构的充分必要条件。要证明同构只能根据定义找到顶点之间的满足条件的双射关系。
例题:
练习1:
设图G有n个结点,m条边,且G中每个结点的度数不是k,就是k+1,则G中度数为k的节点数是()
解析:
可列方程求解
练习2:
解析:
如果是完全图的话, = = 1。再多一条边就变成一个多重图了。
练习3:
解析:
因为是有向图,相同结点之间的有两条边。
练习4:
图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的()?
充分条件。