天津大学管理学院：《管理科学基础》课程PPT教学课件（运筹学）第五章 图与网络分析（5.1）图的基本概念

第一节图的基本概念 1.图与子图 图G=,E),其中Ⅳ={,…y为顶点集, E={e,…,e,为边集 子图G=,E其中V,cV,E,cE 如G: 6 4 简单图:无环、无多重边的图。 2021/2/24

2021/2/24 第一节 图的基本概念 1 . 图与子图    为边集。 图 ，其中 为顶点集， E e e G V E V v v , , ( , ) , , 1 1   = = = 子图G = (V ,E ),其中V V ,E  E。 e1 e2 e3 e5 e6 e4 e7 v3 v1 v2 v4 e2 e3 e5 e6 e4 v3 v1 v2 v4 如 G： G1： 简单图：无环、无多重边的图

2.关联与相邻 关联(边与点关系):若e是v,”,二点间的边, 记e=bv,]称v(或v,)与e关联。 相邻(边与边、点与点):点v,与v,有公共边, 称ν与ν相邻;边e与e有公共点,称e与e,相邻 3.链与圈 链:由G中的某些点与边相间构成的序列5eve2…e 若满足e=b,],则称此边点序列为G中的一条链 圈:封闭的链 连通图:图G中任二点间至少存在一条链。 2021/2/24

2021/2/24 2 . 关联与相邻 记 称 或 与 关联。 关联（边与点关系）：若 是 二点间的边， e v v v v e e v v [ , ], ( ) , 1 2 1 2 1 2 = 称 与 相邻；边 与 有公共点，称 与 相邻。 相邻（边与边、点与点）：点 与 有公共边， 1 2 1 2 1 2 1 2 v v e e e e v v 3 . 链与圈   [ , ], 1 1 1 2 2 1 若满足 则称此边点序列为 中的一条链。 链：由 中的某些点与边相间构成的序列 ， e v v G G v ev e e v + − =  圈：封闭的链。 连通图：图G中任二点间至少存在一条链

4.有向图与无向图 图G=,E)也可记G=(,},”功若点对无序 称G为无向图;否则称G为有向图。为区别起见,称有向图 的边为弧,记(ν)在图上用箭线表示 比较: 无向图:边b,],链 圈 有向图:弧(v,”,),路 回路 2021/2/24

2021/2/24 4. 有向图与无向图     的边为弧，记（ 在图上用箭线表示。 称 为无向图；否则称 为有向图。为区别起见，称有向图 图 也可记 若点对 无序， v ,v ), G G G = (V ,E ), G = ( v , [v ,v ] ). [v ,v ]     有向图：弧（ ），路 无向图：边 ，链 i j i j v v v v , [ , ] ，圈 ，回路 比较：

5.树 例1已知有5个城市,要在它们之间架设电 话线网,要求任2城市都可通话(允许通过其它城 市),并且电话线的根数最少。 特点:连通、无圈。 树—无圈的连通图,记为T。 2021/2/24

2021/2/24 5. 树 例1 已知有5个城市，要在它们之间架设电 话线网，要求任2城市都可通话（允许通过其它城 市），并且电话线的根数最少。 v1 v2 v3 v5 v4 特点：连通、无圈。 树——无圈的连通图，记为T

树的性质:(1)树的任2点间有且仅有1链 (2)在树中任去掉1边,则不连通; (3)在树中不相邻2点间添1边,恰成1圈; (4)若树7有m个顶点,则7有m-1条边 2021/2/24

2021/2/24 v1 v2 v3 v5 v4 树的性质：（1）树的任2点间有且仅有1链； （2）在树中任去掉1边，则不连通； （3）在树中不相邻2点间添1边，恰成1圈； （4）若树T有m个顶点，则T有m-1条边

6.图的部分(支撑)树 若图G=(V,E)的子图7=(V,E)是树, 则称T为G的部分树或支撑树。 特点—边少、点不 性质:G连通,则G必有部分树。 证:破圈、保连通。 2021/2/24

2021/2/24 6.图的部分（支撑）树 若图G=（V，E）的子图T=（V，E’）是树， 则称T为G的部分树或支撑树。 特点——边少、点不少。 性质：G连通，则G必有部分树。 证：破圈、保连通