运筹学讲义 §2.1.1图的基本概念(1) 图( graph):用(顶)点代表对象,顶点之间的边表示对象之间的关系 滨州 “图是关系的数学表达” 齐南 注:图和几何图形不同.几何图形描述物体 青岛 的形状和结构:图仅反映对象之间的关系 聊城 图中顶点的相对位置,顶点之间的边的长短 粗细对反映对象之间的关系并不重要.如 角形两边之和大于第三边”等几何定理 枣庄 在图论中不再成立 图的表示:G=(V,E),其中V为顶点集,E为边集一般地,要求V≠Φ,但E无此要求 顶点( vertex,结(节)点,node):v∈V;边(edge):e=nv∈E;端点( endpoint):l,p 顶点数:v=1:边数:E= 边数E称为图的规模(sie) 注:集合的阶( cardinality):S=集合S中含有的元素的个数 种关系:顶点与顶点相邻(邻接)( adjacent);边与边相邻(邻接);顶点与边关联( incident 有限图( finite graph):v<+o,E<+o 无限图( infinite graph): otherwise 注:以后如不加说明,在本课程中出现的图总是指有限图 空图( empty graph):l≤v<+∞,E=0; 非空图( nonempty graph): otherwise 平凡图( trivial graph):v=1,E=0 非平凡图( nontrivial graph): otherwise. 连杆(link):两个端点不重合的边 环(loop):两个端点重合的边 重边( multiedge,平行边, parallel edge): several edges with the same two distinct endpoints
运 筹 学 讲 义 1 §2.1.1 图的基本概念(1) 图 图（graph）：用（顶）点代表对象，顶点之间的边表示对象之间的关系. “图是关系的数学表达”. 注：图和几何图形不同.几何图形描述物体 的形状和结构；图仅反映对象之间的关系， 图中顶点的相对位置，顶点之间的边的长短 粗细对反映对象之间的关系并不重要.如 “三角形两边之和大于第三边”等几何定理 在图论中不再成立. 图的表示： G = (V, E) ，其中 V 为顶点集， E 为边集.一般地，要求 V ，但 E 无此要求. 顶点(vertex，结(节)点，node)： vV ；边(edge)：e = uvE ；端点(endpoint)：u, v . 顶点数： = V ；边数： = E . 边数 称为图的规模（size）. 注：集合的阶（cardinality）： S = 集合 S 中含有的元素的个数. 三种关系：顶点与顶点相邻（邻接）（adjacent）；边与边相邻（邻接）；顶点与边关联（incident）. 有限图（finite graph）： +, + ； 无限图（infinite graph）：otherwise. 注：以后如不加说明，在本课程中出现的图总是指有限图. 空图（empty graph）： 1 +, = 0 ； 非空图（nonempty graph）：otherwise. 平凡图（trivial graph）： = 1, = 0 ； 非平凡图（nontrivial graph）：otherwise. 连杆（link）：两个端点不重合的边； 环（loop）：两个端点重合的边； 重边（multiedge，平行边，parallel edge）：several edges with the same two distinct endpoints
运筹学讲义 连杆 环 重边 注:以后如不加说明,“边”总是指连杆. 简单图( simple graph):不含有重边和环的图; 重图( multigraph):不含有环(可含有重边)的图 显然,若图G是简单图,则E≤C2(何时取等号?) PFTa R(plane graph): a graph any two edges of which intersect only at their endpoint 非平面图( nonplane graph): otherwise. 平面图 非平面图 可平面图( planar graph): a graph which can be drawn in a plane(平面) so that any two edges of it intersect only at their endpoints 非可平面图( nonplanar graph): otherwis 可平面图 非可平面图 注:一个非平面图有可能是可平面图! 权( weight):给每条边以一个数字(如距离,长度,流量,费用等) 赋权图( weighted graph):边带有权的图 无向图( graph):边无方向的图 有向图( digraph, directed graph): otherwise. 混合图( mixed graph):有的边有方向,有的边无方向的图 注:以后如不加说明,“图”无向图 图的同构( graphic isomorph i sm) 定义对图G1,G2,若彐一一映射( bi jection)f:(G1)→V(G2),使得
运 筹 学 讲 义 2 注：以后如不加说明，“边”总是指连杆. 简单图（simple graph）：不含有重边和环的图； 重图（multigraph）：不含有环（可含有重边）的图. 显然，若图 G 是简单图，则 2 C （何时取等号？）. 平面图（plane graph）：a graph any two edges of which intersect only at their endpoints； 非平面图（nonplane graph）：otherwise. 可平面图（planar graph）：a graph which can be drawn in a plane(平面) so that any two edges of it intersect only at their endpoints； 非可平面图（nonplanar graph）：otherwise. 注：一个非平面图有可能是可平面图！ 权（weight）：给每条边以一个数字（如距离，长度，流量，费用等）； 赋权图（weighted graph）：边带有权的图. 无向图（graph）：边无方向的图； 有向图（digraph，directed graph）：otherwise. 混合图（mixed graph）：有的边有方向，有的边无方向的图． 注：以后如不加说明，“图”无向图. 图的同构（graphic isomorphism） 定 义 对 图 1 2 G ,G ， 若 一一映射（ bijection ） : ( ) ( ) V G1 V G2 f → ，使得
运筹学讲义 vv∈(G1),∈E(G1),有f(u)f(v)∈E(G2),则称G1与G2同构( isomorphic),记作G1=G2 简言之,两个图的结构完全一样即同构 f:a>4,b→>2,c→>1 d→3,e→>5 同构的两个图 不同构的两个图 三 K4的同构图 当图的规模较大时,判断图是否同构很困难. 注:(1)同构是图的一种等价关系,具有反身性,对称性和传递性 (2)同构的两个图有相同的顶点数和边数,反之不真:顶点数或边数不相同的两个图不可能同 构.如 (3)同构关系保持图的对应顶点的度和邻接性 (4)任一v个顶点的简单图必同构于K的某一子图 例1(1)试画出顶点数为3的所有不同构的简单图. (2)试画出顶点数为4的所有不同构的简单图 解:(1)顶点数为3的不同构的简单图共有4个,分别为
运 筹 学 讲 义 3 , ( ), ( ) V G1 uv E G1 u v ，有 ( ) ( ) ( ) E G2 f u f v ，则称 G1 与 G2 同构（isomorphic），记作 G1 G2 . 简言之，两个图的结构完全一样即同构. 同构的两个图 3, 5 : 4, 2, 1, → → → → → d e f a b c 当图的规模较大时，判断图是否同构很困难. 注：（1）同构是图的一种等价关系，具有反身性，对称性和传递性. （2）同构的两个图有相同的顶点数和边数，反之不真；顶点数或边数不相同的两个图不可能同 构.如 （3）同构关系保持图的对应顶点的度和邻接性. （4）任一 个顶点的简单图必同构于 K 的某一子图. 例 1（1）试画出顶点数为 3 的所有不同构的简单图. （2）试画出顶点数为 4 的所有不同构的简单图. 解：（1）顶点数为 3 的不同构的简单图共有 4 个，分别为
运筹学讲义 (2)顶点数为4的不同构的简单图共有11个,分别为 E≤C4=6 E=3 E=5 E=6 若干特殊的图 完全(完备)图( complete graph):任两个互异顶点之间均恰好有唯一一条边相连的图 表示:K △区 K 注:由完全图的定义易见,在顶点数相同的所有简单图中,K,的边数最多,且边数为C2
运 筹 学 讲 义 4 （2）顶点数为 4 的不同构的简单图共有 11 个，分别为 6 2 C4 = = 0 =1 = 2 = 3 = 4 = 5 = 6 若干特殊的图 完全（完备）图（complete graph）：任两个互异顶点之间均恰好有唯一一条边相连的图. 表示： K . 注：由完全图的定义易见，在顶点数相同的所有简单图中， K 的边数最多，且边数为 2 C
运筹学讲义 性质:若G是简单图,则(1)E≤C2:(2)E=C2分G是完全图 证明:(1)注:(2)显然.→∵5(K,)=C,若G不是完全图,则由(G)=C知,G必 含有环或重边,与G是简单图矛盾 例2有n个药箱,每两个药箱恰好装有一种相同的药,每种药也恰好装在两个药箱里,问有多少 种药? 解:以n个药箱为顶点,两个顶点之间有一条边相连当且仅当两个药箱有一种相同的药,作完全 图Kn∴药的种数=s(Kn)=C2■ 分(部)图(偶图, bipartite graph):G=(X,Y)s.t.X∪Y=V,X∩Y=Φ,E:X←>Y v=5的不同构的连通的二分图共有5个: 一般地,规定二分图为简单图 例4一个二分图:3-方体图(3-cube) 注:k一方体(k-cube) Thek- cube is the graph whose vertices are the ordered k- tuples(有序k元组)of0sand1's, wo vertices being joined if and only if they differ in exactly one coordinate(坐标,分量)
运 筹 学 讲 义 5 性质：若 G 是简单图，则（1） 2 C ；（2） = C 2 G 是完全图. 证明：（1）注；（2） 显然. 2 ( ) Kp = C ，若 G 不是完全图，则由 2 ( ) G = C 知， G 必 含有环或重边，与 G 是简单图矛盾.▌ 例 2 有 n 个药箱，每两个药箱恰好装有一种相同的药，每种药也恰好装在两个药箱里，问有多少 种药？ 解：以 n 个药箱为顶点，两个顶点之间有一条边相连当且仅当两个药箱有一种相同的药，作完全 图 Kn . 药的种数 ( ) Kn = 2 = Cn .▌ 二分（部）图（偶图，bipartite graph）： G = (X ,Y) s.t. X Y = V, X Y = ，E : X Y . = 5 的不同构的连通的二分图共有 5 个： 一般地，规定二分图为简单图. 例 4 一个二分图：3-方体图（3-cube） ▌ 注： k −方体（ k −cube） The k −cube is the graph whose vertices are the ordered k −tuples（有序 k 元组） of 0’s and 1’s， two vertices being joined if and only if they differ in exactly one coordinate（坐标，分量）. e.g