QQ客服 官方微博 反馈留言

题名	图的Pfaffian性及其相关问题; The Pfaffian Property of Graphs and Related Problems
作者	林峰根
答辩日期	2011 ; 2011
导师	张福基 ; 张莲珠
关键词	Pfaffian图 Pfaffian运算 完美匹配数 Pfaffian近似1-可扩二部图 极小Brick Pfaffian graph Pfaffian operation Perfect matching Pafffian defect 1-extendable bipartite graph Minimal brick
英文摘要	假设$G=(V(G)，E(G))$是一个图。一个圈$C$称为$G$的一个好圈，当且仅当$V(G)\backslashV(C)$的导出子图含有完美匹配。一个定向$D$称为$G$的一个Pfaffian定向，当且仅当$G$的每一个具有偶数个顶点的好圈都具有奇数条边的定向沿着圈的绕行方向一致。一个具有Pfaffian定向的图称为Pfaffian图。运用图的Pfaffian性，P.W.Kasteleyn，以及M.E.Fisher和H.N.V.Temperley，独立地解决了平面四格子图（$m\timesn$方格子图）的完美匹配计数问题。事实上，计算一般图的完美匹配数的复杂度是NP-complete。但是...; Suppose $G=(V(G), E(G))$ is a graph. A cycle $C$ is a nice cycle of $G$ iff the induced subgraph of $V(G)\backslash V(C)$ has a perfect matching. An orientation of $G$ is Pfaffian iff every nice cycle $C$ with even vertices has odd number of edges directed in the direction of traversal around $C$. A graph is Pfaffian if it has a Pfaffian orientation. Using the Pfaffianproperty of graphs, P.W. Ka...; 学位：理学博士; 院系专业：数学科学学院数学与应用数学系_应用数学; 学号：19120080150454
语种	zh_CN
出处	http://210.34.4.13:8080/lunwen/detail.asp?serial=32842
内容类型	学位论文
源URL	[http://dspace.xmu.edu.cn/handle/2288/47644]
专题	数学科学－学位论文
推荐引用方式 GB/T 7714	林峰根. 图的Pfaffian性及其相关问题, The Pfaffian Property of Graphs and Related Problems[D]. 2011, 2011.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。