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

看板Math作者 (midi)時間12年前 (2013/05/08 20:47), 編輯推噓4(4推 0噓 10→)
留言14則, 5人參與, 6年前最新討論串1/2 (看更多)
想請教 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: 61.175.228.16
→
05/08 22:37, , 1F
|X| = |Y| = 3k 不太對唷
05/08 22:37, 1F
→
05/09 12:27, , 2F
那個3k 是給定假設的條件 @@
05/09 12:27, 2F
→
05/09 12:27, , 3F
假設 X 和 Y 皆為3倍的個數
05/09 12:27, 3F
推
05/09 19:23, , 4F
k=1時就不會了不是嗎？K_3,3 是complete bipartite
05/09 19:23, 4F
推
05/09 19:25, , 5F
而在同一個independent set裡的點(就是你說的X或Y)
05/09 19:25, 5F
→
05/09 19:26, , 6F
他們的neighbor都是一樣的，交集非空
05/09 19:26, 6F
推
05/09 19:28, , 7F
甚至用3regular的條件可以簡單推出點跟邊個數之間的
05/09 19:28, 7F
→
05/09 19:29, , 8F
關係，也可以知道這樣的disjoint set根本不存在
05/09 19:29, 8F
→
05/09 20:35, , 9F
給樓上，k3,3 的任意一個點都會把對面的三個點包含在
05/09 20:35, 9F
→
05/09 20:35, , 10F
那個點的neighborhood 裡面
05/09 20:35, 10F
推
05/09 22:30, , 11F
sorry 我看錯了。以為你的x_i是指X裡的全部元素
05/09 22:30, 11F
→
11/10 11:46, , 12F
假設 X 和 Y 皆為 https://daxiv.com
11/10 11:46, 12F
→
01/02 15:23, 7年前 , 13F
k=1時就不會了不是嗎 https://noxiv.com
01/02 15:23, 13F
→
07/07 10:58, 6年前 , 14F
//daxiv.com https://moxox.com
07/07 10:58, 14F
‣ 更多 nendi 的文章
文章代碼(AID): #1HYabqCg (Math)
‣ 更多 nendi 的文章
文章代碼(AID): #1HYabqCg (Math)