3

友人が私に真実のように思われる推測を提示しましたが、私たちのどちらも証明を思い付くことができません. 問題は次のとおりです。

|U|<|V| のように、互いに素な空でない頂点セット U と V をもつ接続された 2 部グラフが与えられ、すべての頂点が U または V のいずれかにあり、同じセット内の 2 つの頂点を接続するエッジはありません。次数(a)>次数(b)となるように頂点a∈Uとb∈Vを接続するエッジが少なくとも1つ存在する

U に V の次数よりも高い次数を持つ頂点が少なくとも 1 つあることを証明するのは簡単ですが、それらを接続するエッジを持つペアが存在することを証明するのは困難です。

4

2 に答える 2

2

a∈Uおよびb∈Vの任意の辺e=(a,b)について、w(e)=1/deg(b)-1/deg(a)とする。任意の頂点 x について、x に付随するすべてのエッジの 1/deg(x) の合計は 1 に等しくなります。これは、このようなエッジが deg(x) 個存在するためです。したがって、すべてのエッジ e での w(e) の合計は |V|-|U| に等しくなります。|V|-|U|>0 であるため、一部のエッジ e=(a,b) では w(e)>0 となり、deg(a)>deg(b) となります。

于 2012-02-20T20:06:10.020 に答える
0

矛盾によってそれを証明してください。つまり、deg(a) ≤ deg(b) ∀(a,b)∈Eと仮定します。ここで、Eはグラフのエッジセットです (最初の要素がUにあり、2 番目の要素がVにあるという規則を使用) ）。

F⊆E の場合、エッジセットFを介して到達可能なVのサブセットをV(F)で指定します。つまり、次のようになります。

V(F) = {b | (a,b)∈F }

次に、エッジセットFを次のように構築します。

F = empty set
For a ∈ U:
    add any edge (a,b)∈E to F
Keep adding arbitrary edges (a,b)∈E to F until |V(F)| = |U|

得られたセットV(F)はUのすべてのノードに接続されているため、仮定により、

∑<sub>a∈U deg(a) ≤ ∑<sub>b∈V(F) deg(b)

ただし、|U|=|V(F)|であるため、および|U|<|V| 少なくとも 1 つの「到達していない」ノードv∈V\V(F)が存在する必要があることがわかっており、グラフが接続されているため、deg(v)>0を取得します。

∑<sub>a∈U deg(a) < ∑<sub>b∈V deg(b)

これは不可能です。これは、二部グラフの場合は等しいはずです。

于 2012-02-19T17:31:50.967 に答える