通信网结构.ppt

一、?基本定义  设端集V={v1,v2,……vn} 边集E={e1,e2,…….em} eij=(vi,vj) 图G是V，E及R的集合 G={V,E}=V∪E=(V , E , R) 无向图: viRvj等价于vjRvi (eij=eji) 有向图: viRvj不等价于vjRvi 空图： V=φ(此时E必为空集) 孤立点图：E=φ,V≠φ 有限图：V,E均为有限元，∣V∣,∣E∣≠∞ 无限图：V,E无限元 图的几何表示： 端 — 点 边 — 线（不一定直线） 端—端有边——邻接 vi与vj邻接：有边 端—边相连——关联 eij与vi关联 有些应用场合，不许线交叉，不可画在平面图上（如印制，集成）——图的平面性。 有权图：通常对边与端附于一定权值，表示某 种性质。赋之值—权值， 权——权不限于一个f1(v1),f2(v2)...... 如：距，代价，流量，容量，转接容量...... 电流，电位...... 对通信网：端（站，局）；边（信道） 运输网： 车站 路 排水系统：泵源 管道 逻辑思维：状态 转移 如M序列,以 n=3为例，该序列周期为 =8 周期 为的序列有 种 对于n=3，共有2种，即： 子图：若A的端集与边集分别为G的端集与边 集的子集，则A为G的子图。 若A?G，且A?G，则A为G的真子集 真子集---G中至少有一个元素不在A内 若A=G，则A?G，A?G 图的运算： 设A={e1，e2}, e1=（v1，v3）, e2=（v3，v2） 设B={e1，e3}, e1=（v1，v3）, e3=（v1，v4） 并：A?B={e1， e2，e3} ——A，B 所有元素组成 交：A?B={e1 } ——A，B公共元素 若A?B =φ，则 A?B= A+B称直和 差：A-B={e2 } —属A但不属B之元素 A中去掉B的公共边 环和：A?B= {e2，e3} ——属A或属B，但不同属A与B(特有边) 注意：去端—同时去掉与该端关联的所有边 去边—不去关联端 二、 图的联结性 端度数：与该端关联的边数，记为：d(vi) 有向图：d+(vi)=离开vi的边数 d-(vi)=进入vi的边数 有：d(vi)=d+(vi)+d-(vi) 性质： 1)由定义而来： 任一边或与二端关联，或与一端关联（自环）。 所以每边均提供度数为2, 所以有下式 2）奇度数端有偶数个（或0个） 将端集分为：v1——奇度数端集 v2——偶度数端集 v= v1?v2 链、径、环的定义 边序列：相邻二边有公共端的边的串序排列（有限） (v1,v2), (v2,v3), (v3,v4),?? (vi, vj), 边序列中，边可重复出现——重边 端可重复出现——重端 链：无重边的边序列 ?链中每边只出现一次 ?一般链中只有二个端度数为奇数（起止不 同端） ?链可有环 径：无重边，无重端的边序列 ?径是无环的链（每边、每端只能出现一次） ?除起止端外，其他各端度数均为2 ?即网中的路径、路由 环： 闭链 联结图：任何二端间至少存在一条径的图 非联结图?分为几个最大联结子图?即几个“部分” “最大联结子图”—此图加一个属原图而不属此图的元素则此图不联结—即部分 G=A?B?C=A+B+C 全联结图：任何二端间有边（直通路由） ?最完整的联结图 ?对应全联结网 ?边、端数之间固定关系 (无自环,无重边) n=5的全联结图： 正则图：所有端度数都相同的联结图 d(vi)=常数（i=1,2,?n） ?联结性最均匀的图 ?无重边的全联结图是正则图，其d(v)=n-1 ?正则图不一定是全联结图 尤拉图(Euler): 端度数均为偶数的图 ?不一定是联结图 ?联结尤拉图是一笔画图 ?充要条件:联结尤拉图存在一个含全边的环(链) ?二尤拉图的环和也为尤拉图 M图:只有二个奇度数端的图 ?