CAJ | 학술논문

一个图G是匹配覆盖的(或1-可扩的)如果它是连通的且G的每条边都被包含在一个完美匹配里。我们称一个图G为双因子临界的，如果对于G中的任意两个不同顶点x, y，G-x-y都有一个完美匹配。一个双因子临界图被称为砖块，如果它是3-连通的。本文对于双因子临界图与匹配覆盖二部图确定了它们的阈函数。对于非二部的匹配覆盖图，我们发现了一个概率序列，其表现就像一个阈。此外，我们证明几乎所有的3-连通图均是砖块。
일개도G시필배복개적(혹1-가확적)여과타시련통적차G적매조변도피포함재일개완미필배리。아문칭일개도G위쌍인자림계적，여과대우G중적임의량개불동정점x, y，G-x-y도유일개완미필배。일개쌍인자림계도피칭위전괴，여과타시3-련통적。본문대우쌍인자림계도여필배복개이부도학정료타문적역함수。대우비이부적필배복개도，아문발현료일개개솔서렬，기표현취상일개역。차외，아문증명궤호소유적3-련통도균시전괴。
A graph G is matching-covered (or 1-extendable) if it is connected and every edge of G is contained in a perfect matching. We call a graph G bicritical if G-x-y has a perfect matching for every pair of distinct vertices x and y in G. A bicritical graph is called a brick if it is 3-connected. In this paper, we determine thresholds for bicritical graphs and matching-covered bipartite graphs. For non-bipartite matching-covered graphs, we find a probability sequence which acts the same way like a threshold. Furthermore, we show that asymptotically almost surely all 3-connected graphs are bricks.