共查询到20条相似文献,搜索用时 46 毫秒
1.
设G =(V ,U ,E)是一个连通的二部图 ,其中|V|=m ,|U|=n .令M (G)表示G的关联矩阵 ,Jk×s 表示元素全为 1的k ×s矩阵 ,R =M (G)M (G)′ , Jm n =Jm -Jm×n-Jn×m Jn,t(G)表示G中生成树的个数 .在本文中我们不用对G的边定向而获得了下面的主要结论 :t(G) =(m n) -2 det( Jm n R) . 相似文献
2.
《数学的实践与认识》2019,(24)
设G(V,E)是一个图,V_1,V_2是V的一个二部划分,当||V_1|-|V_2||≤1时,称V_1,V_2是V的一个平衡二部划分,用e(V_1,V_2)表示一条边的两个端点在不同划分里边的总数目.最小平衡二部划分是指寻找G(V,E)的一个平衡二部划分使得e(V_1,V_2)最小.研究了二部图和哈密尔顿二部图,得到它们的最小平衡二部划分的上界分别为[m/2]和(n+2)/2. 相似文献
3.
设 T(n,n)表示 n×n 二部竞赛图。本文证明了:如果 uv 是 T(n,n)的一条弧,蕴含d~-(u) d~ (v)≥n-2≥4,则 T(n,n)是 Hamilton 图,除非 T(n,n)属于两类已被刻划的特殊图类。 相似文献
4.
5.
本主要从理论上讨论赋权二部图的权的变化对最优解的影响,并在原最大权匹配的基础上给出求解权值变化后的最大权匹配的算法。 相似文献
6.
7.
8.
9.
在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD),并提出了一个猜想:任意有正数条边的图都可以升分解.本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解,其中Hm2是至多含m2条边的Km1m2的子图. 相似文献
10.
二部图是可迹的一个充分条件 总被引:4,自引:0,他引:4
谢政 《高校应用数学学报(A辑)》1996,(2):213-218
本文证明了以下结果:设G=(X,Y;E)是连通的二部图,如果4≤|Y|≤|X|≤|Y|+1,且NC_2≥|X|-1,则G是可迹的。从而表明[2]中的猜想对二部图是成立的。 相似文献
11.
Emre Kolotoğlu 《组合设计杂志》2013,21(11):524-530
A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K2, 3 and K3, 3. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved. 相似文献
12.
By End(G) and hEnd(G) we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End(G) = hEnd(G). A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly. 相似文献
13.
Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges. 相似文献
14.
15.
For a graph , let denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G , , where is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph , with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for , with high probability. We prove a stronger bound: there exists an absolute constant so that with high probability. 相似文献
16.
We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound .
Received: July 17, 1995 / Revised: April 5, 1996 相似文献
17.
半二面体群的小度数Cayley图 总被引:1,自引:0,他引:1
群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在Aut X中正规.研究了4m阶半二面体群G=〈a,b a2m=b2=1,ab=am-1〉的3度和4度Cayley图的正规性,其中m=2r且r>2,并得到了几类非正规的Cayley图. 相似文献
18.
Nigel Martin 《Graphs and Combinatorics》2007,23(5):559-583
There are simple arithmetic conditions necessary for the complete bipartite graph Km,n to have a complete factorization by subgraphs which are made up of disjoint copies of Kp,q. It is conjectured that these conditions are also sufficient. In any factor the copies of Kp,q have two orientations depending which side of the bipartition the p-set lies. The balance ratio is the relative proportion, x:y of these where gcd(x,y)=1. In this paper, we continue the study of the unbalanced case (y > x) where p = 1, to show that the conjecture is true whenever y is sufficiently large. We also prove the conjecture for K1,4-factorizations. 相似文献
19.
20.
二部图中的独立6-圈 总被引:1,自引:0,他引:1
本文主要证明了对二部图G=(V_1,V_2,E),|V_1|=|V_2|=3k,其中k为正整数.若G的最小度至少为2k-1,则G至少包含k-1个独立6-圈. 相似文献