一個圖G的邊編號是一個正整數的編號r，使得邊不同的ei和ej而r(ei) = r(ej)，他們的每一個路徑(path)，之中皆存在邊ew使得r(ew) > r(ei) = r(ej)。一般來說，邊編號的最佳解，就是求最小的邊編號。
直到2007年，對於不是trival類別的圖以及樹和two-connected outerplanar圖形之外，沒有找到線性時間的演算法。
最近，我想到把邊編號應用到格子圖上，即從中央做cut，如下圖
可以這樣切，或是如下圖這樣切：
如下圖，是一個邊編號完成的成果：
此時，這圖的χe(G)=9。顯然的，若都是直的切，從一半切下去是最佳的，這很容易證明，但為啥麼不斜著切？
這個問題，直覺上，認為不會是斜著切，但要怎麼證，笨笨的我，一時也想不出來。
2010年4月17日記：
如果無法從中間切下去，可能就需要有點斜著切了@"@。如下圖：
沒有留言:
張貼留言