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

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

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

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

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

　　……