71 图的基本概念第7章图72 图的存储结构73 图的遍历74 生成树和 .pdf

第7章 图 7.1 图的基本概念 7.2 图的存储结构 7.3 图的遍历 7.4 生成树和最小生成树 7.5 最短路径 7.6 拓扑排序 本章小结 7.1 图的基本概念 7.1.1 图的定义 图（Graph ）G由两个集合V （vertex ）和E （Edge） 组成，记为G=(V，E)，其中V 是顶点的有限集合，记为 V(G) ，E是连接V 中两个不同顶点（顶点对）的边的有限 集合，记为E(G)。 　　说明：对于n个顶点的图，对每个顶点连续编号，即 顶点的编号为0…n-1。通过编号唯一确定一个顶点。 在图G中，如果代表边的顶点对是无序的，则称G为无 向图。无向图中代表边的无序顶点对通常用圆括号括起来 用以表示一条无向边。 如果表示边的顶点对是有序的，则称G为有向图。在有 向图中代表边的顶点对通常用尖括号括起来 。 1 7.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中，若存在 2 3 0 一条边(i, j)，则称顶点i和顶点j 为此边的两个端点，并称它们 互为邻接点。 4 在一个有向图中，若存在 一条边i, j，则称此边是顶点i 的一条出边，同时也是顶点j 的 1 一条入边；称顶点i和顶点j分别 为此边的起始端点（简称为起 点）和终止端点（简称终点）； 2 3 0 称顶点i 和顶点j 互为邻接点。 4 2. 顶点的度、入度和出度 在无向图中，一个顶点的邻接点的数目, 或者说是 与该顶点相连接的边的数目，称为该顶点的度。 在有向图中，以顶点i为终点的入边的数目，称为 该顶点的入度。以顶点i为起点的出边的数目，称为该 顶点的出度。一个顶点的入度与出度的和称为该顶点的 度。 若一个图中有n个顶点和e条边，每个顶点的度为 di （1≤i≤n ），则有： 1 n e＝ d 2 ∑ i i 1 　例．一个无向连通图中有16条边，所有顶点的度均小于5， 度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2 个，则该图有 个顶点。 A.10 B.11 C.12 D.13 解：设该图有n个顶点，图中度为i的顶点数为ni （0≤i≤4 ）， 显然n =0，n=3+4+2+n +n =9+n ，而度之和 0 1 0 1 =4 ×3+3 ×4+2 ×2+n =28+n ，而度之和=2e=32，所以有 1 1 28+n =32，得n =4，n=9+n =13 。本题答案为D 。 1 1 1