[離散] Grid graph

[recorriendo (孟新)]

遇到一個問題卡住了

Suppose we have a m x n grid graph

V = {v_ij} where i=1,...,m, j=1,...,n and

E = { (v_ij,v_i'j) wherever i'-i=1 }∪{ (v_ij,v_ij') wherever j'-j=1 }

Suppose m,n are even, m < n

How many vertices should we remove (if we remove a vertice, we also remove

all edges incident to it as well) so that the remaining graph has no cycle?

Find the least number.

請問這題該如何下手呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.12.24.136
※ 編輯: recorriendo     來自: 128.12.24.136        (10/28 08:36)
※ 編輯: recorriendo     來自: 128.12.24.136        (10/28 08:36)
推 walkwall    :直覺應該是(mn-m-n)/2+1
推 arthurduh1  :no cycle  =>   剩下edge數 < 剩下vertex數-1
→ arthurduh1  :如此可得下界      上界的話試著構造即可
推 agga        :walkwall, 3*5只要3個點就好
→ agga        :比較像是[(mn-m-n)/3]
→ agga        :剛的是取celing