第7章图论 7.1无向图及有向图 72通路、回路与连通性 73图的矩阵表示 74欧拉( Euler)图 7.5哈密尔顿( Hamilton)图 7.6二部图 7.7平面图 7.8树
第7章 图论 7.1 无向图及有向图 7.2 通路、回路与连通性 7.3 图的矩阵表示 7.4 欧拉（Euler）图 7.5 哈密尔顿（Hamilton）图 7.6 二部图 7.7 平面图 7.8 树
第7章图论 图论的创始人是瑞士数学家欧拉,他于1736 年首次建立“图”模型,解决了哥尼斯堡七桥问 题 图论是一个新的数学分支,也 「很有实用 价值的学科,它在自然科学、社会科学等领域均有 很多应用近年来它受计算机科学蓬勃发展的刺激, 发展极其迅速,应用范围不断拓展,已渗透到诸 逻辑学、物理学、化 电子信息工 程在式 算机科学以及数学的其他分支中,特别是 机科学中,如形式语 数据结构、分布 、操作系统等方面均扮演着重要的角色
第7章 图论 图论的创始人是瑞士数学家欧拉，他于1736 年首次建立“图”模型，解决了哥尼斯堡七桥问 题. 图论是一个新的数学分支,也是一门很有实用 价值的学科,它在自然科学、社会科学等领域均有 很多应用.近年来它受计算机科学蓬勃发展的刺激， 发展极其迅速，应用范围不断拓展，已渗透到诸 如语言学、逻辑学、物理学、化学、电子信息工 程、计算机科学以及数学的其他分支中，特别是 在计算机科学中，如形式语言、数据结构、分布 式系统、操作系统等方面均扮演着重要的角色
7.1无向图及有向图 ■7.1.1图的概念 ■7.1.2度数与握手定理 ■7.1.3子图与补图 ■7.1.4图的同构
7.1 无向图及有向图 7.1.1图的概念 7.1.2度数与握手定理 7.1.3子图与补图 7.1.4图的同构
7.1.1图的概念 般几何上将图定义成空间一些点(顶点) 和连接这些点的线(边)的集合图论中将图定义 为 元组G=(V,E〉,其中∨表示顶点的集 E表示边的集合这样下图可表示为 V={v1,v2,v3,V4},E={e1,e2,e3,e4,e5e6}
7.1.1图的概念 一般几何上将图定义成空间一些点（顶点） 和连接这些点的线（边）的集合.图论中将图定义 为一个二元组G=〈V,E〉,其中V表示顶点的集合， E表示边的集合.这样下图可表示为 V={v1 ,v2 ,v3 ,v4 },E={e1 ,e2 ,e3 ,e4，e5 ,e6 }
7.1.1图的概念 定义7.1-1设A、B为任意的两个集合,称 {abya∈A∧b∈B} 为A与B的无序积,记作A&B 定义7.1-2一个无向图是一个有序的二元组〈V, E〉,记作G,其中 1)V(判)称为顶点集,其元素称为顶点或结 2)E称为边集,它是无序积∨&V的多重子集, 其元素称为无向边,简称边
7.1.1图的概念 定义7.1-1 设A、B为任意的两个集合，称 {{a,b}|a∈A∧b∈B} 为A与B的无序积，记作A&B. 定义7.1-2 一个无向图是一个有序的二元组〈V， E〉,记作G，其中 （1）V（≠φ）称为顶点集，其元素称为顶点或结 点； （2）E称为边集，它是无序积V&V的多重子集， 其元素称为无向边，简称边
7.1.2度数与握手定理 1.顶点的度数 设无向图G=VE〉,顶点ⅵ的度数记为d(v),是指与v 相关联的边的条数 在有向图D=V,E〉中,以顶点v为始点引出的边 的条数,称为该顶点的出度记为d():以顶点v为终点引 入的边的条数,称为该顶点的入度,记为d():而顶点的出 度数与入度数之和称为该顶点的度数,简称度,记为0(), d(v)=d()+d()
7.1.2度数与握手定理 1.顶点的度数 设无向图G=〈V,E〉,顶点vi的度数记为d(vi ),是指与vi 相关联的边的条数. 在有向图D＝〈V，E〉中，以顶点v为始点引出的边 的条数，称为该顶点的出度,记为d + (v)；以顶点v为终点引 入的边的条数，称为该顶点的入度,记为d - (v)；而顶点的出 度数与入度数之和称为该顶点的度数，简称度，记为d(v)， 即 d(v)＝d + (v)+d- (v)
7.1.2度数与握手定理 握手定理 定理7.1-1(握手定理)图G=V,E)为任意无 向图,其中V=V1,v2,…,n3旧E|=mm为边数),此 ∑d(Ⅵ)=2m, 即图中结点的度数之和等于边数的两倍
7.1.2度数与握手定理 2.握手定理 定理7.1-1 (握手定理)图G=〈V,E〉为任意无 向图，其中V={v1 ,v2 ,…,vn },|E|=m(m为边数)，此 时有 ∑ d(vi )=2m, 即图中结点的度数之和等于边数的两倍. n i=1
7.1.2度数与握手定理 定理71-2设D=V,E〉为任意有向图, V={1,V2,…n},旧E=m,此时有 ∑d(W)=2m ⅰ=1 且∑d(v)=∑d(w)=m 推论任何图(无向的或有向的)中,奇度数顶点的个 数是偶数
7.1.2度数与握手定理 定理7.1-2 设D=〈V,E〉为任意有向图， V={v1 ,v2 ,…,vn }，|E|=m，此时有 ∑d(vi )=2m 且∑d+ (vi )= ∑d- (vi )= m. 推论 任何图(无向的或有向的)中，奇度数顶点的个 数是偶数. n i=1 n i=1 n i=1
7.1.3子图与补图 1.子图 定义71-4设G=V,E〉,G=〈V,E"〉是两个图若 VV,且gE,则称是G的子图,G是G的母图,记作G 若G'国且G长G(即VV或贮E),则G是G的真子图 若G′G且V=V,则称G'是G的生成子图 设∨1且∨1,以V1为顶点集,以两端点均在V1中 的全体边边集的G的子图,称为V1导出的导出子图 设E1E,且E1,以E1为边集,以E1中边关联的顶 点的全体均顶点集的G的子图,称为E导出的导出子图
7.1.3子图与补图 1.子图 定义7.1-4 设G=〈V,E〉，G′=〈V′,E′〉是两个图.若 V′ V,且E′ E,则称G′是G的子图，G是G′的母图，记作G′ G. 若G′ G且G′≠G(即V′ V或E′ E)，则称G′是G的真子图. 若G′ G且V′= V，则称G′是G的生成子图. 设V1 V且V1≠φ，以V1为顶点集，以两端点均在V1中 的全体边为边集的G的子图，称为V1导出的导出子图. 设E1 E,且E1≠φ，以E1为边集，以E1中边关联的顶 点的全体为顶点集的G的子图，称为E1导出的导出子图
7.1.3子图与补图 2.补图 定义7.1-5设G=〈V,E〉是n阶无向简 单图以V为顶点,以所有能使G成为完全图 K的添加边组成的集合为边集的图,称为G 相对于完全图Kn的补图,简称G的补图,记 作G
7.1.3子图与补图 2.补图 定义7.1-5 设G=〈V,E〉是n阶无向简 单图.以V为顶点，以所有能使G成为完全图 Kn的添加边组成的集合为边集的图，称为G 相对于完全图Kn的补图，简称G的补图，记 作 G