第章图论 定义9.12若图G有n个结点,则称该图为n阶图。 定义91.3设G为图,如果G的所有边都是有向边,则 称G为有向图。如果G的所有边都是无向边,则称G为无向 图。如果G中既有有向边,又有无向边,则称G为混合图 图93的(a)是无向图,(b)是有向图,(c)是混合图 (a (b) 图9.3
第9章 图论 定义9.1.2 若图G有n个结点，则称该图为n阶图。 定义9.1.3 设G为图，如果G的所有边都是有向边，则 称G为有向图。如果G的所有边都是无向边，则称G为无向 图。如果G中既有有向边，又有无向边，则称G为混合图。 图9.3的(a)是无向图，(b)是有向图，(c)是混合图
第章图论 在一个图中,若两个结点由一条边(有向边或无向边) 关联,则称其中的一个结点是另一个结点的邻接点。并 称这两个结点相互邻接。 在一个图中不与任何结点相邻接的结点,称为孤立 点 在一个图中,如果两条边关联于同一个结点,则称 其中的一个边是另一个边的邻接边。并称这两个边相互 邻接。关联于同一个结点的一条边叫做环或自回路。在 有向图中环的方向可以是顺时针,也可以是逆时针,它 们是等效的 定义9.14由孤立点组成的图叫做零图。由一个孤立 点组成的图叫做平凡图。 根据定义9.1.4,平凡图一定是零图
第9章 图论 在一个图中，若两个结点由一条边(有向边或无向边) 关联，则称其中的一个结点是另一个结点的邻接点。并 称这两个结点相互邻接。 在一个图中不与任何结点相邻接的结点，称为孤立 点。 在一个图中，如果两条边关联于同一个结点，则称 其中的一个边是另一个边的邻接边。并称这两个边相互 邻接。关联于同一个结点的一条边叫做环或自回路。在 有向图中环的方向可以是顺时针，也可以是逆时针，它 们是等效的。 定义9.1.4 由孤立点组成的图叫做零图。由一个孤立 点组成的图叫做平凡图。 根据定义9.1.4，平凡图一定是零图
第章图论 912结点的度及其性质 定义91.5设G=<VE>是图,veV,与v相关联的边数 叫做结点v的度。记为deg(v)。规定,自回路为所在结点 增加2度 在图G=<VE>中,度数最大(小)的结点的度叫做图G 的最大(小)度,记为△(G)6(G)图G的最大度和最小度 表示为: A(G= max deg()|v∈ 6(G)= mint deg()|v∈ 在图91中,△(G)=4,δ(G)=0
第9章 图论 9.1.2结点的度及其性质 定义9.1.5 设G=V,E是图，vV，与v相关联的边数 叫做结点v的度。记为deg(v)。规定，自回路为所在结点 增加2度。 在图G=V,E中，度数最大(小)的结点的度叫做图G 的最大(小)度，记为(G)((G))。图G的最大度和最小度 表示为： (G)=max deg(v) | vV (G)= min deg(v) | vV 在图9.1中， (G)=4，(G)=0
第章图论 定理9.1.1在任何图G=<VE>中,所有结点度数的和 等于边数的2倍。即 ∑deg(v)=2 v∈I 证明:图的每一条边都和两个结点相关联,为每个 相关联的结点增加一度,给图增加两度。所以所有结点度 数的和等于边数的2倍。 推论在任何图G=<VE>中,度数为奇数的结点必为 偶数个
第9章 图论 定理9.1.1 在任何图G=V,E中，所有结点度数的和 等于边数的2倍。即： = 2|E| 证明：图的每一条边都和两个结点相关联，为每个 相关联的结点增加一度, 给图增加两度。所以所有结点度 数的和等于边数的2倍。 推论 在任何图G=V,E中，度数为奇数的结点必为 偶数个。 vV deg(v)
第章图论 定义9.16设G=<VE>是有向图,v∈V,射入(出)结点 v的边数称为结点v的入(出)度。记为deg(v)(degt(v) 显然,任何结点的入度与出度的和等于该结点的度数 Ep deg(v)=deg(v)+deg+(v) 定理91.2在有向图中,所有结点入度的和等于所有 结点出度的和 证明:在有向图中每一条边对应一个入度和一个出 度,为图的入度和出度各增加1。所以,所有结点入度的 和等于边数,所有结点出度的和也等于边数
第9章 图论 定义9.1.6 设G=V,E是有向图，vV，射入(出)结点 v的边数称为结点v的入(出)度。记为deg－(v) (deg＋(v))。 显然，任何结点的入度与出度的和等于该结点的度数， 即deg(v)=deg－(v)+deg＋(v)。 定理9.1.2 在有向图中，所有结点入度的和等于所有 结点出度的和。 证明：在有向图中每一条边对应一个入度和一个出 度，为图的入度和出度各增加1。所以，所有结点入度的 和等于边数，所有结点出度的和也等于边数