Pfaffian图的结构性质及相关问题研究

基本信息
批准号:11171279
项目类别:面上项目
资助金额:36.00
负责人:张莲珠
学科分类:
依托单位:厦门大学
批准年份:2011
结题年份:2015
起止时间:2012-01-01 - 2015-12-31
项目状态: 已结题
项目参与者:郭晓峰,卢福良,林峰根,陈锦松,郭利涛,庄蔚,杨卫华,魏首柳
关键词:
多项式BrickPermanentk圈可扩图Pfaffian图
结项摘要

本项目研究近年来图论领域备受关注的图的Pfaffian性问题。Thomas 2006年世界数学家大会上45分钟的报告(A survey of Pfaffian orientations of graphs)介绍了图的Pfaffian定向方面的研究成果和相关问题的进展。Pfaffian定向是物理学家 Kasteleyn为解决NP-难的完美匹配计数问题(统计物理中称为Dimer问题)提出来的。如果图有Pfaffian定向,那么它的完美匹配计数问题可以在多项式时间内解决。本项目将从结构上研究图的Pfaffian性,重点研究可定向闭曲面上Pfaffian图的结构性质、极小Brick(3-连通双临界图)的结构特征(在紧割分解的意义下图的Pfaffian性可归结为Brick 的Pfaffian性)、k-圈可扩图与图的Pfaffian性的内在联系、结构刻画以及Permanent多项式的计算方法。

项目摘要

本项目重点研究图的Pfaffian性的结构性质及相关的问题。一个无向图的一个Pfaffian定向是指图的的一个定向使得这的斜邻接矩阵的行列式等于它的完美匹配数的平方。一个Pfaffian图是指它有一个Pfaffian定向的图。一般图的完美匹配计数问题是NP-难的,但如果一个图有Pfaffian定向,那么它的完美匹配计数问题可以在多项式时间内解决。本项目研究主要包含以下几个方面。.图的Pfaffian性的结构性质研究。主要研究结果包含:(1)得到了可嵌入在环面上的Pfaffian图的一些充分条件,应用这些充分条件,我们证明了可嵌入在环面上的若干网格子图是Pfaffian图的充分必要条件是图非二部图,并给出了这些图Pfaffian定向的方法:(2)证明了S. Norine 和 R. Thomas提出的一个猜想:每一个极小3-连通双临界图含有四个3度顶点。(3)从匹配minor的角度刻画了任一个图与偶长路的乘积图是Pfaffian图的和充分必要条件;(4)证明了循环图Cn(a1,a2,…,ak)是Pfaffian图当且仅当 k 等于1, 或 k=2 并且 a1+a2 为奇数这一性简洁的刻画与判定.(5)给出了含有一个顶点的度为点数的一半的1-可扩二部图的一个定向是Paffian的判定,同时给出了一个多项式时间算法。.完美匹配计数问题的研究。我们用图的Pfaffian定向的方法进行研究,分别得到了嵌入在克莱因瓶上的8.8.4网格和8.8.6网格图的完美匹配数的显式表达式和嵌入在环面上的几类4-正则网格图的完美匹配数的显式表达式等。.线图的哈密顿性和超欧拉图的性质等问题的研究。主要研究结果包含:(1)证明了有至多9个3度顶点的图的3-连通、实质4-连通线图是哈密顿的,并且所有条件是紧的;(2)证明了每一个边度至少7的3-边连通、实质6-边连通图或每一个边度至少6, 至多24个3度顶点的3-边连通、实质5-边连通图是collapsible;(3)证明了每一个3-连通、实质11-连通线图或每一个7-连通线图是哈密顿连通的,并基于图的最小边度和限制性边连通度等参数证明了一个3-边连通图是collapsible的若干充分条件等。

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

DOI:{{i.doi}}
发表时间:{{i.publish_year}}

暂无此项成果

数据更新时间:2023-05-31

其他相关文献

1

Protective effect of Schisandra chinensis lignans on hypoxia-induced PC12 cells and signal transduction

Protective effect of Schisandra chinensis lignans on hypoxia-induced PC12 cells and signal transduction

DOI:10.1080/15287394.2018.1502561
发表时间:2018
2

F_q上一类周期为2p~2的四元广义分圆序列的线性复杂度

F_q上一类周期为2p~2的四元广义分圆序列的线性复杂度

DOI:10.11999/JEIT210095
发表时间:2021
3

Himawari-8/AHI红外光谱资料降水信号识别与反演初步应用研究

Himawari-8/AHI红外光谱资料降水信号识别与反演初步应用研究

DOI:
发表时间:2020
4

基于协同表示的图嵌入鉴别分析在人脸识别中的应用

基于协同表示的图嵌入鉴别分析在人脸识别中的应用

DOI:10.3724/sp.j.1089.2022.19009
发表时间:2022
5

当归红芪超滤物对阿霉素致心力衰竭大鼠炎症因子及PI3K、Akt蛋白的影响

当归红芪超滤物对阿霉素致心力衰竭大鼠炎症因子及PI3K、Akt蛋白的影响

DOI:10.3969/j.issn.1008-0805.2022.07.18
发表时间:2022

张莲珠的其他基金

批准号:10271105
批准年份:2002
资助金额:9.00
项目类别:面上项目

相似国自然基金

1

图的Pfaffian定向相关问题及应用研究

批准号:11671186
批准年份:2016
负责人:卢福良
学科分类:A0409
资助金额:48.00
项目类别:面上项目
2

几类Pfaffian图的结构性质研究

批准号:11301251
批准年份:2013
负责人:卢福良
学科分类:A0409
资助金额:22.00
项目类别:青年科学基金项目
3

几类图的Pfaffian定向及其相关问题研究

批准号:11226288
批准年份:2012
负责人:卢福良
学科分类:A0409
资助金额:3.00
项目类别:数学天元基金项目
4

格原子图C*-代数的性质及相关问题的研究

批准号:11801123
批准年份:2018
负责人:靖杨萍
学科分类:A0207
资助金额:25.00
项目类别:青年科学基金项目