Progress Report

Subject: 研究進度報告 (March 2011)

Dear 趙老：

附檔是我最近這一兩個月來得研究心得，主題是 "L(2,1)-labeling of graphs with maximum degree 3"。

很有意思的課題與進展，我有幾個問題：
(a) Peterson graph的λ(G)是定數嗎？
(b)是否有Δ(G)=3, 而λ(G)=9的實例？(我眼花，或許寄來的例子就是。)
(c)該由哪個點開始做BFS呢？因為在很多情況下，Label的起點也很關鍵。另外，BFS的root，一定從0開始編起嗎？

(a), (b): 是的，Peterson graph的λ(G)=9，因為它具有10個點且其diameter為2，也就是說每點之間的距離皆不超過2，則根據L(2,1)-labeling的定義，其上的每個node的編號一定要相異，所以λ(G)至少是9。而因為我寫給您的那個例子就是一個最大標籤不超過9的標籤方法，所以λ(G)=9。（老師您沒眼花，是我附的例圖太小了，不好意思。）

(c): 我目前的想法並沒有規範BFS的起點，雖然的確有少數的點不能作為root，但這種點它的鄰居之中一定有至少一個可以當root；這部份與我設計的類BFS圖的結構有關，細節等我寫好定義以後我會再和您說明。root 的確是一律從 0 開始標。

我之前在想這個問題時，曾經有一段時間幾乎沒有甚麼進展。直到最近這一個月內才比較又覺得有一些新的想法可以嘗試。當然，這過程中也遇到了相當多的問題，所以我目前是處於不斷地改假設、論證、改假設、論證、......的狀態。

這與叢林探險沒啥兩樣，要注意自己的備糧，以及可以殺出生路的方向。不過也要記得保持彈性，山不轉路轉，路不轉人轉，絕不原地踏步，要逐步切到最能展現進展斜率的研究課題上。

那段沒有甚麼靈感的日子我時常在想，對於那些會出現在課本裡偏離散、組數的習題，我以往的經驗是，當它是一個我有感覺我解得出來的題目，即便是難題，只要我對它不離不棄，最終必然可以將它解決，然而，研究的課題似乎就不是如此。將研究的課題與教課書上的習題做比擬也許不太恰當，不過我的想法是，一個大的課題應是由許許多多小的習題所建構出來的，所以在這兩種規模不同的問題之間，一定還是存在有某種程度的相似性。也許問題是出在我還沒有學會該如何組織這些零碎的思維，來拼湊出一個屬於我自己的視野地圖。

對我而言，有時不確定是否有解是一種莫大的樂趣。「山窮水盡疑無路，柳暗花明又一村」的驚喜，是老天爺給研究工作者最心滿意足的回饋。當然，很多時候是「山快窮，水已盡，抬頭一看，哇，斷崖，『此路不通』！」

習題和研究問題的微妙差別：
(a)習題通常有解，研究問題卻常常無解；
(b)習題可在一天或一週內完成，研究問題卻可能耗費數月或一年以上的時間完成；
(c)習題有明確的截止繳交期限，研究問題常常「此恨綿綿無絕期」。

老師的觀察使我想到了有時候信心程度的多寡也或多或少會有影響。當我知道問題有解時，這種有依靠感覺也會增加我在解題時的信心。所以對此我也曾經幻想過，那是不是只要努力催眠自己說這個研究的問題有解，且猜想是對的，這樣就會證出來了！？遺憾的是目前幾次實驗結果下來證實這種方法是行不通的，不然就是我還太清醒。不過老師請您放心，我會時時告誡自己不要自欺欺人，催眠到最後還以為自己證出來了，其實不然。

縱使最近在嘗試證明的過程中，失敗的頻率依然很高，但總覺得在每經歷到一次失敗的過程之後，對於這問題本身的難解之處也會有更深一層的體會，比起之前甚麼想法都沒有的時候要來得充實多了，所以我目前是希望能夠維持著這樣的節奏來想問題。對於最終的結果或許會失敗雖然仍是感到害怕，不過既然有了進展，那我想應該還是先衝衝看吧！

嗯，「成功固然是很好的老師，但失敗是更好的老師」，知道怎麼失敗，就可離失敗更遠些。

希望在接下來的這一個月內，我能夠乘著對於問題的熱度持續來多做嘗試。如果有所突破，我會在四月底前將我目前的想法整理成draft。之前我總覺得將想法寫下來是一件很費時的事，不僅會壓縮到思考的時間，且每改變一次想法就要修一次手稿，所以我總是不太想把這些想法寫下來。但我發現某些細節如果不將定義寫出來，只留在自己的腦海裡，似乎就難以將想法很系統地向別人說明，如此一來也增加了和老師討論的難度。所以近期必要時，也許不一定等到有更進一步的突破，我也會開始來動工整理我的draft。

學思並用，撰寫亦是學與思的利器，常常在過程中就豁然開朗了。

最近實驗室的同學們偶爾也會與我分享一些有趣的問題。譬如說像大秉昨天和我提到的那一篇，題目是 "Fast distance multiplication of unit-Monge matrices" (SODA 2010)，我覺得就還滿對我胃口的。我想雖然我現階段應該要分配大部分的時間在此次進度報告的課題上，但我也得花點時間接觸一些其他問題，留一點契機，如此一來假使未來在研究目前的課題上看到重大瓶頸無法突破時，也較不至於一時之間突然手足無措。

有個備胎問題是不錯的策略，但得小心不陷入「追二兔，不得一兔」的窘境。另外，有時就像打九號球賽，在打四號球時，不僅要進袋，還得考慮將母球做到下一球最佳的擊球位置；而如果四號球無法直接進袋，亦可考慮間接撞擊其他球進袋。

老師先前有提醒過我可多看一些新的會議論文，我覺得這點我一直做得不是很好，我會再努力改進我在這方面的不足。若有其他需要注意的事項，還請老師多提點囉。

多看最新動態，可掌握主軸的脈動；多讀經典論文，可累積解題的功力。誠如朱熹〈觀書有感〉所言：「半畝方塘一鑑開，天光雲影共徘徊，問渠哪得清如許，為有源頭活水來。」Be the best of you!

謝謝老師給了那麼多生動的例子！有兔子、有球賽、有山有水有村落，果真是生活中處處有靈感阿……。希望我有朝一日能在打球打到一半時突然想到一個絕妙的演算法:D（做白日夢中）

謝謝老師！

蔚茵