第四部分 图论 主要内容 图的基本概念：图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性：欧拉图、哈密顿图、带权图及其应用 树：无向树及其性质、生成树与最小生成树、根树及其应用
第十四章 图的基本概念
第一节 图
E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 则G = <V,E>为一无向图，用图1表示G 图1
（7）顶点之间的相邻与邻接关系 设Ｇ＝<V,E>为无向图，vi,vj∈V,ek,el ∈E.若存在et ∈E,使得et=(vi,vj),则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。 （8）标定图与非标定图：顶点或边用字母标定的图为标定图，否则为非标定图。 （9）基图：将有向图各有向边均改成无向边后的无向图称为原来图的基图。
（4）+(D)=max{ d+(v)| vV(G)} +(D) =min{ d+(v)| vV(G)} (D) )=max{ d-(v)| vV(G)} (D) =min{ d-(v)| vV(G)} 分别称为D的最大出度，最小出度，最大入度，最小入度。 （5）奇顶点度：度为奇数的顶点 （6）偶度顶点：度为偶数的顶点 （7）悬挂顶点：度数为1的顶点
第二节 通路与回路
第三节 图的连通性
在上图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}是边割集吗？
第四节 图的矩阵表示 (5)第i行元素和为零，当且仅当该vi是孤立点 P288图14.14 （每条边关联两个顶点） （M（G）的第i行元素之和为vi的度数） （各顶点的度数之和等于边数的两倍） (5)第i行元素和为零，当且仅当该vi是孤立点 P284 图例
P288图14.15 （每列和为零，说明每条边既是始点也是终点） （M(D)中所有元素和为零) P285 图例
P289图14.16 (第i行为vi的出度） (第j行为vj的入度） (A（D）中所有元素之和） (A（D）中主对角线元素之和）
第十四章 习题课