《运筹学》课程PPT教学课件（Operations Research）第六章 图论（6.1）图的基本概念

运筹学 Operations Research §6.1图的基本概念 图( graph):用顶点代表对象,顶点之间的边表示对象之 间的关系 滨州 济南 青岛 聊城◎ 枣庄 注:图与几何图形不同. 2021/2/20

2021/2/20 1 运 筹 学 Operations Research §6.1 图的基本概念 图（graph）：用顶点代表对象，顶点之间的边表示对象之 间的关系. 注：图与几何图形不同

运筹学 Operations Research 图的表示:G=(,E) 顶点集:V 边集:E 顶点( vertex):y∈ 边(edge):e=l∈E 顶点数:v= 边数 2021/2/20 2

2021/2/20 2 运 筹 学 Operations Research 图的表示： G = (V, E) 顶点集： 边集： V E 顶点(vertex)： 边(edge)： vV e = uvE 顶点数： 边数：  = V  = E

运筹学 Operations Research 三种关系: 顶点与顶点相邻(邻接)( adjacent); 边与边相邻(邻接); 顶点与边关联( incident) 空图( empty graph):1≤v<+∞,E=0 平凡图( trivial graph):w=1,E=0 2021/2/20 3

2021/2/20 3 运 筹 学 Operations Research 三种关系： 顶点与顶点相邻（邻接）（adjacent）； 边与边相邻（邻接）； 顶点与边关联（incident）. 空图（empty graph）： 1   +, = 0 平凡图（trivial graph）：  = 1, = 0

运筹学 Operations Research 连杆(link):两个端点不重合的边 环(1oop):两个端点重合的边; 重边( multiedge):具有相同端点的若干条边 13 ●卩 连杆 环 重边 简单图( simple graph):不含有重边和环的图 赋权图( weighted graph):边带有权(表示距离,长 度,流量,费用等的数字)的图 2021/2/20 4

2021/2/20 4 运 筹 学 Operations Research 连杆（link）：两个端点不重合的边； 环（loop）：两个端点重合的边； 重边（multiedge）：具有相同端点的若干条边. 简单图（simple graph）：不含有重边和环的图. 赋权图（weighted graph）：边带有权（表示距离，长 度，流量，费用等的数字）的图

运筹学 Operations Research 无向图( graph):边无方向的图; 有向图( digraph): otherwise. 图的同构( graphic isomorphism):结构完全一样的图 如 4 b 2021/2/20

2021/2/20 5 运 筹 学 Operations Research 无向图（graph）：边无方向的图； 有向图（digraph）：otherwise. 图的同构（graphic isomorphism） ：结构完全一样的图. 如

运筹学 Operations Research 不同构的两个图 人 三 K4的同构图 2021/2/20 6

2021/2/20 6 运 筹 学 Operations Research

运筹学 Operations Research 例1(1)试画出顶点数为3的所有不同构的简单图 (2)试画出顶点数为4的所有不同构的简单图 解:(1) 2 2021/2/20 7

2021/2/20 7 运 筹 学 Operations Research 例1（1）试画出顶点数为3的所有不同构的简单图. （2）试画出顶点数为4的所有不同构的简单图. 解：（1） （2）……▌

运筹学 Operations research 完全图( complete graph):任两个互异顶点之间均恰好有 唯一一条边相连的图 表示:K △区级 KI K K 4 5 性质若G是简单图,则(1)E≤C;(2)何时取=? 2021/2/20 8

2021/2/20 8 运 筹 学 Operations Research 完全图（complete graph）：任两个互异顶点之间均恰好有 唯一一条边相连的图. 表示： K (1) ;(2) ? 2 性质 若G是简单图，则   C 何时取 =

运筹学 Operations Research 二分图( bipartite graph):G=(XY,Y) 2.3 2021/2/20

2021/2/20 9 运 筹 学 Operations Research 二分图（bipartite graph）： G = (X ,Y)

运筹学 Operations Research 个二分图: 1 2…-+---51 2 3-方体 2021/2/20 10

2021/2/20 10 运 筹 学 Operations Research 一个二分图： 3-方体