---
title: 圖論在中山
description: graph theory at nsysu
tags: article
image: https://i.imgur.com/fI8S3dB.png
---

# 圖論在中山

國立中山大學應用數學系是臺灣離散數學的重要學術殿堂，先後有官大智、朱緒鼎、王彩蓮、董立大等多位老師的付出，學術成果豐碩，而我也有幸於 2018 年加入中山應數的團隊。從我的學生時期到現在，中山應數一直是離散數學各路學者的聚集地，時常有知名的國際學者來訪，也培育了眾多優秀的碩博士生、以及博士後研究員。今年適逢中山大學 40 週年校慶，遂以一種虔敬的心情，一路挖掘圖論在中山發跡的過程。

離散數學在中山已有二十餘年的發展，四位老師身懷各種長才，履履在研究上創造出耀眼的表現。官大智教授專長為理論電腦科學、演算法、以及資訊安全，曾任中山大學資訊科學研究中心主任，也活躍於中華民國資訊安全學會等學術社群；朱緒鼎教授為圖著色理論領域國際知名的學者，曾獲中山大學西灣講座教授及國科會（現科技部）傑出研究獎；王彩蓮教授初期研究主軸為代數，後期興趣轉向代數組合以及圖著色理論，其發表的文章被國際期刊 Journal of Graph Theory 列為 2016~2017 年最常被引用的文章前五名；董立大教授專長為電腦連接網路、圖的哈密頓路徑、以及圖的辨識碼等領域，藉由扎實的數學背景，積極投入臺灣的人工智慧發展，與台化、中鋼、中鴻等公司都有產學合作，現為中山大學人工智慧研究暨產業推廣中心主任。

中山應數一直是南區學術發展的重心，圖論與離散數學也不例外。一路走來，中山應數主辦了將近二十場的學術研討會，其中【南區組合數學研討會】以及【西子灣組合數學系列研討會】已經辦了五屆，為系上的優良傳統；【組合數學新苗研討會】為每年離散數學圈孕育新秀的重要活動，其中三屆為中山應數主辦。因為國際研討會的關係，時常有國際學著來訪，國際知名的圖論學家 Jaroslav Nešetřil、Pavol Hell、Zdeněk Dvořák 等都曾來訪中山數次。由於中山大學依山傍水，在朱緒鼎教授的帶領下，時常研討會都會搭配爬山的行程；更有一次學者們帶著小白板上山，在山上聽 Nešetřil 教授演講並討論數學，成為美談。

受到朱緒鼎教授的影響，系上有很多人都接觸過圖著色理論。圖著色理論是圖形學中一個重要的問題，它可以應用在各種行程安排上（比如說電腦的程式執行順序）。著名的四色問題考慮地圖的著色，並問說是否任何一張地圖都可以只用四種顏色來著色，使得任兩個相鄰國家的著色不相同。如果把每個國家當做一個點，相鄰的國家連一條邊，那麼四色問題就是在問：是否可以將這樣的圖上的點著色，使得有連邊的兩個點著色不相同？只用四個顏色是否足夠？這樣的問題可以推廣在任何的圖上，來問說幫一個圖適當地著色最少須要幾個顏色，而這個顏色數我們稱之為圖的著色數。（以下圖為例，右圖的著色數為 $3$。）圖著色的問題也可以想成是把點分類的問題，每個顏色視為一類，而每類中的點彼此之間不能有邊相接。


系上的教授曾以各種方法來討論圖著色問題，包含數學歸納法、代數方法（組合零點定理）、機率方法、拓樸方法等，發表過數十篇的期刊論文，對這個問題做出長足的貢獻。身為中山應數的後學，我也期許自己能在圖著色的理論上付出努力，希望以線性代數的工具來探索這個問題。在代數圖論的領域中，我們研究圖和矩陣的關聯性，其中一種常見的矩陣稱為圖的拉普拉斯矩陣。如果一個圖有 $n$ 個點，其相對應的拉普拉斯矩陣是一個 $n\times n$ 的對稱矩陣，而這樣的矩陣會有 $n$ 個實數的特徵值 $\lambda_1\leq \cdots\leq\lambda_n$、以及 $n$ 個相對應的特徵向量 ${\bf v}_1,\ldots,{\bf v}_n$。一個已知的結果說明如果一個圖可以用兩個顏色著色，則這個圖的點可以跟據 ${\bf v}_n$ 上 $n$ 個數字的正負號來分類，而且這樣的分類剛好是這個圖的二著色。基於這個想法，我希望能找出圖著色和特徵向量的連結。比如說考慮下方的圖，將它的 ${\bf v}_n$ 當 $x$ 座標、它的 ${\bf v}_{n-1}$ 當 $y$ 座標，則可以畫出另一張圖；而我們會發現在新的圖上同樣顏色的點都聚在一起。這個方向的研究是我目前正在執行的計畫，受到科技部年輕學者養成研究計畫（愛因斯坦培植計畫）補助，希望能傳承中山應數的驕傲，繼續在圖論上做出貢獻。


圖論在中山發展了二十餘年，在國內與國際的學術社群都有一定名聲。近期隨著科技的發展，圖論與統計、電腦科學結合，發展出資料科學上的各種應用。系上開始規畫人工智慧相關課程，同時與企業建立產學合作，而其中許多技術都須要用到圖論的演算法及理論。圖論在中山，也從理論走向理論及應用兼備，相信在未來會有更多彩多姿的表現。

國立中山大學
應用數學系
林晉宏
September, 2020