• / 114
  • 下载费用:10 金币  

离散数学-图论基础.ppt

关 键 词:
离散数学-图论基础.ppt
资源描述:
第七章 图论基础 Graphs,2019年7月12日星期五,第一节 图的基本概念,一个图G定义为一个三元组:G= V —— 非空有限集合,V中的元素称为结点 (node)或 顶点(vertex) E —— 有限集合(可以为空),E中的元素称为边(edge) Φ —— 从E到V的有序对或无序对的关联映射(associative mapping),2019年7月12日星期五,图的基本概念,图G=中的每条边都与图中的无序对或有序对联系 若边e  E 与无序对结点[va, vb]相联系,即Φ(e)= [va, vb] (va, vb  V)则称e是无向边(或边、棱) 若边e  E与有序对结点相联系,即Φ(e)= (va, vb  V)则称e是有向边(或弧) va是e的起始结点, vb是e的终结点,2019年7月12日星期五,图的基本概念,若va和vb与边(弧)e相联结,则称va和vb是e的端结点 va和vb是邻接结点,记作:va adj vb (adjoin) 也称e关联va和vb,或称va和vb关联e 若va和vb不与任何边(弧)相联结,则称va和vb是非邻接结点,记作:va nadj vb 关联同一个结点的两条边(弧),称为邻接边(弧) 关联同一个结点及其自身的边,称为环(cycle),环的方向没有意义,2019年7月12日星期五,图的基本概念,若将图G中的每条边(弧)都看作联结两个结点 则G简记为: 每条边都是弧的图,称为有向图(directed graph)(如图b) 每条边都是无向边的图,称为无向图(undirected graph) (如图a) 有些边是弧,有些边是无向边的图,称为混合图(如图c),2019年7月12日星期五,图的基本概念,若图G中的任意两个结点之间不多于一条无向边(或不多于一条同向弧),且任何结点无环,则称G为简单图(如图c) 若图G中某两个结点之间多于一条无向边(或多于一条同向弧),则称G为多重图(如图a, b) 两个结点间的多条边(同向弧)称为平行边(弧), 平行边(弧)的条数,称为重数,2019年7月12日星期五,图的基本概念,在多重图的表示中,可在边(弧)上标注正整数,以表示平行边(弧)的重数 把重数作为分配给边(弧)上的数,称为权(weight) 将权的概念一般化,使其不一定是正整数,则得到加权图的概念: 给每条边(弧)都赋予权的图,叫做加权图(weighted graph) 记作G=,W是各边权之和,2019年7月12日星期五,图的基本概念,在无向图G=中,V中的每个结点都与其余的所有结点邻接,即 (va)(vb)(va, vb  V  [va, vb]  E),如图(a) 则称该图为无向完全图(complete graph),记作K|V| 若|V|=n,则|E|= C = n(n-1)/2,2 n,2019年7月12日星期五,图的基本概念,在有向图G=中,V中的任意两个结点间都有方向相反的两条弧,即 (va)(vb)(va,vbV  E∧E),如图(a) 则称该图为有向完全图,记作K|V| 若|V|=n,则|E|= P = n(n-1),2 n,2019年7月12日星期五,图的基本概念,在图G=中,若有一个结点不与其他任何结点邻接 则该结点称为孤立结点,如图(a)中的v4 仅有孤立结点的图,称为零图,零图的 E = ,如图(b) 仅有一个孤立结点的图,称为平凡图(trivial graph),如图(c),2019年7月12日星期五,问题,问题1:是否存在这种情况:25个人中,由于意见不同,每个人恰好与其他5个人意见一致? 问题2:是否存在这种情况:2个或以上的人群中,至少有2个人在此人群中的朋友数一样多?,2019年7月12日星期五,结点的次数,二、结点的次数 定义:在有向图G=中,对任意结点v  V 以v为起始结点的弧的条数,称为出度(out-degree) (引出次数),记为d+(v) 以v为终结点的弧的条数,称为入度(in-degree) (引入次数),记为d-(v) v的出度和入度的和,称为v的度数(degree) (次数),记为d(v) = d+(v) + d-(v),2019年7月12日星期五,结点的次数,定义:在无向图G=中,对任意结点v  V 结点v的度数d(v) ,等于联结它的边数 若结点v 上有环,则该结点因环而增加度数2 记G的最大度数为:  (G) = max {d(v)| v  V} 记G的最小度数为:  (G) = min {d(v)| v  V},2019年7月12日星期五,结点的次数,在图G中的任意一条边e  E,都对其联结的结点贡献度数2 定理:在无向图G=中,  d(v) = 2|E| 通常,将度数为奇数的
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:离散数学-图论基础.ppt
链接地址:https://www.weizhuannet.com/p-8800238.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开