第章图论 9,1.3多重图、简单图、完全图和正则图 定义917在图G中,连接同一对结点的多条相同边 称为平行边。平行边的条数称为该平行边的重数。含平行 边的图叫多重图。不含平行边和环的图叫简单图。 例如,在图94(a)中结点a和b之间有两条平行边,结 点b和c之间有三条平行边,结点b上有两条平行边,这两 条平行边都是环。图94(a)不是简单图 又如,在图94(b)中结点v1和v2之间有两条平行边。v 和v2之间的两条边,因为方向不同,所以不是平行边。图 94(b)不是简单图。 简单图不含平行边和环
第9章 图论 9.1.3多重图、简单图、完全图和正则图 定义9.1.7 在图G中，连接同一对结点的多条相同边 称为平行边。平行边的条数称为该平行边的重数。含平行 边的图叫多重图。不含平行边和环的图叫简单图。 例如，在图9.4(a)中结点a和b之间有两条平行边，结 点b和c之间有三条平行边，结点b上有两条平行边，这两 条平行边都是环。图9.4(a)不是简单图。 又如，在图9.4(b)中结点v1和v2之间有两条平行边。v2 和v3之间的两条边，因为方向不同，所以不是平行边。图 9.4(b)不是简单图。 简单图不含平行边和环
第章图论 b (b) 图9.4
第9章 图论
第章图论 定理91.3设G为n阶简单无向图,则△(G)≤n-1 证明:因为G有n个结点,G的任何结点ν最多只能与其 余的n-1结点相邻接;又因为G为简单图,既无平行边,又 无环。所以deg(v)-≤n-1。由y的任意性,就有 △(G)= maxi deg(v)|v∈≤n-1 定义91.8设G为n阶简单无向图,若G中的每个结点都 与其余的n-1个结点相邻接,则称G为n阶无向完全图。记为 K。在m阶无向完全图中,给每一条边任意确定一个方向, 所得到的图称为阶有向完全图。也记为Kn° 今后,将n阶无向完全图和n阶有向完全图统称为n阶完 全图
第9章 图论 定理9.1.3 设G为n阶简单无向图，则(G)≤n–1。 证明：因为G有n个结点，G的任何结点v最多只能与其 余的n–1结点相邻接；又因为G为简单图，既无平行边，又 无环。所以deg(v)≤n–1。由v的任意性，就有 (G) =maxdeg(v) | vV≤n–1。 定义9.1.8 设G为n阶简单无向图，若G中的每个结点都 与其余的n–1个结点相邻接，则称G为n阶无向完全图。记为 Kn。在n阶无向完全图中，给每一条边任意确定一个方向， 所得到的图称为n阶有向完全图。也记为Kn。 今后，将n阶无向完全图和n阶有向完全图统称为n阶完 全图
第章图论 定理914n阶完全图K的边数为 证明:在K中,每个结点都与其余的n-1结点相邻接, 即任何一对结点之间都有一条边,故边数应为C2n-=1) 定义91.9设G为m阶简单无向图,若G中每个结点都是k 度的,则称G为k次正则图
第9章 图论 定理9.1.4 n阶完全图Kn的边数为 证明：在Kn中，每个结点都与其余的n–1结点相邻接， 即任何一对结点之间都有一条边，故边数应为 定义9.1.9 设G为n阶简单无向图，若G中每个结点都是k 度的，则称G为k次正则图。 ( 1) 2 2 1 Cn = n n −
第章图论 914图的同构 在图论中只关心结点间是否有连线,而不关心结点的 位置和连线的形状。因此,对于给定的图而言,如果将图 的各结点安排在不同的位置上,并且用不同形状的弧线或 直线表示各边,则可以得到各种不同图形。所以,同一图 的图形并不惟一。由于这种图形表示的任意性,可能出现 这样的情况:看起来完全不同的两种图形,却表示着同 个图 例如,在图96中,(a)和(b)两个图的图形不同,但它们 的结构完全相同,是同一个图。 为了描述看起来不同,而其结构完全相同的图,引入 了同构的概念
第9章 图论 9.1.4图的同构 在图论中只关心结点间是否有连线，而不关心结点的 位置和连线的形状。因此，对于给定的图而言，如果将图 的各结点安排在不同的位置上，并且用不同形状的弧线或 直线表示各边，则可以得到各种不同图形。所以，同一图 的图形并不惟一。由于这种图形表示的任意性，可能出现 这样的情况：看起来完全不同的两种图形，却表示着同一 个图。 例如，在图9.6中，(a)和(b)两个图的图形不同，但它们 的结构完全相同，是同一个图。 为了描述看起来不同，而其结构完全相同的图，引入 了同构的概念