华北理工大学：《运筹学》课程教学课件（讲稿）第7章 图与网络分析（Graph Theory and Network Analysis）

图与网络分析(Graph Theory and Network Analysis)图与网络的基本知识树及最小树问题最短路问题最大流问题

图与网络分析 (Graph Theory and Network Analysis) 图与网络的基本知识 最短路问题 树及最小树问题 最大流问题

图论Graph Theory哥尼斯堡七桥问题（KonigsbergBridgeProblem)，LeonhardEuler（1707-1783）在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联BB

B A C D • 哥尼斯堡七桥问题 (Königsberg Bridge Problem) • Leonhard Euler (1707-1783) 在1736年发表第一篇 图论方面的论文，奠基了图论中的一些基本定理 • 很多问题都可以用点和线来表示，一般点表示实 体，线表示实体间的关联 图论 Graph Theory A B C D

例1下图是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。北京天津石家庄太原塘沽济南青岛郑州徐州连云港重庆武汉上海南京

例1 下图是我国北京、上海、重庆等十四 个城市之间的铁路交通图，这里用点表示 城市，用点与点之间的线表示城市之间的 铁路线。诸如此类还有城市中的市政管道 图，民用航空线图等等。 太原 石家庄 北京 天津 塘沽 济南 青岛 徐州 连云港 南京 上海 郑州 重庆 武汉

例2有六支球队进行足球比赛，我们分别用点i，…，V表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v,队战胜v2队，队战胜V3队，V3队战胜v队，如此等等。这个胜负情况，可以用有向图反映出来。7

例2 有六支球队进行足球比赛，我们分别用点 v1 ，.，v6表示这六支球队，它们之间的比赛情况， 也可以用图反映出来，已知v1队战胜v2 队，v2 队战胜 v3 队，v3 队战胜v5队，如此等等。这个胜负情况，可 以用有向图反映出来。 v3 v5 v2 v4 v v 6 1

第一节图与网络的基本知识（一）、图与网络的基本概念EBC1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）

第一节 图与网络的基本知识 （一）、图与网络的基本概念 E A D B C 1、一个图是由点和连线组成。（连线可带箭头，也可 不带，前者叫弧，后者叫边）

V=和 V中元素的无序对的一个图是由点集一个集合E={e构成的二元组，记为G=（V，E，其中V中的元素V叫做顶点，V表示图G的点集合；E中的元素ek叫做边，E表示图G的边集合。例eiV= (11,12,V3,v4,'s,ve)Vie2E =[er,e2,es,es,es,er,er,eg,eg,eio]3e10ei = (11, V2]e, =(11, V2]eg = (V2, V3]e4 = (v3, V4)eoV65Oeges =(V1, V3]eg =(v3, Vs)eg =(vs, Ve)e, =(v3, vs)图1e, =(V6, v]e10 =(1, v6)

v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 一个图是由点集 和 中元素的无序对的 一个集合 构成的二元组，记为G =(V，E)，其 中 V 中的元素 叫做顶点，V 表示图 G 的点集合；E 中的元素 叫做边，E 表示图 G 的边集合。 = {vV j} }{ k = eE j v k e V 例 = { , vvvvvvV 654321 } },{ 10987654321 = ， eeeeeeeeeeE },{ 211 = vve },{ 212 = vve },{ 323 = vve },{ 434 = vve },{ 315 = vve },{ 536 = vve },{ 537 = vve },{ 658 = vve },{ 669 = vve },{ 6110 = vve 图1

2、如果一个图是由点和边所构成的，则称其为无向图，记作C=（V，E)，连接点的边记作（Vi，V,），或者（Vi，Vi）。3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D-（V，A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从V指向V；的弧，记作(vi，v)。VV= {Vi, V2, V'3, V4, Vs, V},A =((v1, v3), (v2, V),(v2, V3),(V2, Vs) , (v3, Vs) , (v2, V4)V's2(v4, Vs) , (vs,V4) , (v's, V) )图2如果两个点u，vEV,且边(u,v)EE,则称u、v两点相邻如果两条边e，e;EE，且它们有一个公共端点u，则称e;，e,相邻，边e，e,称为点u的关联边

2、如果一个图是由点和边所构成的，则称其为无向图，记作 G = (V，E)，连接点的边记作（ vi , vj），或者（ vj , vi）。 3、如果一个图是由点和弧所构成的，那么称它为有向图，记 作 D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧 集合。一条方向从 vi指向 vj 的弧，记作( vi , vj)。 v 4 v v 6 1 v 2 v 3 v 5 V = { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 }， A = {( v 1 , v3 ) , ( v 2 , v 1) , ( v 2 , v 3 ) , ( v 2 , v 5 ) , ( v 3 , v 5 ) , ( v 2 , v 4 ) ( v 4 , v 5 ) , ( v 5 , v 4 ) , ( v 5 , v 6 ) } 图 2 如果两个点 u ， v ∈V,且边(u,v) ∈E,则称 u 、 v两点相邻 。 如果两条边 ei ， ej ∈ E，且它们有一个公共端点 u，则称 ei ， ej 相邻，边 ei ， ej 称为点 u 的关联边

4、一条边的两个端点是相同的，那么称为这条边是环。5、如果两个端点之间有两条以上的边，那么称为它们为多重边。6、一个无环，无多重边的图称为简单图，一个无环有多重边的图称为多重图。eiD台e2ese10Vses台4VDV5e9Oe简单图多重图

4、一条边的两个端点是相同的,那么称为这条边是环。 5、如果两个端点之间有两条以上的边，那么称为它们 为多重边。 6、一个无环，无多重边的图称为简单图，一个无环， 有多重边的图称为多重图。 v 1 v 5 v 4 v v 3 2 简单图 v 1 v 2 v 5 v 4 v 3 多重图 v 1 v 2 v 3 v 4 v 5 v 6 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 e10

7、每一对顶点间都有边相连的无向简单图称为完全图有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图

7、每一对顶点间都有边相连的无向简单图称为完全图。 有向完全图则是指任意两个顶点之间有且仅有一条有 向边的简单图

8、以点V为端点的边的个数称为点V的度（次），记作d()。图中(d(v)=4，d(v)=4（环计两度）度为零的点称为弧立点，ei度为1的点称为悬挂点，Ve2悬挂点的关联边称为悬挂边，度为奇数的点称为奇点，er0S3度为偶数的点称为偶点。esV6eC2

度为零的点称为弧立点， 度为1的点称为悬挂点， 悬挂点的关联边称为悬挂边， 度为奇数的点称为奇点， 度为偶数的点称为偶点。 8、以点 v为端点的边的个数称为点v 的度（次），记 作 。 vd )( 图中 d( v 1)= 4 ， d( v 6)= 4 （环计两度 ） v 1 v 2 v 3 v 4 v 5 v 6 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 e10