共查询到18条相似文献,搜索用时 84 毫秒
1.
简单图的最大匹配的矩阵求法 总被引:1,自引:0,他引:1
李世群 《数学的实践与认识》2007,37(7):120-124
简单图的最大匹配与完美匹配一般算起来比较困难,而且至今未见用矩阵解决这类问题的报道.利用图的邻接矩阵及关联矩阵求简单图的最大匹配和二分图的完美匹配,对于二分图的完美匹配及一般简单图的最大匹配各给出了两种方法,这些方法简洁又便于用矩阵软件进行计算. 相似文献
2.
3.
4.
5.
6.
7.
8.
研究3-正则图的一个有意义的问题是它是否存在k个没有共边的完美匹配.关于这个问题有一个著名的Fan-Raspaud猜想:每一个无割边的3-正则图都有3个没有共边的完美匹配.但这个猜想至今仍未解决.设dim(P(G))表示图G的完美匹配多面体的维数.本文证明了对于无割边的3-正则图G,如果dim(P(G))≤14,那么k≤4:如果dim(P(G))≤20,那么k≤5. 相似文献
9.
10.
为了研究具有完美匹配图的Tuttc集和极端集,文献[1,2]提出了一种新的图运算,并且得到了许多有趣的性质。本文中,我们刻画了level(G)=0的具有唯一完美匹配的饱和图G,并且确定了具有唯一完美匹配图的D-图的边数的紧上界。 相似文献
11.
12.
We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs. 相似文献
13.
Mihai Ciucu 《Journal of Algebraic Combinatorics》1996,5(2):87-103
We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of order n introduced by Elkies, Kuperberg, Larsen and Propp has exactly 2
n(n+1)/2 perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles. 相似文献
14.
The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs. 相似文献
15.
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks. 相似文献
16.
Perfect matchings of k-Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k. In general, this enumeration problem is #P-complete. We give a Composition Theorem of 2r-Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k-Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) [8], which states that the Pfaffian number of a graph is a power of four. 相似文献
17.
Kenneth A. Berman 《Journal of Combinatorial Theory, Series B》1981,30(3):343-350
It is shown that in a 0-sum Boolean weighted graph G the sum of the weights taken over all the spanning trees equals the sum of the weights taken over all the perfect matchings in the graph G − v, where v is any vertex of G. Several related theorems are proved which include parity results on perfect matchings and spanning trees in Eulerian graphs. The ideas on perfect matchings in 0-sum Boolean weighted graphs are generalized to matchings in any Boolean weighted graph. 相似文献
18.
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the burnt pancake graphs and show that every optimal (conditional) matching preclusion set is trivial. 相似文献