9课件第14章 图 论.pdfVIP

第十四章 图 论 第一节 图的基本概念 一、部分概念 u 1 图 图 G 是有序的三元数组(V （G），E （G）、ψ(G))其中 V （G） 是非空的顶点集，E （G）是和 V （G）不相交的边集合，ψ(G)是联系 G 中 的边和一对无序点之间的关联函数 .如 e ∈E （G），u,v∈V （G）且 ψG （e） = uv，则称 e 连接 u,v，u,v 称为 e 的端点 . 相邻 共一条边的二个端点. u 1 边相邻 共一个顶点的两条边 u u 2 5 环 具有同一端点的边 杆 具有不同端点的边. u3 u4 v(G) 图 G 所含有的顶点数. (G) 图 G 所含有的边数. 简单图 G 是一个无环且不存在两个顶点连接二条杆的图 . 有向图 每条边上的两个端点都有头尾之分的图 . 无向图 每条边上的两个端点都没有头尾之分的图 . 以下讨论中，如不作特别说明所述的图是无向的单图 . 完全图 每一对不同的顶点都有一条边相连的简单图，记为K . n 二部图 （偶图） 顶点集分成两个非空的子集 X 和 Y，使得每边有一个端点 在 X 中另一端点在Y 中 . 完全二部图 X 中每个顶点与Y 中每个顶点相连的二部图 . 顶点的度 顶点 的度是指 G 中与 关联的边的个数，每个环算作两条边 . v v 1 K K G K 5 4 33 33 定理 1 在任意图中，奇数度的顶点个数为偶数 . k--正则图 每个顶点的度均为k 的图 . 途径 是顶点和边的交错序列 w v eve v e v ，且边e 的端 0 1 1 2 k1 k1 k i 点是v ,v