第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的多重子集， 其元素称为无向边，简称边