我是一個數(shù)學工作者，專業(yè)方向是圖論。研究圖論已經十年有余。一個月前，一個偶然的機會讓我萌生了一個念頭，那就是我想嘗試用C++寫出我所學過的圖論方面的算法。作為一個數(shù)學工作者，過去一直是紙上談兵，我之前并沒有真正寫過多少程序。確實，只知道寫證明的純理論的數(shù)學工作者往往自視甚高地看不起工程中實際寫程序的程序員（即使程序員圈子里也有不少厲害的數(shù)學工作者），另一個方向的鄙視鏈好像也一定程度上存在著。于是，我不想只作一個“思想上的巨人行動上的矮子”，便有了這個系列的博客。
首先聲明，我不是專業(yè)的程序員，只是大學里教數(shù)學的一個教書匠。程序寫得不好還請諸位指教。另一方面，工作上壓力也蠻大，有不少教學工作和論文方面的工作。所以我的博客可能無法定期更新。
然后說說我們的主要目標。目前我的目標是寫一下有關“圖的頂點染色”方面的算法，如果我足夠“有毅力”可以堅持下去的話（其實，之前也想做這件事情，后來都慢慢放棄了），將來看情況再寫寫其他方面，甚至于純粹的離散數(shù)學方面的內容。下面開始正題。
（一）圖論和頂點染色的相關簡介。
圖論的研究對象是“圖”，我們在數(shù)學上一般用G，H，F(xiàn)這幾個字母表示。設G是一個圖，一般認為G有兩部分組成，分別是頂點集V(G)和邊集E(G)，它們有時也簡寫作V和E，因而有時也將圖G更準確地表示為G(V,E)。畫在紙上看，一般是用小圓點表示圖的頂點，而用連接兩個小圓點的線表示邊。實際上，這恰恰暗示著圖G還有隱含的第三個部分，那就是頂點和邊的關聯(lián)關系，一般說，邊e與頂點u和v相關聯(lián)，直觀上看，就是圖上有一條線e將頂點u和v相連。由于這些“線”實際上只是體現(xiàn)邏輯上的關聯(lián)關系，所以這些具體的畫法一般沒有什么要求，當然筆者專業(yè)的拓撲圖論以及和圖論有些沾邊的“組合幾何學”（幾何圖論）有些例外，一般情況下是不做要求的。
設e是一個邊，它關聯(lián)的兩個頂點是u和v，則稱u和v是它的兩個端點，并且稱u和v是相鄰的。如果u=v，那么我們稱這個邊e是一個loop（國內中文書里翻譯這個loop有好幾種名字，為了不造成混亂，涉及學術名詞時，我盡量保持英文表述，除非中文已經有了確切的約定俗成）。如果關聯(lián)著u和v的邊不只一條，那么我們就稱這一組邊是一組平行邊（也叫重邊）。如果一個圖沒有平行邊也沒有l(wèi)oop，那么我們就稱這種圖是一個簡單圖（simple graph）。
下面說一下頂點染色?？紤]圖G(V,E)。設c是一個從V到集合{1, 2, ... , k}的映射（如果“映射”這個詞你聽起來不習慣，也可以把它換成“函數(shù)”，完全沒毛?。?，那么我們就說c是圖G上的一個k-頂點染色，簡稱k-染色（k-colouring），c的像集（或者說值域）{1, 2, ... , k}中的每個數(shù)字都叫做這個染色所用的顏色。如果進一步地，染色c能保證：任何邊不會連接顏色相同的頂點，那就說這個染色c是好的（proper）。
設c是圖G的所有好的染色中顏色個數(shù)最少的一個，那么就說c是G的最優(yōu)的頂點染色，并且稱c所用的顏色個數(shù)是G的色數(shù)（chromatic number），記作χ(G)。求圖G的色數(shù)的問題就是“圖的頂點染色問題”。
（二）游戲怎么玩？
1. 從圖的頂點染色的定義可以看出，平行邊的存在在染色問題中是沒有意義的，而loop的存在在染色問題中是致命的。所以，我們在染色問題中只考慮簡單圖。
2. 我們的程序需要用各種算例來檢驗，我將把這些算例用文本文件的形式存儲。每個算例都是一個隨機圖，它的每條邊的存在性由一個指定的概率給出，換言之，這個圖的邊集是等概率的。所以我們首先需要一個生成隨機圖的程序，這個程序將在下一篇中給出，要求是輸入兩個參數(shù)，一是圖的頂點數(shù)，二是每條邊出現(xiàn)的概率。這兩個參數(shù)能控制圖的稠密程度，一般來說，圖越稠密頂點染色的程序的實際耗時很可能越大，所以它們將是十分重要的參數(shù)。
3. 以后的算法中會出現(xiàn)其他一些概念，由于涉及圖論概念可能很多，所以我將不會一次性寫完，而是每次只寫這一篇所需要的概念。并在文章結尾處留下本篇所涉及者。
（三）本篇所列概念（依照出現(xiàn)次序）
圖；頂點集V(G)；邊集E(G)；關聯(lián)關系；
端點；相鄰的頂點；loop；平行邊，重邊；簡單圖；
<