李曉明

（北京大學(xué) 計(jì)算機(jī)系， 北京 100871）

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

問題：給定一有向圖G，最少添加幾條邊，使之成為一個(gè)強(qiáng)連通圖。

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

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

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

1）問題的導(dǎo)入。

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

圖1 班級(jí)社會(huì)網(wǎng)絡(luò)圖

在下一次課上展示這個(gè)圖像，讓同學(xué)們意識(shí)到這是他們上次提供數(shù)據(jù)的結(jié)果，有益于建立起課堂學(xué)習(xí)的內(nèi)容和他們相關(guān)的體驗(yàn)。舉例來說，可以提問如下。

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

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

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

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

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

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

經(jīng)過問題導(dǎo)入階段的小例子，學(xué)生們應(yīng)該已經(jīng)意識(shí)到入度為0的節(jié)點(diǎn)和出度為0的節(jié)點(diǎn)是求解這個(gè)問題需要關(guān)注的重點(diǎn)。以此為基礎(chǔ)，幾個(gè)可以逐步展開的分析點(diǎn)如下。

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

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

圖2 關(guān)于一般情況下max{p,q}充分性的一個(gè)反例

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

必要的話，可以讓學(xué)生討論將DAG增廣為強(qiáng)連通與將G增廣為強(qiáng)連通的等價(jià)性的證明。

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

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

3）問題的求解。

努力將看起來錯(cuò)綜復(fù)雜的情形轉(zhuǎn)變?yōu)楹?jiǎn)單清晰的情形，不斷將問題簡(jiǎn)化，是值得我們?cè)诮虒W(xué)中貫徹的一個(gè)基本方法。這個(gè)將有向圖增廣為強(qiáng)連通的問題是體現(xiàn)這種方法的一個(gè)好例子。前面將一個(gè)一般的有向圖G轉(zhuǎn)變?yōu)镈AG可以看成是其中一個(gè)步驟，接下來的步驟如下。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 D→Bn的例子

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

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

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

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

圖6 G不是弱連通的，它由4個(gè)弱連通分量構(gòu)成

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

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

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

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

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