图论与网络模型 图论与网络介绍 网络最大流问题
图论与网络模型 一 .图论与网络介绍 二.网络最大流问题
图的基本概念 1关系图:表示若干事物之间具有的某种关系的 例:若有ABc,D,E五个人,他们之间相互认识的情 况为A与C、D、E认识;B与C、E认识;C与A、D 认识;D与A、C、E认识;与A、B、D认识 我们用点分别表示人,相互认识用线连接就得到下 面的图:
一、图的基本概念 1.关系图:表示若干事物之间具有的某种关系的 图. 例:若有A,B,C,D,E五个人,他们之间相互认识的情 况为:A与C、D、E认识;B与C、E认识;C与A、D 认识;D与A、C、E认识;E与A、B、D认识. 我们用点分别表示人,相互认识用线连接,就得到下 面的图: A ° ° B E ° ° C D °
2图是由若干个点和连线构成的 记为 G=V,E) 其中:V-点集;E-边集 点v称为顶点;连线e称为边或弧 例:哥尼斯堡七桥问题(从某点出发经过 七座桥各一次后回到起点) B C A
2. 图是由若干个点和连线构成的. 记为: G = (V, E) 其中: V----点集; E----边集. 点v 称为顶点; 连线e 称为边(或弧). 例: 哥尼斯堡七桥问题 (从某点出发,经过 七座桥各一次后回到起点) A B C D ° A B° C° D °
若两个点Ⅵ,有边e连接则称e与v,v是关联的; 若两条边e,e有公共顶点v,则称el,e是相邻的 3点的度--与点关联的边的条数记为d(v) 奇点--度数为奇数的点 偶点--度数为偶数的点 结论:一个图中奇点的个数必为偶数 4连通图:在一个图中若任何两个顶点之间至少有 一条路线连接则称这个图为连通图 5圈Cn:一条封闭的路线称为圈
若两个点v1, v2 有边e 连接,则称e与v1, v2 是关联的; 若两条边e1, e2 有公共顶点v,则称e1, e2 是相邻的. 3.点的度---- 与点v关联的边的条数. 记为d (v) 奇点----度数为奇数的点 偶点----度数为偶数的点 结论: 一个图中奇点的个数必为偶数. 4.连通图: 在一个图中,若任何两个顶点之间至少有 一条路线连接,则称这个图为连通图. 5. 圈 Cn : 一条封闭的路线称为圈
6完全图Kn:n个点之间都有边相连的图 如图 K2 K3 K4 7网络当圈的边弧有方向且各弧给予一定的权的图
6.完全图 Kn: n个点之间都有边相连的图. 如图: ° ° K2 ° ° ° K3 ° ° ° ° K4 7.网络:当图的边(弧)有方向,且各弧给予一定的权的图