平方图的一对多的3可覆盖性
发布时间：2018-11-09 14:37
【摘要】：给定一无向图G=(V,E),一对多的k可覆盖的定义:内部存在k条点不交的从任意一个源到任意k个汇的路覆盖图中每一个点.在文献[1]中,Park等人确立了一个充要条件,对任意的连通图的立方图都有一个连接一个源和三个汇点的一对多的3不交路覆盖.由于一个图的k可覆盖性需要点的连通度比较高,他找到了连通图的立方图存在一对多的3覆盖的充要条件,于是他考虑降低一下点的连通度,如2连通图的平方图是否也具有一对多的3可覆盖性.在文中,将展示2连通图的平方图是一对多的3可覆盖的.即2连通图的平方图总有一个3-DPC.
[Abstract]:Given an undirected graph G = (VVX E), the definition of a one-to-many k-covered graph is that there exists every point in the path covering graph with k disjoint points from any source to any k sink. In reference [1], Park et al established a sufficient and necessary condition that a one-to-many 3-disjoint path covering a cubic graph of any connected graph has a one-to-many one to many connected source and three meeting points. Because the k coverage of a graph requires a higher connectivity of a point, he finds a sufficient and necessary condition for a cubic graph of a connected graph to have a one-to-many 3-covering, so he considers reducing the connectivity of a given point. For example, whether the square graph of 2 connected graph also has 3 covering property of one to many. In this paper, we show that the square graph of 2-connected graph is one-to-many 3-covered. That is, the square graph of 2-connected graph always has a 3-DPC.
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
[Abstract]:Given an undirected graph G = (VVX E), the definition of a one-to-many k-covered graph is that there exists every point in the path covering graph with k disjoint points from any source to any k sink. In reference [1], Park et al established a sufficient and necessary condition that a one-to-many 3-disjoint path covering a cubic graph of any connected graph has a one-to-many one to many connected source and three meeting points. Because the k coverage of a graph requires a higher connectivity of a point, he finds a sufficient and necessary condition for a cubic graph of a connected graph to have a one-to-many 3-covering, so he considers reducing the connectivity of a given point. For example, whether the square graph of 2 connected graph also has 3 covering property of one to many. In this paper, we show that the square graph of 2-connected graph is one-to-many 3-covered. That is, the square graph of 2-connected graph always has a 3-DPC.
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
【相似文献】
相关期刊论文 前1条
1 路杨;冯玉强;韩雪;刘古泉;;面向电子商务的一对多谈判支持模型[J];中国管理信息化;2006年06期
相关重要报纸文章 前10条
1 记者 郭楠;期货公司积极备战资管“一对多”[N];期货日报;2014年
2 孙泽晖 李秀沛;医疗贿赂：“一对多”现象突出[N];检察日报;2014年
3 本报记者 谢忠设 刘方斌 通讯员 董荣荣;临沂化工交易试水“一对多”[N];中国化工报;2014年
4 记者 吴s，
本文编号：2320702
本文链接：https://www.wllwen.com/kejilunwen/yysx/2320702.html
