图的离散等周问题、条件连通性及其相关的Weierstrass型函数研究

自Harper引入图的离散等周问题以来,确定此类问题最优解在理论计算机领域、社会选择理论、网络可靠性得到广泛的应用。受Fusco,Maggi和Pratelli关于欧式空间上连续等周问题的稳定性的启发,图的离散等周问题最优解及稳定性问题更能激发研究者理解相关问题极值结构深层次的性质。.本项目拟研究主要问题以下:(1)若图具有边等周问题最优序,将其在笛卡尔乘积下的幂图的边等周问题字典序最优解与一类处处连续不可导函数构造的迭代函数系统的吸引子建立联系,得到Weierstrass型函数;(2)进一步分析幂图的边等周问题字典序最优解的稳定性、单调性、自相似性和分层结构;(3)将以此类幂图为拓扑结构网络的条件连通性的碎片的个数与Weierstrass型函数的水平集合建立联系,进而推广Knuth关于经典的Takagi函数可数多个水平集合的结论。

Since discrete isopermetric problem on graphs was introduced by Harper,determining its optimal solution has found widely applications in theoretical computer scienc- e,social choice theory and reliability analysis of networks.Motivated by results from Fusco,Maggi and Pratelli on the stability of isopermetric problem for Euclidean space,researcheres are driven to study of the corresponding extreme and stability problem.It often leads to a deeper understanding of the original extreme problem..In this project,(1)we mainly focus on the following relationship between lexicographic order optimal solutions of the edge isoperimetric problem on the cartesian power graph and an everywhere continuous nowhere differentiable function bulit by the attractor of iterated function system,and it is related to Weierstrass-type functions;(2) analyzing stability, monotonicity,self similarity and hierarchical structure properties of lexicographic order optimal solutions of the edge isoperimetric problem on these power graphs;(3) for these graphs,we plan to look for associations between the number of fragments of conditional connecti- vity and the level sets of Weierstrass-type functions,and to expand the Knuth's results on countably infinite level sets of classical Takagi function.