Difficult Combinatorial Search Problems and Graph Theory Models and Algorithms for Carbon Frameworks

Carbon框架的困难组合搜索问题以及图论模型和算法

• 批准号: RGPIN-2014-05864
• 负责人: Myrvold, Wendy
• 金额: $ 2.33万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708298
• 关键词: Difficult; Combinatorial; Search; Problems; Graph

Theme 1. Difficult Combinatorial Search Problems The graph coloring problem takes as input a graph G and the aim is to color the vertices of G so that adjacent vertices are different colors. This problem is so hard that there are some reasonably small graphs such that finding an optimal coloring is either overly time consuming or not feasible using existing algorithms. One goal of my research is to find faster graph coloring algorithms. The graph coloring problem has many applications including determination of conflict-free schedules, map coloring, and register allocation. Venn diagrams give pictorial representations of all possible logical relations between a finite collection of sets. We plan to exhaustively generate new classes of Venn diagrams. The computational results can be used to investigate conjectures about Venn diagrams. One example of an open question is Winkler's conjecture that any simple Venn diagram can be extended to a larger simple Venn diagram with the addition of a single curve. An (r, g)-cage is a graph having a minimum number of vertices such that each vertex has degree r and the minimum cycle size is g. Cages have attracted a lot of interest from the graph theory community and have properties that make them appealing for a network topology. There are many values for r and g where there is a large gap between the lower bounds given for an (r,g)-cage and the upper bound coming from the number of vertices in a smallest known existing r-regular graph of girth g. Our intent is to try to close those gaps. Theme 2. Graph Theory Models and Algorithms for Carbon Frameworks Graphs are often used by chemists as models for molecules. The molecules considered in this research have carbon frameworks. Fullerenes correspond to 3-regular planar graphs with face sizes 5 or 6. Although fullerenes were only recently discovered (1985) they have been the subject of intense research because of their unique chemistry and potential application in materials science, electronics, nanotechnology and medicine. Benzenoids are unsaturated molecules composed of fused hexagonal rings. More generally, polycyclic aromatic hydrocarbons (PAH's) have mixtures of ring sizes 4, 5, 6 and 7. They occur naturally and as atmospheric pollutants from burning fuels, and can be carcinogenic. The goal of this research is to better understand properties of these molecules such as currents, stability, geometry, and resonance energy. Understanding induced currents is critical for interpreting chemical characterisation by Nuclear Magnetic Resonance. Graph theory models for current represent current by giving a direction and magnitude to each edge of the molecular graph. Graph theory models for currents can be easier to implement and give a simpler representation of the answer than some other numerical approaches. They facilitate prediction of currents for infinite families of molecules. One of our goals is to compare current models to each other looking for inconsistencies and anomalies. The next step is to refine or redevelop the graph theory based methods so that they more accurately reflect the current. The graph theoretic approaches published so far are better suited to benzenoids which are often fairly flat. We plan to develop extensions for predicting current in 3D structures such as fullerenes, or cases where the graph has no perfect matchings or where the cycle sizes vary as for PAH's. Further research will involve determining correlations between computed graph invariants and chosen molecular properties. Definition of new invariants is all too easy, but we will identify those that are efficiently computable and offer information content related to geometry and energy of molecular and extended carbon frameworks

主题1.困难的组合搜索问题 图着色问题以图G为输入，目标是对图G的顶点着色，使得相邻的顶点是不同的颜色。这个问题是如此困难，有一些合理的小图，这样找到一个最佳的着色要么是过于耗时或不可行的使用现有的算法。我的研究目标之一是找到更快的图着色算法。图着色问题有许多应用，包括确定无冲突的时间表，地图着色，寄存器分配。 维恩图给出了有限集合之间所有可能的逻辑关系的图形表示。我们计划穷尽生成新的类的维恩图。计算结果可用于研究文氏图的性质。一个开放问题的例子是温克勒猜想，任何简单的维恩图都可以通过添加一条曲线扩展为更大的简单维恩图。 一个（r，g）-笼是一个有最少顶点数的图，使得每个顶点的度为r，最小圈长为g。笼吸引了图论社区的大量兴趣，并且具有使它们对网络拓扑有吸引力的属性。有许多值的r和g，其中有一个大的差距之间的下限（r，g）-笼和上限来自最小的已知现有的r-正则图的围长g的顶点数。我们的目的是努力缩小这些差距。 主题2.碳框架的图论模型与算法 化学家经常用图作为分子的模型。本研究中考虑的分子具有碳框架。富勒烯对应于面大小为5或6的3-正则平面图。虽然富勒烯是最近才发现的（1985年），但由于其独特的化学性质和在材料科学，电子学，纳米技术和医学中的潜在应用，它们一直是激烈研究的主题。苯环是由稠合六方环组成的不饱和分子。更一般地，多环芳烃（PAH）具有环尺寸为4、5、6和7的混合物。它们是自然产生的，也是燃烧燃料产生的大气污染物，可能致癌。这项研究的目的是更好地了解这些分子的性质，如电流，稳定性，几何形状和共振能量。了解感应电流对于解释核磁共振化学表征至关重要。 电流的图论模型通过给分子图的每条边一个方向和大小来表示电流。电流的图论模型可以更容易实现，并给出比其他一些数值方法更简单的答案表示。他们促进预测电流的无限家庭的分子。我们的目标之一是将当前的模型相互比较，寻找不一致和异常。下一步是改进或重新开发基于图论的方法，使其更准确地反映当前的情况。到目前为止，发表的图论方法更适合于通常相当平坦的benzenetrat。我们计划开发扩展预测电流的三维结构，如富勒烯，或情况下，图形没有完美的匹配或循环大小不同的PAH的。 进一步的研究将涉及确定计算的图形不变量和选择的分子性质之间的相关性。新的不变量的定义太容易了，但是我们将确定那些有效计算的不变量，并提供与分子和扩展碳框架的几何和能量相关的信息内容