還有一個(gè)例子出現(xiàn)在某種程序設(shè)計(jì)環(huán)境中，連通性可用來斷言兩個(gè)變量名是否等價(jià)。問題是在經(jīng)過這樣的斷言序列之后，能夠確定兩個(gè)給定的名字是否等價(jià)。這個(gè)應(yīng)用激發(fā)了我們打算考慮的幾個(gè)算法的研制。它直接將我們的問題與一種簡(jiǎn)單抽象關(guān)聯(lián)起來，為使算法具有廣泛應(yīng)用而提供了一種方法。我們即將看到這一點(diǎn)。

　　像上一段描述的變量名等價(jià)問題這樣的應(yīng)用程序要求我們把每個(gè)不同的變量名與一個(gè)整數(shù)關(guān)聯(lián)起來。這種關(guān)聯(lián)關(guān)系也隱含在前面描述的網(wǎng)絡(luò)連接和電路連接的應(yīng)用中。在第10章至第16章，我們將會(huì)以一種更高效的方法考慮提供這種連接關(guān)系的大量算法。因此，不失一般性，本章假設(shè)有N個(gè)對(duì)象，每個(gè)都與0一N一1之間的一個(gè)整數(shù)名對(duì)應(yīng)。

　　我們正在尋求完成特定和良定義任務(wù)的程序，可能還想要解決其他許多相關(guān)的問題。在研制算法時(shí)我們面對(duì)的首要任務(wù)之一是確信我們已經(jīng)以合理的方式指定了問題。我們要求算法的越多，它完成任務(wù)所需要的時(shí)間和空間越多。不可能量化這個(gè)關(guān)系，并且我們?cè)诎l(fā)現(xiàn)一個(gè)問題難以求解或是求解代價(jià)昂貴，或是在好的情況下，發(fā)現(xiàn)算法可以比原始說明提供更多有用的信息時(shí)，我們常常修改這個(gè)問題的說明。

　　例如，我們的連通問題的說明只要求我們的程序知道任意給定對(duì)p—q是否是連通的，并不能夠表明連接那個(gè)對(duì)的任何方式。添加這樣一個(gè)說明的要求會(huì)使問題更加困難，會(huì)涉及其他的算法，我們將在第5章簡(jiǎn)略討論，并在第7章詳細(xì)討論。

　　前面這段提到的說明要比原始說明要求更多的信息，我們也可以要求更少的信息。例如，我們可能只想回答這樣的問題：“M個(gè)連接足以把Ⅳ個(gè)對(duì)象都連接起來嗎？”這個(gè)問題表明，要研制一個(gè)高效的算法，常常需要我們對(duì)正在處理的抽象對(duì)象進(jìn)行高級(jí)推理。在這種情況下，由圖論基本結(jié)果可以得出所有Ⅳ個(gè)對(duì)象是連通的，當(dāng)且僅當(dāng)連通算法輸出的對(duì)的個(gè)數(shù)恰好為N一1（見5．4節(jié)）。換句話說，連通算法永遠(yuǎn)不會(huì)輸出多于N一1個(gè)對(duì)，這是因?yàn)橐坏┧�輸出N一1個(gè)對(duì)，則它從那個(gè)時(shí)刻遇見的任何對(duì)將會(huì)是連通的。因此，我們可以修改求解連通問題的程序，增加一個(gè)計(jì)數(shù)器就可以得到一個(gè)回答yes-no問題的程序，而不輸出那些前面不連通的每個(gè)對(duì)，當(dāng)計(jì)數(shù)器的值為N-1時(shí)，程序回答“yes”，否則回答“no”。這個(gè)問題只是我們希望回答關(guān)于連通性的許多問題中的一個(gè)例子。輸入對(duì)的集合稱為圖（graph），輸出對(duì)的集合稱為圖的生成樹，它連接了所有對(duì)象。我們?cè)诘谄卟糠挚疾靾D、生成樹以及所有相關(guān)算法的性質(zhì)。

　　……