圖論是數(shù)學(xué)的一個(gè)獨(dú)立分支，與整個(gè)數(shù)學(xué)領(lǐng)域都有聯(lián)系，從抽象代數(shù)和拓?fù)鋵W(xué)等純數(shù)學(xué)部分，到運(yùn)籌學(xué)和計(jì)算等應(yīng)用數(shù)學(xué)部分，再到化學(xué)、生物學(xué)和電子學(xué)等其他科學(xué)領(lǐng)域。英國(guó)南安普頓大學(xué)研究生圖論課程介紹了圖論的基本概念，主要關(guān)注有限圖。課程內(nèi)容涉及圖的數(shù)值不變量和計(jì)算它們的方法；如何瀏覽圖；圖的點(diǎn)和邊著色以及圖的其他數(shù)值不變量；圖是平面的條件；以及隨機(jī)圖理論的基礎(chǔ)知識(shí)。課程概述如下。

一、內(nèi)容摘要

1、圖的基本數(shù)值的定義，包括直徑和半徑、最小和最大度、圍長(zhǎng)和周長(zhǎng)、色數(shù)和色指數(shù)、團(tuán)數(shù)和獨(dú)立數(shù)；除此之外，還可以包括其他不變量。

2、歐拉圖，以及圖是歐拉圖的充要條件。

3、哈密爾頓圖，以及圖是哈密爾頓圖的充分條件，包括Ore定理。

4、樹，包括普魯弗序列和完全圖的生成樹數(shù)的凱萊定理。

5、平面圖形，包括歐拉公式的陳述、證明和應(yīng)用；庫(kù)拉托夫斯基定理的陳述(但不是證明)。

6、圖的頂點(diǎn)著色，包括產(chǎn)生頂點(diǎn)著色的貪婪算法和Brooks定理的陳述。

7、平面圖的頂點(diǎn)著色，包括五色定理的陳述和證明，以及四色定理的陳述。

8、圖的邊著色，包括二部圖的邊著色，以及Vizing定理和Koenig定理的陳述。

9、隨機(jī)圖的基本定義和性質(zhì)；關(guān)于大圍長(zhǎng)和大色數(shù)圖存在性的Erdos定理。

二、學(xué)習(xí)目標(biāo)

1、陳述和應(yīng)用教學(xué)大綱中描述的圖形性質(zhì)的定義和基本結(jié)果，并確定這些性質(zhì)是否適用于特定的圖的例子和類別，以及圖的構(gòu)造。

2、陳述教學(xué)大綱中描述的與圖形相關(guān)的數(shù)值不變量的定義，在證明中使用這些定義，并且計(jì)算特定例子和圖類以及圖構(gòu)造的這些不變量。

同學(xué)可以根據(jù)上述內(nèi)容摘要來(lái)規(guī)劃學(xué)習(xí)安排，無(wú)論是課前預(yù)習(xí)還是課后復(fù)習(xí)，都有助于達(dá)成學(xué)習(xí)目標(biāo)，從而在南安普頓大學(xué)圖論課程評(píng)估中取得好成績(jī)。