Graph and Digraph Structure

图和有向图结构

• 批准号: 9701598
• 负责人: Paul Seymour
• 金额: $ 14.4万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9701598&HistoricalAwards=false
• 关键词: Graph; Digraph; Structure

Seymour 9701598 This project encompasses three lines of research in graph theory. (1) To design a fast algorithm to test if a directed graph has a circuit of even length. this is a well-known open problem, with a number of algebraic ramifications. At the time of this writing, the investigator, Neil Robertson and Robin Thomas have made substantial progress with it, but further development is necessary. (2) To develop a theory of digraph minors, parallel to the highly successful theory of graph minors; this is made approachable now because of the recent solution of the Galllai-Younger conjecture. The ``undirected'' theory has led to numerous results and algorithms of wide interest and applicability, and the investigator believes that similar success with the ``directed'' theory. (3) To complete work on solving Tutte's conjectured extension of the four-colour theorem. A group of researchers, including the PI, has found a new proof of the four-colour theorem itself, and they have reduced Tutte's conjecture to a form which can probably be proved by modifying this new proof. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.

西摩9701598 该项目包括图论的三条研究路线。(1)设计一个快速算法来测试有向图是否有偶数长度的回路。 这是一个众所周知的公开问题，具有许多代数分支。 在写这篇文章的时候，调查员尼尔·罗伯逊和罗宾·托马斯已经用它取得了实质性的进展，但进一步的发展是必要的。(2)发展一个理论的有向图未成年人，平行于非常成功的理论的图未成年人;这是接近现在，因为最近的解决方案的Gallai-Younger猜想。 “无方向”理论已经导致了许多结果和算法的广泛兴趣和适用性，研究人员认为，类似的成功与“有方向”的理论。 (3)完成解决Tutte四色定理的限制性扩展的工作。 一组研究人员，包括PI，已经发现了四色定理本身的新证明，他们已经将Tutte猜想简化为一种形式，这种形式可能可以通过修改这个新证明来证明。 这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。离散系统的行为对现代通信极为重要。例如，大型网络的设计，如电话系统中的网络设计，以及计算机科学中的算法设计，都要处理离散的对象集，这就需要使用组合研究。