In 1983, Harary proposed the concept of conditional connectivity, which is not only the integration of a variety of classical concepts of connectivity, but also yields a large number of new concepts of connectivity that having profound background in the design of optimization network, such as super vertex (edge) connectedness and restricted vertex (edge) connectivity and so on. For degree sequence and connected property of graph, there are usually two kinds of problems to be studied: one is forcible problem, that is, all graphs with the given degree sequence must have the connected property; the other is the potential problem, that is, there is a graph with the given degree sequence having the connected property. In this project, we will study degree sequence with super vertex (edge) connectedness and optimally restricted edge connectedness by using the theory and methods of optimization theory and graph theory. Specifically, we will study the potentially super vertex (edge) connected and optimally restricted edge connected graphical sequence, multi-graphical sequence and bipartite graphical sequence. Furthermore, we will consider the potentially super vertex (edge) connected and optimally restricted edge connected graphical sequence, multi-graphical sequence and bipartite graphical sequence with small diameter.
Harary于1983年提出了条件连通度的概念,它不仅统合了各类经典连通性概念,而且由此引发了大量新的在网络优化设计中具有深刻背景的连通性概念,如超点(边)连通性和限制性点(边)连通度等。对于度序列和图的连通性质,一般有两类问题需要研究:一类是强制性问题,即对所有满足给定度序列的图,都要满足给定的图的连通性质;另一类是存在性问题,也就是找到一个满足给定度序列的图,使得它满足给定的图的连通性质。本项目将综合应用组合优化和图论的理论和方法研究度序列和图的超点(边)连通性质、最优限制边连通性质的存在性问题。具体地说,我们将研究存在超点(边)连通、最优限制边连通的图序列、重图序列和二部图序列。更近一步,我们将考虑限定直径的存在超点(边)连通、最优限制边连通的图序列、重图序列和二部图序列。
图的各类条件连通度,如超(点)边连通性和限制性(点)边连通度等,是衡量网络可靠性的重要参数。对于度序列和图的连通性质,如何找到一个满足给定度序列的图使得它满足给定的图的连通性质,是属于度序列的存在性问题。本项目综合应用组合优化和图论的理论和方法研究图的度序列的连通性存在问题和图的各类条件连通度。我们得到如下主要结果:刻画了重图序列的超边连通性质;证明了连通的半点传递有向图是最大点连通的;笛卡尔积图k-限制点连通的相关结果(1<k<5);笛卡尔积图圈点连通度的相关结果;保持连通度的子树的研究结果。
{{i.achievement_title}}
数据更新时间:2023-05-31
基于多色集合理论的医院异常工作流处理建模
萃取过程中微观到宏观的多尺度超分子组装 --离子液体的特异性功能
信息熵-保真度联合度量函数的单幅图像去雾方法
吹填超软土固结特性试验分析
强震过程滑带超间隙水压力效应研究:大光包滑坡启动机制
图的度序列与连通图中的若干专题研究
图的彩虹连通与广义连通度
高阶限制边连通度的计算和优化
图的连通支配集构造算法研究