§2.1 圖的定義
以數學物件表示的話，一般來說我們會把圖定義為由點集合 $V$ 和邊集合 $E$ 所形成的配對 $G=(V, E)$。
§2.2 圖的分類
當我們把模型抽象變成只有點和邊的時候，根據各種需求我們會自然地把所有可能的圖進行分類。比方說根據定義我們可以寫下無向圖、有向圖、無權圖、加權圖、重圖（Multi graph）、近圖（Pseudo graph）、簡單圖、無限圖等等。在這些圖上我們又可以定義道路（Walk）、行跡（Trail）、路徑（Path）、圈或環（Cycle）、連通元件（Connected Components）等等。
基於這些基本的定義，我們可以刻劃並且分類出一系列具備相同性質的圖。 比方說：連通圖是一類滿足「任兩點之間都存在一條路徑的無向圖」、而樹是一類滿足「任兩點之間都存在恰好一條路徑的無向圖」、而平面圖是一類滿足「可以把該圖繪製在歐幾里得平面上，使任兩條邊都不相交的圖」等等。
根據圖分類衍伸的問題
只要有一個性質 $P$，我們就可以把所有滿足該性質 $P$ 的圖蒐集起來變成一個類別 $\mathcal{G}_P$。通常我們對於與性質 $P$ 相關的計算問題有以下幾種類型：
- 辨認問題（Recognition Problem）：給定圖 $G$，判斷是否 $G\in \mathcal{G}_P$。
- 辨認且舉證（Witness Problem）：給定圖 $G$，除了判斷是否 $G\in\mathcal{G}_P$ 以外，還必須輸出一個簡潔的證據，使得基於這個證據能夠有更有效率的驗證方法。
- 列舉問題（Enumeration Problem）：給定額外性質 $Q$，找出（或計數）所有 $\mathcal{G}_P$ 中滿足性質 $Q$ 的圖。
- 簡潔資料結構（Succinct Data Structure）：能否將該類圖用較少的記憶體儲存之，並且仍能夠提供足夠有效率的資料結構操作。
§2.3 關於輸入格式
稍早提到的電腦與圖靈機等等，其輸入內容都是二元字串。要怎麼把一個輸入圖論的圖以二元字串來表達呢？對於一些計算問題而言，不同的輸入方式會造成演算法有著不同的執行效率。說得誇張一點的話，甚至會造成若干數量級的效率差異。
但其實這就是約定俗成的東西，在沒有特別說明的情況下，我們總是可以依照圖的定義 $G=(V, E)$，將所有點集合 $V$ 和邊集合 $E$ 的物件依序列出來，作為電腦的輸入。因此，決定演算法執行效率的重點，在於輸入後我們將以什麼樣的資料結構儲存這個圖。
§2.4 關於資料結構
一般來說儲存一張圖的方式有鄰接矩陣（Adjacency Matrix）和鄰接串列（Adjacency Lists）兩種方式。這兩種方式有各自的優缺點，大家有興趣可以想一下，這裡就不贅述了。