第8章图的基本概念 图8.1.1
第8章 图的基本概念 图 8.1.1 (a) (b) (c) e 1 e2 e 3 e 4 e 5 e6 1 2 4 3 5
第8章图的基本概念 下面介绍一些图的基本概念和常用术语 邻接点同一条边的两个端点 孤立顶点没有边与之关联的顶点。 零图顶点集V非空但边集E为空集的图。 平凡图1,=m=0的图 邻接边关联同一个顶点的两条边。 环关联同一个顶点的一条边((ν,ν)或(ν,v〉)
第8章 图的基本概念 下面介绍一些图的基本概念和常用术语。 邻接点 同一条边的两个端点。 孤立顶点 没有边与之关联的顶点。 零图 顶点集V非空但边集E为空集的图。 平凡图 |V|=1，|E|=m=0的图。 邻接边 关联同一个顶点的两条边。 环 关联同一个顶点的一条边（（v，v）或〈v，v〉）
第8章图的基本概念 平行边关联一对顶点的m条边(m≥2,称重数,若 是有向边则应方向相同)。 多重图含有平行边(无环)的图 简单图不含平行边和环的图。 完全图每对顶点间均有边相连的无向简单图。n阶 完全图记作Kn 竞赛图在K的每条边上任取一个方向的有向图。 有向完全图每对顶点间均有一对方向相反的边相 连的有向图
第8章 图的基本概念 平行边 关联一对顶点的m条边（m≥2，称重数，若 是有向边则应方向相同）。 多重图 含有平行边（无环）的图。 简单图 不含平行边和环的图。 完全图 每对顶点间均有边相连的无向简单图。n阶 完全图记作Kn。 竞赛图 在Kn的每条边上任取一个方向的有向图。 有向完全图 每对顶点间均有一对方向相反的边相 连的有向图
第8章图的基本概念 由完全图的定义易知,无向完全图K的边数为 E(K =Ch=n(n-1) 有向完全图G的边数为 E(G)=n(n-1)
第8章 图的基本概念 由完全图的定义易知，无向完全图Kn的边数为 2 1 ( ) ( 1) 2 E K C n n n n = = − 有向完全图G的边数为 E G n n ( ) ( 1) = −
第8章图的基本概念 顶点的度数顶点所关联的边数。顶点v的度数记 作d(ν)。在有向图中,以顶点ν为起点的边数称顶点 v的出度,记作d(v);以顶点v为终点的边数称顶点v 的入度,记作a(v)
第8章 图的基本概念 顶点的度数 顶点所关联的边数。顶点v的度数记 作d（v）。在有向图中，以顶点v为起点的边数称顶点 v的出度，记作d +（v）;以顶点v为终点的边数称顶点v 的入度，记作d -（v）