CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第六章图与网路分析 图是最直观的模型
©管理与人文学院 忻展红 1999，4 第六章 图与网路分析 图是最直观的模型
图论 Graph Theory 哥尼斯堡七桥问题( Konigsberg bridge problem) Leonhard euler(1707-1783)在1736年发表第一篇图论 方面的论文,奠基了图论中的一些基本定理 很多问题都可以用点和线来表示,一般点表示实体 线表示实体间的关联 A
2 B A C D 图论 Graph Theory • 哥尼斯堡七桥问题 (Königsberg Bridge Problem) • Leonhard Euler (1707-1783) 在1736年发表第一篇图论 方面的论文，奠基了图论中的一些基本定理 • 很多问题都可以用点和线来表示，一般点表示实体， 线表示实体间的关联 A B C D
6图与网路的基本概念 611图与网路 网路( Network) 节点( ertex) 边上具有表示连接强度 物理实体、事物、概念 的权值,如w 一般用v表示 又称加权图( Weighted 边(Ege) graph 节点间的连线,表示有 关联 一般用e;表示 图( Graph) 12 节点和边的集合 一般用G(V,E)表示 点集v{v1,2y,wn} 边集E={en} 图61
3 6.1 图与网路的基本概念 6.1.1 图与网路 • 节点 (Vertex) – 物理实体、事物、概念 – 一般用 vi 表示 • 边 (Edge) – 节点间的连线，表示有 关联 – 一般用 eij 表示 • 图 (Graph) – 节点和边的集合 – 一般用 G(V,E) 表示 – 点集 V={v1 ,v2 ,…, vn } – 边集E={eij } v 1 v 5 v 4 v 3 v 2 e 12 e 34 e13 e 24 e22 e'13 e 45 图 6.1 网路 (Network) 边上具有表示连接强度 的权值，如 wij 又称加权图(Weighted graph)
612无向图与有向图 所有边都没有方向的图称为无向图,如图61 在无向图中e1="n,或(v以=(v 当所有边都有方向时,称为有向图,用G(V,4)表示 在有向图中,有向边又称为弧,用a表示,i的顺序 是不能颠倒的,图中弧的方向用箭头标识 图中既有边又有弧,称为混合图
4 6.1.2 无向图与有向图 • 所有边都没有方向的图称为无向图，如图6.1 • 在无向图中 eij=eji，或 (vi , vj )=(vj , vi ) • 当所有边都有方向时，称为有向图，用G(V,A)表示 • 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序 是不能颠倒的，图中弧的方向用箭头标识 • 图中既有边又有弧，称为混合图
6.13端点,关联边,相邻,次 图中可以只有点,而没有边;而有边必有点 若节点v"之间有一条边,则称v是en的端点 ( end vertex),而t是节点v,v的关联边( incident edge) 同一条边的两个端点称为相邻 adjacent)节点,具有共同 端点的边称为相邻边 条边的两个端点相同,称为自环(se!lop);具有两个 共同端点的两条边称为平行边( parallel edges) 既没有自环也没有平行边的图称为简单图( simple graph) 在无向图中,与节点相关联边的数目,称为该节点的 次"( degree),记为d;次数为奇数的点称为奇点 (od)次数为偶数的点称为偶点(even);图中都是偶点的 图称为偶图( even graph)
6.1.3 端点，关联边，相邻，次 • 图中可以只有点，而没有边；而有边必有点 • 若节点vi , vj 之间有一条边 eij，则称 vi , vj 是 eij 的端点 (end vertex)，而 eij 是节点 vi , vj 的关联边(incident edge) • 同一条边的两个端点称为相邻(adjacent)节点，具有共同 端点的边称为相邻边 • 一条边的两个端点相同，称为自环(self-loop)；具有两个 共同端点的两条边称为平行边(parallel edges) • 既没有自环也没有平行边的图称为简单图(simple graph) • 在无向图中，与节点相关联边的数目，称为该节点的 “次”(degree)，记为 d ；次数为奇数的点称为奇点 (odd),次数为偶数的点称为偶点(even)；图中都是偶点的 图称为偶图(even graph)