Re: [圖論]一個和cubic bipartite 有關的問題

[over ( )]

可能不會。

Example: X = {x_i : i=1,2,...,6}
         Y = {y_i : i=1,2,...,6}

        N(x_1) = {y_1,y_2,y_3}
        N(x_2) = {y_1,y_2,y_4}
        N(x_3) = {y_1,y_5,y_6}
        N(x_4) = {y_2,y_5,y_6}
        N(x_5) = {y_3,y_4,y_5}
        N(x_6) = {y_3,y_4,y_6}

找不到如此一組{x_1,x_2,...,x_k}。

※ 引述《nendi (midi)》之銘言：
: 想請教  a cubic (3-regular) bipartite graph G, V(G) = (X,Y)
: 其中 X和Y的個數皆為3k, k屬於正整數
: 是否一定會存在一組  x_1,x_2 .... x_k \in X
:                   k
: 使得  Y 被包含在  U  N(x_i)
:                  i=1
: 並且  N(x_1),N(x_2),...,N(x_k) 為一 disjoint set 呢？
: 感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.51.121
推 nendi       :感謝，非常漂亮