5.2 度数、通路与回路
本章目录 · 1 节
本章导读
定义5.2.1:无向图顶点 的度 ,是以它为端点的次数;环贡献2,平行边逐条计数。有向图中,作为起点的次数为出度 ,作为终点的次数为入度 ,总度为二者之和;有向环各贡献一个入度和一个出度。度不同于不同邻点的数量。
最大度、最小度分别为 、;有向图也可分别取总度、出度、入度的最大最小值,记 。度为1的顶点称悬挂顶点,其关联边称悬挂边;度奇偶分别对应奇度、偶度顶点。
图5.1.1(a)按 的度为 ,所以 ; 为悬挂点, 为悬挂边。图(b)按 的出度为 ,入度为 ,总度为 ;因此总最大最小度为5、3,最大最小出度为4、0,最大最小入度为3、1。
定理5.2.1(握手定理):任意有限无向图均有 ,因为每条边恰提供两个端点次数,环亦不例外。定理5.2.2:有向图满足 ,故总度之和仍为 。推论5.2.1:任意图的奇度顶点数为偶数;总度和为偶数,去掉偶度项后,奇数项之和仍为偶数,所以奇数项个数只能为偶数。
给定顶点次序后的度数列记为 。若存在以它为度数列的无向图,称可图化;若可由无向简单图实现,称可简单图化。单个标定图的数列确定,不表示给定数列只对应一个图。有向图还须区分入度列和出度列。
定理5.2.3:非负整数列可图化,当且仅当总和为偶数,这里的实现允许环和平行边。必要性由握手定理;充分性先把奇数度顶点两两连边,各消耗一个度,再在每个顶点添加剩余度数一半的环。若限定简单图,这个充分条件失效。定理5.2.4: 阶无向简单图满足 ,因为没有环且每个其他顶点至多贡献一条边;这仍只是必要条件,并非完整判据。
【例5.2.1】判断以下数列是否可图化、可简单图化:(1);(2);(3);(4) 且和为偶数;(5)。
解:(1)和为21,不能图化。(2)和16,可图化;但5个顶点的简单图最大度不超过4,故不能简单图化。(3)和10,可图化;若为简单图,前三个度3顶点都须与全部其他点相邻,便迫使第四点的度至少3,与1矛盾。(4)和为偶数所以可图化;但 个互异正整数必有 ,故不能简单图化。(5)可以简单图化,教材给出下列两种实现。
定义5.2.2:两个图同构,是指存在顶点集间的双射,保持全部边的端点对应、重数,并在有向图中保持方向。写 。同构图可以有不同的顶点名和画法,单靠“外观相似”不能证明;需要给出双射或可验证的结构对应。图的同构关系自反、对称、传递,分别由恒等映射、逆映射、映射复合得到。
阶数、边数、度数列相同都是同构的必要条件,但不足以推出同构。图5.2.1的两个实现即为反例。证明不同构可找不变量,如三角形个数、某长度圈的数量,或邻接点之间的结构;核对有向图时还要比较成对的入出度,不能仅比较总度。
定义5.2.3: 阶无向简单图中,每点与其他 个点均相邻,称无向完全图 ;有向简单图中,任意两个不同点之间都有方向相反的两条边,称有向完全图;若基图为 ,而每对不同点间只选一个方向,称竞赛图。三者边数依次为 。
定义5.2.4:无向简单图每个顶点度均为 ,称 正则图。 为0正则图, 为 正则图,彼得松图为3正则图。握手定理给出边数 ,所以 必为偶数; 奇数时 必为偶数。正则不表示所有画法具有同样几何对称性。
【例5.2.2】列出:(1)4阶3条边的全部非同构无向简单图;(2)3阶2条边的全部非同构有向简单图。
解:(1)只有星形 、四点路径 、三角形加孤立点三种,度数列分别为 。不能因题目要求三条边而漏掉最后一个图的孤立点。
(2)若两条边关联三个顶点,基图为一条二边路径,有同向链、两边共同指向中点、两边共同离开中点三种。若只关联两个顶点,则两边必须为相反方向,第三点孤立,共得到第四种。没有环且每个有向对至多一条边,保证这已覆盖全部可能。
定义5.2.5:无向简单图 的补图 与 使用相同顶点集;两个不同点在补图中相邻,当且仅当它们在原图中不相邻。补图不添加环,不删除孤立顶点。若 ,称自补图。图5.2.4(a)、(c)互为补图的同构类型,(b)为自补图。补图是在无向简单图的前提下定义,不能不加说明地套到多重图。
定义5.2.6:无向图的顶点与边交替序列 ,相邻顶点为对应边的端点,称从 到 的通路;长度是边出现次数 ,不是顶点个数。首尾相同称回路。按本书术语,边不重复称简单通路;再加上首尾相同称简单回路。除了首尾可以相同外,全部顶点不重复且边不重复,称初级通路或路径;首尾相同的初级回路称圈。某些文献把“简单路径”用于不重复顶点,本书则明确区分“简单”和“初级”,不能混用术语。
有重复边的通路或回路称复杂通路或复杂回路。有向图还要求每一步与边方向一致,不能沿反向边行走。初级通路一定简单,简单通路却可能重复顶点;环构成长1的圈,两条平行无向边可构成长2的圈,所以无向简单图的圈长至少3。圈长奇偶对应奇圈、偶圈。
简单图中顶点序列足以确定各步边,多重图中则必须保留边标号,否则同一顶点序列可能对应不同通路。图上没有标点的线段交叉处不能临时作为中转顶点。
定理5.2.5及推论5.2.2: 阶图中,不同顶点 之间若存在通路,就存在长度不超过 的初级通路。若已有通路重复某顶点,删去两次出现之间的闭合段,首尾连接关系仍合法且长度缩短;反复删除直到没有重复顶点,至多含 个顶点,因此至多 条边。有向图的删段同样保持方向。
定理5.2.6:若从 到自身有正长度回路,则有长度不超过 的正长度回路,可取从 出发的最短正长度回路并删去内部重复顶点的闭合段。推论5.2.3进一步要求原有回路为简单回路时,可得到经过 、长度不超过 的初级回路。这个“简单”条件对无向图不可随便省略:一条悬挂边来回走能回到起点,却不构成不重复边的圈。
【例5.2.3】无向完全图 的顶点标为 ,问圈的数量。
解:必须先说明计数约定。在同构类型意义下,只有一个三角形;按教材“定义意义”区分起点和行走方向,则有 六条。若只区分起点、将正反方向视为同一个,则有三种;若起点和正反方向都不区分,则只有一个。计数结果不同来自等同约定,不是同一个问题算出矛盾答案。
