图的基本术语8.1.2在一个无向图中，若存在一条边（i，j)，则称顶点和顶点j为该边的两个端点，并称它们互为邻接点，即顶点是顶点的一个邻接点，顶点也是顶点的一个邻接点。在一个有向图中，若存在一条边<i，>，则称此边是顶点的一条出边同时也是顶点的一条入边。和分别为此边的起始端点（简称为起点）和终止端点（简称终点）。并称顶点是i的出边邻接点，顶点是j的入边邻接点。6/40
在一个无向图中，若存在一条边(i，j)，则称顶点i和顶点j为该边的 两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶 点j也是顶点i的一个邻接点。 在一个有向图中，若存在一条边<i，j>，则称此边是顶点i的一条出边， 同时也是顶点j的一条入边。i和j分别为此边的起始端点（简称为起点） 和终止端点（简称终点）。并称顶点j是i的出边邻接点，顶点i是j的 入边邻接点。 6/40
在无向图中，顶点所具有的边的数目称为该顶点的度。在有向图中，顶点i的度又分为入度和出度，以顶点为终点的入边的数目，称为该顶点的入度。以顶点为起点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。。若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的度为d；（o≤i≤n-1），则有：一di02i=07/40
在无向图中，顶点所具有的边的数目称为该顶点的度。在有向图中， 顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该 顶点的入度。以顶点i为起点的出边的数目，称为该顶点的出度。一 个顶点的入度与出度的和为该顶点的度。 若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的 度为di（0≤i≤n-1），则有： 7/40
【例8.1】一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有多少个顶点？解：设该图有n个顶点，图中度为i的顶点数为n；（0≤i≤4）。n4=3, n3=4。要使顶点数最少，该图应是连通的，即ng=0。n=n4+n3+n2+n1+ne=7+n2+n1,即n2+n1=n-7。度之和=4×3+3×4+2×n2+n1=24+2nz+n1≤24+2(n2+n1)=24+2X(n-7)=10+2n。而度之和=2e=32，所以有10+2n≥32，即n≥11。即这样的无向图至少有11个顶点。8/40
【例8.1】一个无向图中有16条边，度为4的顶点有3个，度为3的顶 点有4个，其余顶点的度均小于3，则该图至少有多少个顶点？ 解：设该图有n个顶点，图中度为i的顶点数为ni（0≤i≤4）。 n4=3，n3=4。 要使顶点数最少，该图应是连通的，即n0=0。 n=n4+n3+n2+n1+n0=7+n2+n1，即n2+n1=n-7。 度之和=4×3+3×4+2×n2+n1=24+2n2+n1≤24+2(n2+n1)= 24+2×(n-7)=10+2n。 而度之和=2e=32，所以有10+2n≥32，即n≥11。 即这样的无向图至少有11个顶点。 8/40
完全无向图中的每两个顶点之间都存在着一条边。含有n个顶点的完全无向图有n(n-1)/2条边。完全有向图中的每两个顶点之间都存在着方向相反的两条边。含有n个顶点的完全有向图包含有n(n-1)条边。（b）一个完全有向图（a）一个完全无向图9/40
完全无向图中的每两个顶点之间都存在着一条边。含有n个顶点的 完全无向图有n(n-1)/2条边。 完全有向图中的每两个顶点之间都存在着方向相反的两条边。含有 n个顶点的完全有向图包含有n(n-1)条边。 1 2 0 3 1 2 0 3 （a）一个完全无向图 （b）一个完全有向图 9/40
当一个图接近完全图时，则称为稠密图。当一个图含有较少的边数（即无向图有e<<n(n-1)/2,有向图有e<<n(n-1)）时，则称为稀疏图。10/40
当一个图接近完全图时，则称为稠密图。 当一个图含有较少的边数（即无向图有e<<n(n-1)/2，有向图有 e<<n(n-1)）时，则称为稀疏图。 10/40