5.1 图的定义及运算
本章目录 · 1 节
本章导读
图论用顶点表示对象,用边表示对象之间的联系。图的数学结构取决于端点、方向和边的重数,不取决于纸上点的具体坐标或线段是否弯曲。改变画法不一定改变图;改变端点或箭头方向则可能改变图。
教材先定义无序积 。为了记录无向边,把无序对简写成 ,这里 ,并允许 。它与此前使用尖括号的有序对 不同,阅读时要先确认图是有向还是无向。
定义5.1.1:无向图 的顶点集 为非空有限集,边集 是 的有限多重子集。多重集合允许同一对端点之间有多条边,每条边应有自己的身份或重数;不能用普通集合去重操作把平行边删成一条。定义5.1.2:有向图 的顶点集同上,边集是 的有限多重子集,每条边都有指定的起点、终点。
【例5.1.1】分别画教材给定的无向图和有向图。
解:(1),按图中的标号,。 端点相同但仍是两条独立边, 是环,共7条边。
(2),,共7条有向边。 同向平行, 方向相反,不能归成同一组有向平行边。
顶点数称为图的阶;边数与顶点数分别记 。没有边的 阶图称零图,记 ;只有一个顶点且无边的零图 称平凡图。教材起初要求非空顶点集,但运算可能删除全部顶点,因此另允许顶点集为空的空图,记 。空图没有顶点,零图则可以有多个孤立顶点,不应混淆。
顶点、边附有指定名字或编号的图称标定图,无指定名字的称非标定图。把有向图的各条边去掉方向得到其基图,仍应保留边的重数;反向的两条边去向后可能成为无向平行边。
无向边的两个端点与它关联;非环边与每个端点关联一次,环与其唯一顶点关联两次。相连的顶点称相邻,具有共同端点的边称相邻。有向边从起点指向终点,环的两者相同;两有向边可前后衔接,是指一条的终点等于另一条的起点。没有任何边关联的顶点称孤立点,只有环的顶点并非孤立点。
在无向图中,邻域 ,闭邻域 ;关联集 包含与 关联的全部边。邻域是顶点集合,平行边不重复增加邻点;关联集要保留不同边,不能把两者的大小当成同一个数。环不把 加入开邻域,但仍属于关联集。
有向图的后继元集为 ,先驱元集为 。邻域取二者并,闭邻域再加 。例如图5.1.1(a)中 ,,;图(b)中 。
定义5.1.3:无向图中端点相同的多条边称平行边,条数称重数;有向图还要求它们起点和终点分别相同。含平行边的图称多重图;既无平行边也无环的图称简单图。只有环而无平行边的图仍不是简单图。图5.1.1的两个图都不是简单图。
定义5.1.4:同为有向或同为无向的 ,若 ,且全部保留边端点都在 中,则 是 的子图。至少一项严格包含称真子图; 时称生成子图,它可以有原图没有的孤立点。
给定非空顶点子集 ,保留这些顶点及原图中两端都在其中的全部边,得顶点导出子图 。给定非空边子集 ,只保留这些边及它们关联的全部端点,得边导出子图 。导出子图要求“全部满足条件的边”或“恰好关联的端点”,不能凭画法任意再删。
定义5.1.5给出四种基本运算。删边 或 只删除指定边,保留全部顶点,即使因此出现孤立点;删顶点 或 同时删除相关顶点及其关联的全部边。收缩非环边 时,先删该边,再将两个端点合并为新顶点,其余边端点随之更新,可能产生平行边或环。加边是在指定顶点之间增加一条新的边,允许改变重数;若希望结果保持简单图,还需另行排除环和已有邻接边。
定义5.1.6讨论两个无孤立点、类型相同的图。并图的顶点集为 ,边集为 ;差图以 为边集,以这些边关联的全部端点为顶点集;交图同样由 及关联端点组成;环和由对称差 及关联端点组成。这里差图会去掉不再关联剩余边的顶点,与前面“删边但保留全部顶点”的操作不同,二者即使使用相似减号也须看清定义。
比较带标号的边时,应先统一边的身份;不同平行边不能只因端点相同而被当成同一条边。若用边的多重集合计算,需保持同一重数运算约定:并取最大重数,交取最小重数,差取非负重数差,对称差取重数差的绝对值,而不是把所有重数无条件相加。
顶点集不交的图称不交图;边集不交称边不交或边不重。顶点不交必然边不交,反向不成立。相同图的差为空图;边不交时,交图为空、环和等于并图,并有 ,这些等式按本节规定的图运算解释,不能忽略顶点集的处理规则。
