有向圖的增強
——一個適合以問題求解為導向教學的例子

李曉明

（北京大學 計算機系， 北京 100871）

過去幾年，在北大有一門通選課，叫“社會科學中的計算思維方法”。每次上課的時候，我總會給出一個小小的有向圖的例子，讓同學們觀察，看最少添加幾條邊，可以讓那個圖變成強連通的，這個看起來像是一個趣味數學游戲的活動常常會引起學生們的積極參與。由于例子很小，大家通常在兩三分鐘里就能給出正確的結果。然后，我就留下這個游戲推廣到一般的問題讓有興趣的同學思考。

問題：給定一有向圖G，最少添加幾條邊，使之成為一個強連通圖。

看起來這個問題對那些喜歡數學和邏輯思維的學生的確是有吸引力的：幾乎每一次，都會有同學嘗試給出一個完整的解。于是，我也做了一下文獻搜索，發(fā)現這個問題的最早解是由Eswaran和Tarjan在1976年給出的[1]。1995年，Frank將問題推廣到k-強連通，并給出了解[2]。有意思的是，2005年還有人發(fā)表論文，指出文獻[1]中的解有點錯誤，并給予了糾正[3]。

讀那些文獻，第一感覺是，那是一個已經被深入研究并解決了的問題，從學術上講不太會有什么進一步的新意，但幾年的課堂教學，卻讓我有了另外一方面的認識。雖然那些文獻中提出了多種解法，但往往都比較復雜，不適合教學；既然這問題那么容易引起學生的興趣，是不是可以找到一個比較適合教學的方法（算法）呢？

于是，基于對那幾篇文獻的理解和近幾年來斷斷續(xù)續(xù)和幾個選課學生討論的結果，特別是2016年的學生張浩千和2018年的學生姜百翼提出的想法，一個適合作為以問題求解為導向的教學方案浮現出來。在這里，我們不妨先介紹這個方案本身，然后再討論它適合什么樣的學生和課程。

1）問題的導入。

實踐表明，用某種“真實的數據”來引出這個問題是比較有效的。我的做法是在前面的一次課上給每個學生發(fā)一張紙，讓每人除了寫上自己的名字外，還寫出班里其他3個同學的名字，于是，我就有了一個有向圖的數據。經過課后的整理，利用一個畫圖軟件，就得到如圖1所示的一個有向圖的圖像。

圖1 班級社會網絡圖

在下一次課上展示這個圖像，讓同學們意識到這是他們上次提供數據的結果，有益于建立起課堂學習的內容和他們相關的體驗。舉例來說，可以提問如下。

基于這樣一個圖所表達的關系，假設有向邊意味著“可以直接傳話”，如果要讓每個同學都能（直接或間接地）傳話給另一個同學（即兩個節(jié)點之間存在有向路徑），最少需要添加幾條邊？

如果班里的人數較多，如圖中節(jié)點數超過20，就會讓大家感到無從下手，這時候，可以單獨給出一個小例子，讓他們嘗試一下如何添加最少的邊使其變成強連通，這樣就可以體會到這個問題的挑戰(zhàn)性所在，從而產生尋求一般解的愿望。

此時，有向圖、有向路徑、強連通、強連通分量、弱連通（即不考慮邊的方向性，是連通的）等概念，作為下面展開討論的基本“語匯”，就都可以自然帶入了。所謂“以問題求解為導向的教學”（我覺得類似于教育學中近年來不少人推崇的“Project-based learning”（PBL）），就是讓抽象的概念隨著對問題理解的展開而出現在學生面前，而不是一上來首先是定義、定理、例子，然后再講應用。

2）問題的定義（抽象）與初步分析。

現在，我們可以抽象出本文一開始給出的問題了，即：

問題：給定一有向圖G，如何添加最少的邊，將它增廣為一個強連通圖。

經過問題導入階段的小例子，學生們應該已經意識到入度為0的節(jié)點和出度為0的節(jié)點是求解這個問題需要關注的重點。以此為基礎，幾個可以逐步展開的分析點如下。

（1）為避免在一開始陷入不必要的枝節(jié)，不妨先假設有向圖G是弱連通的。令p為入度為0節(jié)點個數，q為出度為0節(jié)點個數。此時，大多數同學都能夠很快意識到至少需要max{p,q}條邊才能將G增廣為強連通圖，即max{p,q}是必要的。達成這樣的認識對建立信心有益處。

（2）max{p,q}也是充分的嗎？這是第一個具有挑戰(zhàn)性的問題。學生們肯定是分兩派了，持肯定意見的只能是大致的感覺，持否定意見的也許能給出反例，從而證明了他們的正確。例如圖2（實線邊）就是一個反例，其中每一個節(jié)點都在一個環(huán)中，于是p=q=0，但還是需要1條邊（虛線）才能讓它強連通。

圖2 關于一般情況下max{p,q}充分性的一個反例

在什么樣的情況下max{p,q}不足以解決問題？從上面這個小例子容易想到的一個一般情形，即由非平凡連通分量（即不是單個節(jié)點）構成的有向圖就可能產生這樣的問題，進而也容易猜想將一個圖（G）的非平凡連通分量“收縮”成一個節(jié)點，所導致的結果圖應該和G在增廣強連通上具有某種等價性。此時就可以引入有向無環(huán)圖（DAG）的概念，以及由G通過“收縮”其強連通分量為一個節(jié)點，從而得到一個DAG的過程（算法）。

必要的話，可以讓學生討論將DAG增廣為強連通與將G增廣為強連通的等價性的證明。

（3）到這里引出一個自然的問題：若G是有向無環(huán)圖（DAG），為了將它增廣為強連通圖，用max{p,q}條邊是充分的嗎？

這也就是經過前面的導入和提煉后形成的核心問題。接下來就是在課堂上可以一步步展開的討論。

3）問題的求解。

努力將看起來錯綜復雜的情形轉變?yōu)楹唵吻逦那樾?，不斷將問題簡化，是值得我們在教學中貫徹的一個基本方法。這個將有向圖增廣為強連通的問題是體現這種方法的一個好例子。前面將一個一般的有向圖G轉變?yōu)镈AG可以看成是其中一個步驟，接下來的步驟如下。

（1）我們現在考慮用max{p,q}條邊能否解決問題。容易想到的是那些添加的邊應該首先用來減少出度為0和入度為0節(jié)點的個數，即要跨在它們之間。如果p≠q，不妨假設p＞q（反過來的情形類似處理），就要想多出的那些入度為0的節(jié)點怎么辦？此時，若用p-q條邊在入度為0的節(jié)點之間做連接，只要不形成環(huán)，我們就得到一個入度為0與出度為0個數相等（記為n）的圖，記為D。學生們不難認識到，若能用n條邊解決D的問題，也就是用max{p,q}條邊解決了DAG的問題。于是我們實現了對問題的又一次簡化，即只要考慮p=q=n的情形即可。

那么，我們討論的就是一個相當“規(guī)范化”的有向無環(huán)圖D，如圖3所示。

圖3 G→DAG→D，一個“規(guī)范化”表示的有向圖

其中，我們將入度為0和出度為0的節(jié)點集合突出出來，用P和Q分別指代。圖中虛線框中含有所有其他節(jié)點，其中文字所表達的斷言也是適合讓學生在課上證明的（其中要用到D是有向無環(huán)弱連通的性質）。

（2）現在要追求的，就是看能否在D的基礎上添加n條邊，讓它成為強連通。通過前面的討論，大家基本能認識到，如果可能的話，那些邊一定都是從Q到P。那么，是不是隨便怎么連，只要是一個無冗余、無遺漏的1—1映射就可以了呢？不是！這里有一個例子。

圖4中，n=2。如果添加的兩條邊是2→1和4→3，雖然不再有入度為0或出度為0的節(jié)點，但結果圖顯然還不是強連通的。不過，若添加的邊是2→3和4→1，就可解決問題。

圖4 隨意添加邊不一定能解決問題的一個例子

通過這個例子，學生們對在P和Q之間添加邊所面對的狀況會有切實的體驗，直覺上能感到應該爭取和避免什么。此時，聰明的學生也許就能總結出具體的方法（課堂上不容易，但在課下進一步深入思考后有可能）。不過，從教學的角度，我想把“不斷化簡”的途徑再往前開拓一步。

（3）這里的關鍵是要啟發(fā)出一個很有用的認識：若添加一些邊能讓D中包含P和Q的某個子圖強連通，則那些邊也就將D增廣為強連通。以圖3為例換句話說，如果添加一些從Q到P的邊，加上虛線框中的某些從P到Q的路徑，能保證P和Q中的節(jié)點兩兩之間都有雙向路徑，則D中所有節(jié)點兩兩之間也就都存在雙向路徑，即成為強連通。

這樣的認識一旦提出，直覺上是容易被接受的。如果教學目標中希望強調理論性，這里可以插入一個關于證明的討論；而在強調較快的課堂節(jié)奏，讓學生很快把握問題求解過程全貌的教學設計下，也可以直接往下進行，而將證明留在后面。

這個認識的意義在于，可以基于圖3中的D，得到一個兩部分相等的二部圖Bn，其節(jié)點集合就是P={s1,s2,…,sn}和Q={t1,t2,…,tn}，存在邊si→tj，當且僅當在D中有一條從si到tj的路徑。圖5是一個例子。

（4）于是，問題就變成如何添加n條邊，讓Bn成為強連通。這里，依然按照“化簡”的思路，即考慮是否可以添加1條邊，將Bn變成Bn-1，一個保持關鍵的連通性質但出度為0和入度為0節(jié)點數分別減1的二部圖。若這個操作能做到，就可以有Bn→Bn-1→…→Bk，直到Bk是一個“完全二部圖”，即每一個s都有到每一個t的邊。那樣的圖上有豐富的邊，于是有許多種添k條邊使之成為強連通的方式，其中一種就是對所有i，添上ti→si。在如此得到的結果圖中，可以看到一個將所有節(jié)點串起來的環(huán)（也就是強連通）：

（5）如何添加1條邊，將Bn變成Bn-1？記O(si)?Q和I(tj)?P分別為節(jié)點si和tj的鄰居集合。如果Bn不是完全二部圖，就存在si，O(si)?Q，也就是存在ti?O(si)。取一個這樣的si和O(si)之外的tj，用tj→si作為添加邊。

這樣，圖中入度為0和出度為0的節(jié)點都少一個，正是我們希望的，但它已經不是二部圖。Bn-1如何形成？它除了沒有si和tj，還應該保持在添加了邊tj→si之后，P和Q中剩余節(jié)點之間的路徑關系，也就是：

圖5 D→Bn的例子

至此，遵循不斷去繁化簡的思路，就完成了一條路徑的展示：

這條路徑總會達到一個完全二部圖Bk（極端情況就是兩部各只有一個節(jié)點），于是就得到一個用最少的邊，將有向圖增廣為強連通圖的實施過程框架，可以看成是一個“高層的”算法。若DAG中有max{p,q}=p≥q=n，可見這個過程用到的邊數為(p-q)+(q-k)+k=p=max{p,q}，正是所希望的。當然，其中每一個環(huán)節(jié)的落實都會涉及某些具體算法，如在從D到Bn這個環(huán)節(jié)會用到廣度優(yōu)先搜索、從G到DAG的環(huán)節(jié)需要檢測強連通分量等。因此，將這個問題求解過程完整實現，也可以成為一個不錯的數據結構和程序設計綜合練習，其輸入為一個有向圖G的邊集合或鄰接矩陣，輸出為需要添加的邊集合。

至此，還有什么遺留問題嗎？答案是有！那就是在前面的（1）中，有G是弱連通的假設。如果G本身包含幾個沒有任何關聯的部分（弱連通分量），我們希望將它增廣為強連通圖，應該怎么做？

假設G有m個弱連通分量，對應入度為0和出度為0的節(jié)點個數分別為{p1,q1},{p2,q2},…，{pm,qm}。一個迅速的想法會是：每個分量按照上述算法處理，然后用m條邊將它們連成一個大“環(huán)”，于是總共要用條邊，但這是不正確的！圖6就是一個反例。

圖6 G不是弱連通的，它由4個弱連通分量構成

按照剛才那個想法，將它增廣為強連通圖，需要2+2+4=8條邊，但在圖7所示的方案中，5條邊（虛線）就夠了。

圖7 針對非弱連通圖的一種優(yōu)化實施方案

受這個例子的啟發(fā)，新的（正確的）結論就是：假設G有m個弱連通分量，分別有入度為0和出度為0節(jié)點的個數 {p1,q1},{p2,q2},…,{pm,qm}，其中，若某個弱連通分量為一個孤立點，則合理地認為它既是1個出度為0的節(jié)點，又是1個入度為0的節(jié)點（相當于是由兩個節(jié)點和一條邊構成的子圖）。這樣，記將G增廣為強連通圖需要的最少邊數就是max{p,q}，既必要也充分。具體實施層面，則是在G有孤立點的情況下，先將孤立點變成一個2節(jié)點1條邊的子圖，后面的過程則和前述完全相同，最后再將那些由孤立點衍生的兩節(jié)點認定為同一個節(jié)點即可。

至此，我們完成了一個以問題求解為導向的教學方案的描述，其中涉及的知識大致分布在離散數學和算法設計課程中。如果要實現的話，還涉及程序設計和數據結構課程，那么安排在什么課程里更合適呢？在目前多數學校計算機專業(yè)的教學計劃中，一二年級的課程基本比較傳統(tǒng)，為了兼顧現狀，可以將其考慮作為數據結構與算法課程的一個綜合作業(yè)。這樣的作業(yè)，不是老師簡單地給學生布置一個任務，而是老師引導學生歷經上述思考與推理的過程（大致需要2～4學時），然后由學生做程序實現。這樣，學生體驗的就不是急匆匆地完成作業(yè)，而是解決問題的思想方法，以及相關知識的綜合與深入應用過程。其中，可以梳理出幾條值得作為證明練習的斷言，從而讓學生不僅能在直覺上認同“G→DAG→D→Bn→Bn-1→…→Bk”這樣一個宏觀的框架，還能得到對其正確性的嚴謹理解。

另外一種考慮，則是開發(fā)出8～10個類似分量的問題，形成一門以問題求解為導向的新課，不僅可以針對計算機專業(yè)開設，還可以供其他專業(yè)的學生選修。