3

サイズn/4の最大カーディナリティ一致を持つグラフを見つけるにはどうすればよいですか? またはn / 3と言いますか？ここで、n はグラフの頂点の数を表します。接続されたグラフは可能ですか?

4

2 に答える 2

0

タットベルジュの公式に基づいてこのようなグラフを作成できます。これを使用して、次のように、最大​​マッチングサイズn/4のグラフを作成できます。Vをグラフ内の頂点のセットとし、Uを頂点の任意のサブセットとします。k- |U|となるような数kを見つけます > = | V |/2。VUから奇数サイズのコンポーネントC1、C2、...、Ck（互いに素である）を構築し、各CiからのエッジのセットをUの頂点に追加します。

C1、...、Ckは、Uを削除したときに取得する奇数サイズのコンポーネントであることに注意してください。{U、C1、...、Ck}の他の頂点は、上記の制約に従って任意の方法で接続できます。

于 2012-10-07T13:30:38.110 に答える
0

最も単純な例は、完全2部グラフK_m、nです。マッチングサイズを一定の比率（|V|/k）に調整するには、それ以降は、でnある必要があり、マッチングサイズはです。(2*k-1)*m|V| = n + m = 2*k*m2*m

于 2012-10-06T18:10:53.153 に答える