有向超欧拉图及相关问题研究

项目名称： 有向超欧拉图及相关问题研究

项目编号： No.11401103

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 洪艳梅

作者单位： 福州大学

项目金额： 22万元

中文摘要： 欧拉问题是图论中非常古老的一个问题，一个(有向)图称为超欧拉图是指存在一个(有向)闭迹通过图中所有点.对无向图，自Catlin提出约化方法以后超欧拉问题变得非常热门. 本项目拟研究有向图上的超欧拉问题，从最小度和连通度充分条件入手，逐步刻画有向图的超欧拉性，包括局部结构性刻画与禁止子图结构刻画等, 并给出在这些条件下寻找支撑欧拉子图的算法. 同时，借鉴Catlin的思想提出适用于有向图的约化方案，建立有向图超欧拉问题的一个一般性方法；最后，拟把(有向)图的超欧拉问题与(有向)图连通度结合起来，提出支撑(边/弧)连通度的概念，拟把研究(有向)图连通度的方法应用到(有向)图的超欧拉性上面，并研究这两个问题之间的本质联系. 该问题的研究与有向哈密尔顿问题以及无向图上的超欧拉问题密切相关.

中文关键词： 有向欧拉子图；超欧拉；最小度；连通度；

英文摘要： Euler problem is a very old problem of graph theory.A (directed) graph is called supereulerian if there is a (directed) closed trace through all the vertices. The supereulerian problem on undirected graph became very popular since Catlin's reduction metho

英文关键词： Eulerian subdigraph；Supereulerian；minimum degree；connectivity；