Mathematical Sciences: Random Graphs

数学科学：随机图

• 批准号: 9002347
• 负责人: Boris Pittel
• 金额: --
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-15 至 1993-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9002347&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Random; Graphs

The principal investigator will study the vertex and edge connectivity of the giant component of a randomly evolving graph. One aspect of an Erdos-Renyi randomly evolving graph is a sudden appearance of the giant component, right after the moment when the average vertex degree becomes equal to 1. This research will lead to a better understanding of the likely behavior of such important extremal characteristics of the random graph as the chromatic number, the independence number and the matching number. The investigator will also study the giant component phenomenon in two other models, bipartite random graph and a Flory-Stockmayer-Whittle model of polymerization process. Finally, the investigator will work on fast probabilistic algorithms for Hamilton circuits and matchings.

主要研究者将研究顶点和边缘 随机演化图的巨连通性 Erdos-Renyi随机演化图的一个方面是突然的 巨大组件的出现，就在 平均顶点度变为等于1。 这项研究将 从而更好地了解这种可能的行为， 随机图的重要极值特征 色数、独立数与匹配 number. 调查人员还将研究巨型组件 现象在其他两个模型，二分随机图和一个 聚合过程的Flory-Stockmayer-Whittle模型 最后，研究人员将致力于快速概率 汉密尔顿电路和匹配的算法。