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

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

Theme 1. Difficult Combinatorial Search ProblemsThe 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 FrameworksGraphs 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