1、 第三篇 图 论1图论的简介：n 图论是数学的一个分支，是研究由线连接的点集的理论，它以图为研究对象。图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力、开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印制电路板的设计、图案识辩、地图着色、情报检索，也应用于诸如语言学、社会结构、经济学、运筹学、遗传学等方面。234n 图论作为一个数学分支，有一套完整的体系和广泛的内容，这里主要围绕与计算机科学有关的知识，只介绍图论的一些基本概念、定理和研究内容，同时给出一些相应的算法和
2、应用，目的在于今后对计算机有关学科的学习和研究时，可以以图论的基本知识作为工具。5本章主要内容：n 图n 图的基本概念n 通路、回路和连通图n 图的连通性n 图的矩阵表示6第八章 图n 离散数学研究的图与几何图形、机械图形的区别：离散数学研究的图是另一种数学结构，不关心图中顶点的位置、边的长短和形状 , 只关心顶点与边的联结关系。n 图可分为 有限图 和 无限图 两类 , 本书只研究有限图 , 即顶点和边都是有限集合。 78.1 图的基本概念n 8.1.1图的定义n 定义 8.1 一个图是一个有序对（ V,E)， 记为G=(V,E)， 其中 V=v1,v2, vn为有限非空集合， vi 称为
3、结点 ，简称 V是 顶点集，图 G的顶点集用 V(G)表示；E=e1,e2, em 为有限的边集合， ei 称为 边 ，每个 ei 都有 V中的结点对与之相对应，称 E为 边集或弧集 。即每条边连结中的某两个点，图 G的边集用 E(G)表示。 8n 如果 E中的边对应中 ei 的结点对是无序的 vi, vj， 称 ei 是 无向边 ，记作 ei = vi , vj ，称 vi ， vj 是 ei 的两个端点，顶点 vi ， vj 称为是 邻接的或相邻的 ，边 ei 和顶点vi 与 vj 均称为是 关联的 ，即 ei 关联于 vi 与vj 。9n 关联于同一顶点的边称为 自回路 或 自环 ，关联于同一对顶点的边多于一条时，称这些边是 平行边 ，其条数称为是边的 重数 ；不与任何顶点邻接的顶点称为 孤立点 ；只与一条边关联的顶点称为 悬挂点 ，它所关联的边称为 悬挂边 。n 如果 ei 与结点有序对 (vi, vj)相对应， 称 ei 是 有向边 ，记 ei =（ vi , vj） ，称 vi为 ei的始点 ， vj为 ei 的 终点 。 10
