圖論是訓(xùn)練離散數(shù)學(xué)證明技巧的樂園，其結(jié)果在計(jì)算科學(xué)、社會(huì)科學(xué)和自然科學(xué)等多個(gè)領(lǐng)域具有廣泛應(yīng)用．本書可作為本科生或低年級(jí)研究生1~2個(gè)學(xué)期的圖論課程的教材．本書不要求任何圖論的預(yù)備知識(shí)．盡管本書包含許多算法和應(yīng)用，但重點(diǎn)是講解圖的結(jié)構(gòu)和解決圖論問題的技巧．
目前在圖論方面已經(jīng)有許多教科書．由J. A.Bondy和U.S.R.Murty撰寫的優(yōu)秀教材《Graph Theory with Applications》(Macmillan/North-Holland［1976］)把重點(diǎn)放在證明和應(yīng)用兩個(gè)方面，本書的草稿參照了該書．圖論至今仍是一門年輕的學(xué)科，應(yīng)該如何介紹圖論的題材，大家仍然沒有一致的看法．主題的挑選和順序的安排，證明方法、目標(biāo)和基本題目的選擇等，一直是眾說紛紜．作者在多次修改本書的過程中認(rèn)識(shí)到，對(duì)于這些問題做決定是很困難的．本書是作者對(duì)這些爭(zhēng)議的一點(diǎn)貢獻(xiàn)．
第2版
第2版的修訂主要是為了更易于學(xué)生學(xué)習(xí)和更便于教師教學(xué)．本書的總體內(nèi)容沒有很大的變化，但是對(duì)內(nèi)容的表述方式做了修改，使其更容易理解，這一點(diǎn)在本書的前幾部分尤其明顯．有關(guān)第2版所做的某些修改，稍后將詳細(xì)討論，此處僅做一下概述．
非選學(xué)節(jié)中的選學(xué)材料現(xiàn)在用*號(hào)標(biāo)明．這些內(nèi)容不會(huì)在后續(xù)內(nèi)容中使用，因而可以跳過．忽略多數(shù)選修內(nèi)容以后，本書可以作為一學(xué)期的圖論教學(xué)內(nèi)容．如某一小節(jié)標(biāo)記為“選學(xué)”，則整個(gè)小節(jié)的內(nèi)容都是可選修的，而不再標(biāo)記該小節(jié)中的各個(gè)項(xiàng)．
對(duì)于缺乏基礎(chǔ)知識(shí)的學(xué)生，附錄A概述了有關(guān)集合、邏輯、歸納法、計(jì)數(shù)、二項(xiàng)式系數(shù)、關(guān)系和鴿巢原理等方面的相關(guān)知識(shí)．
對(duì)于很多證明都重新進(jìn)行了更細(xì)致的敘述，并增加了更多的例子．
增加了350多道習(xí)題，其中多數(shù)是第1～7章中的比較容易的題目．這樣，本書的總習(xí)題量超過了1 200道．
增加了100多幅插圖．本書的插圖總量超過了400幅．為區(qū)別插圖中包括的幾種類型的邊，書中把原有的實(shí)線和虛線改變?yōu)榇志�和實(shí)線，增加了插圖的清晰度．
相對(duì)簡(jiǎn)單的問題都集中放在各節(jié)習(xí)題的前面部分，用來作為熱身練習(xí)．一些習(xí)題進(jìn)行了改寫，使其語義更加清楚．
對(duì)習(xí)題的提示做了補(bǔ)充，增加了一個(gè)“部分習(xí)題的提示”的附錄．
為了易于查找，概念術(shù)語都用黑體字給出，其中絕大多數(shù)都出現(xiàn)在概念定義中．
為了易于查找，術(shù)語都集中在附錄D中．
有關(guān)歐拉回路、有向圖和Turán定理的內(nèi)容經(jīng)過了重新編排，以提高學(xué)習(xí)效率．
第6章和第7章交換了順序以便先介紹平面性的思想，與復(fù)雜度有關(guān)的部分經(jīng)過改編安排在附錄中．
改正了專業(yè)術(shù)語的錯(cuò)誤，并更加強(qiáng)調(diào)與本書內(nèi)容直接相關(guān)的術(shù)語．
特點(diǎn)
本書的特點(diǎn)就是使學(xué)生能夠深入理解本書的內(nèi)容．本書包括對(duì)證明技巧的討論、1 200多道習(xí)題、400多幅插圖以及許多例子．本書正文中出現(xiàn)的結(jié)論都有詳細(xì)完整的證明．
很多本科生在開始學(xué)習(xí)圖論前很少了解證明技巧，附錄A提供的數(shù)學(xué)基礎(chǔ)知識(shí)有助于初學(xué)者提高這方面的技巧．如果初學(xué)者在理解和書寫證明時(shí)有困難，請(qǐng)結(jié)合第1章仔細(xì)閱讀附錄A．雖然本書前面的一些章節(jié)仍然討論了一些證明技巧（特別是歸納法），但是更多的背景知識(shí)（特別是集合、函數(shù)、關(guān)系和初等計(jì)數(shù)）已經(jīng)安排在附錄A中．
大多數(shù)習(xí)題都需要證明．很多本科生在論證問題方面的實(shí)踐不足，這將影響他們對(duì)于圖論和其他數(shù)學(xué)知識(shí)的興趣．即使拋開數(shù)學(xué)，論證問題方面的智能訓(xùn)練也是極其重要的，作者希望學(xué)生喜歡這種訓(xùn)練．在求解問題時(shí)，學(xué)生應(yīng)該注意語言的使用（“說出的即是你要表達(dá)的”），而且表達(dá)準(zhǔn)確（“表達(dá)的即是你要說出的”）．
雖然圖論中許多術(shù)語本身就表明了它們各自的定義，但太多的專業(yè)術(shù)語定義會(huì)影響內(nèi)容的可讀性．?dāng)?shù)學(xué)家喜歡一開始就給出一系列定義，但學(xué)生們大都愿意熟練掌握一個(gè)概念后再去接受下一個(gè)概念，這樣他們會(huì)學(xué)得更好．學(xué)生的這個(gè)意愿和審稿者的建議使作者推遲了很多定義的給出，直到需要的時(shí)候．例如，笛卡兒積的定義在5.1節(jié)的著色問題部分給出，線圖的定義則分別在4.2節(jié)的Menger定理部分和7.1節(jié)的邊著色部分給出，誘導(dǎo)子圖的定義和連接的定義分別推遲到1.2節(jié)和3.1節(jié)給出．
書中已經(jīng)改變了對(duì)有向圖介紹的位置，將其推遲到了1.4節(jié)．如果在介紹圖的同時(shí)介紹有向圖，會(huì)使學(xué)生產(chǎn)生迷惑．在第1章的最后介紹有向圖的內(nèi)容結(jié)構(gòu)相對(duì)容易學(xué)習(xí)，學(xué)生能夠在了解兩種圖的差別的同時(shí)加強(qiáng)對(duì)基本概念的理解．在連通性問題上，本書仍會(huì)將這兩個(gè)模型放在一起討論．
本書比其他圖論書籍包含更多的內(nèi)容．作為“其他主題”的可選章節(jié)，最后一章匯集了很多圖論最新研究結(jié)果，使得本書適合不同層次的讀者使用．本科生的教學(xué)內(nèi)容可以由前七章組成（去掉大部分選學(xué)內(nèi)容），第8章可作為對(duì)相應(yīng)主題感興趣的學(xué)生的閱讀材料．研究生的教學(xué)內(nèi)容可以采用如下結(jié)構(gòu)：第1章和第2章作為推薦閱讀材料，在課堂上使學(xué)生快速進(jìn)入第3章的學(xué)習(xí)，并講授第8章的一些主題．第8章以及前面章節(jié)的選學(xué)內(nèi)容也可作為高級(jí)圖論課程的基本內(nèi)容．
很多圖論中的結(jié)論都有多個(gè)證明，這樣有助于提高學(xué)生采用多種方法處理問題的靈活性．對(duì)于同一個(gè)問題，本書可能在注記中談及一些不同的證明方法，另外一些留作練習(xí)．
很多習(xí)題都有提示，一些提示在習(xí)題中直接給出，另一些在附錄C中給