§1图的基本概念 (10)闭路(自回路):图中起始且终止于同一结 点的边 (闭路的箭头方向是没有意义的)6 (11)多重边(平行边):二个结点之间 方向相同的二条(多条)边 例
§1图的基本概念 (10)闭路（自回路）：图中起始且终止于同一结 点的边 (闭路的箭头方向是没有意义的 )例： (11)多重边（平行边）：二个结点之间 方向相同的二条（多条）边 例：
§1图的基本概念 《定义》:含有多重边的图称为多重图,非多重 图称为线图。 简单图:无自回路的线图称为简单图。由定义可 见,简单图是没有自回路和多重边的图。 例: /八 线图 简单图
§1图的基本概念 《定义》：含有多重边的图称为多重图，非多重 图称为线图。 简单图：无自回路的线图称为简单图。由定义可 见，简单图是没有自回路和多重边的图。 例：
§1图的基本概念 《定义》:有权图(赋权图)G是一个三元组〈V、E g〉或四元组〈V、E、f、g〉,其中Ⅴ为结点集 合,E为边的集合,是定义在V上的函数,g是定义 在边集合E上的函数。 实际上,有权图可以用一句话概括:每一条边或结点均 注上数字的图(数字可以为整数、正实数) 例:给出一个有权图 G=〈V、E、f、g〉,其图如下: 5 其中V={v1,V2V3} 4.6 E={e1,e2} e 84.5
§1图的基本概念 《定义》：有权图（赋权图）Ｇ是一个三元 组〈Ｖ、Ｅ、 ｇ〉或四元组〈Ｖ、Ｅ、ｆ、ｇ〉，其中Ｖ为结点集 合，Ｅ为边的集合，f是定义在Ｖ上的函数，g是定义 在边集合Ｅ上的函数。 实际上，有权图可以用一句话概括：每一条边或结点均 注上数字的图（数字可以为整数、正实数） 例：给出一个有权图 Ｇ＝〈Ｖ、Ｅ、ｆ、ｇ〉，其图如下： 其中Ｖ＝ {v1 ,v2 ,v3} Ｅ＝{e1 ,e2}
s1图的基本概念 (12)孤立结点:不与任何结点相连接的结点 (13)零图:仅包含孤立结点的图,又称(n,0)图 (14)平凡图:只有一个结点的图(1,0)图 《定义》:在有向图中,对于任何结点v,以v为始点的边的条 数,称为结点v的引出度数,记作;以终点的 边的条数称为v的引入度数,记作结点的v的大数 和引出度数之和称为v的度数,用deg(v)表示。 由定义可见 度数deg(v) 对无向图讲:结点的度數等乎以结点关联的边的条数
§1图的基本概念 (12)孤立结点：不与任何结点相连接的结点 (13)零图：仅包含孤立结点的图，又称（ｎ，０）图 (14)平凡图：只有一个结点的图（1，0）图 《定义》：在有向图中，对于任何结点v，以v为始点的边的条 数，称为结点v的引出度数， 记作 ；以v点为终点的 边的条数称为v的引入度数，记作 结点的v的引入度数 和引出度数之和称为v的度数，用deg（v）表示。 由定义可见： 度数deg（v）＝ 对无向图讲：结点的度数等于和该结点关联的边的条数 deg (v) + deg (v) + deg (v) − deg (v) − +
§1图的基本概念 例 (15)正则图:所有结点均具有同样度数的简单无向图 例 (一次正则图) b (二次正则图) (三次正则图)
§1图的基本概念 例： (15)正则图：所有结点均具有同样度数的简单无向图 例：