我是一個數(shù)學(xué)工作者，專業(yè)方向是圖論。研究圖論已經(jīng)十年有余。一個月前，一個偶然的機(jī)會讓我萌生了一個念頭，那就是我想嘗試用C++寫出我所學(xué)過的圖論方面的算法。作為一個數(shù)學(xué)工作者，過去一直是紙上談兵，我之前并沒有真正寫過多少程序。確實(shí)，只知道寫證明的純理論的數(shù)學(xué)工作者往往自視甚高地看不起工程中實(shí)際寫程序的程序員（即使程序員圈子里也有不少厲害的數(shù)學(xué)工作者），另一個方向的鄙視鏈好像也一定程度上存在著。于是，我不想只作一個“思想上的巨人行動上的矮子”，便有了這個系列的博客。

首先聲明，我不是專業(yè)的程序員，只是大學(xué)里教數(shù)學(xué)的一個教書匠。程序?qū)懙貌缓眠€請諸位指教。另一方面，工作上壓力也蠻大，有不少教學(xué)工作和論文方面的工作。所以我的博客可能無法定期更新。

然后說說我們的主要目標(biāo)。目前我的目標(biāo)是寫一下有關(guān)“圖的頂點(diǎn)染色”方面的算法，如果我足夠“有毅力”可以堅持下去的話（其實(shí)，之前也想做這件事情，后來都慢慢放棄了），將來看情況再寫寫其他方面，甚至于純粹的離散數(shù)學(xué)方面的內(nèi)容。下面開始正題。

（一）圖論和頂點(diǎn)染色的相關(guān)簡介。

圖論的研究對象是“圖”，我們在數(shù)學(xué)上一般用G，H，F(xiàn)這幾個字母表示。設(shè)G是一個圖，一般認(rèn)為G有兩部分組成，分別是頂點(diǎn)集V(G)和邊集E(G)，它們有時也簡寫作V和E，因而有時也將圖G更準(zhǔn)確地表示為G(V,E)。畫在紙上看，一般是用小圓點(diǎn)表示圖的頂點(diǎn)，而用連接兩個小圓點(diǎn)的線表示邊。實(shí)際上，這恰恰暗示著圖G還有隱含的第三個部分，那就是頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系，一般說，邊e與頂點(diǎn)u和v相關(guān)聯(lián)，直觀上看，就是圖上有一條線e將頂點(diǎn)u和v相連。由于這些“線”實(shí)際上只是體現(xiàn)邏輯上的關(guān)聯(lián)關(guān)系，所以這些具體的畫法一般沒有什么要求，當(dāng)然筆者專業(yè)的拓?fù)鋱D論以及和圖論有些沾邊的“組合幾何學(xué)”（幾何圖論）有些例外，一般情況下是不做要求的。

設(shè)e是一個邊，它關(guān)聯(lián)的兩個頂點(diǎn)是u和v，則稱u和v是它的兩個端點(diǎn)，并且稱u和v是相鄰的。如果u=v，那么我們稱這個邊e是一個loop（國內(nèi)中文書里翻譯這個loop有好幾種名字，為了不造成混亂，涉及學(xué)術(shù)名詞時，我盡量保持英文表述，除非中文已經(jīng)有了確切的約定俗成）。如果關(guān)聯(lián)著u和v的邊不只一條，那么我們就稱這一組邊是一組平行邊（也叫重邊）。如果一個圖沒有平行邊也沒有l(wèi)oop，那么我們就稱這種圖是一個簡單圖（simple graph）。

下面說一下頂點(diǎn)染色?？紤]圖G(V,E)。設(shè)c是一個從V到集合{1, 2, ... , k}的映射（如果“映射”這個詞你聽起來不習(xí)慣，也可以把它換成“函數(shù)”，完全沒毛?。敲次覀兙驼fc是圖G上的一個k-頂點(diǎn)染色，簡稱k-染色（k-colouring），c的像集（或者說值域）{1, 2, ... , k}中的每個數(shù)字都叫做這個染色所用的顏色。如果進(jìn)一步地，染色c能保證：任何邊不會連接顏色相同的頂點(diǎn)，那就說這個染色c是好的（proper）。

設(shè)c是圖G的所有好的染色中顏色個數(shù)最少的一個，那么就說c是G的最優(yōu)的頂點(diǎn)染色，并且稱c所用的顏色個數(shù)是G的色數(shù)（chromatic number），記作χ(G)。求圖G的色數(shù)的問題就是“圖的頂點(diǎn)染色問題”。

（二）游戲怎么玩？

1. 從圖的頂點(diǎn)染色的定義可以看出，平行邊的存在在染色問題中是沒有意義的，而loop的存在在染色問題中是致命的。所以，我們在染色問題中只考慮簡單圖。

2. 我們的程序需要用各種算例來檢驗(yàn)，我將把這些算例用文本文件的形式存儲。每個算例都是一個隨機(jī)圖，它的每條邊的存在性由一個指定的概率給出，換言之，這個圖的邊集是等概率的。所以我們首先需要一個生成隨機(jī)圖的程序，這個程序?qū)⒃谙乱黄薪o出，要求是輸入兩個參數(shù)，一是圖的頂點(diǎn)數(shù)，二是每條邊出現(xiàn)的概率。這兩個參數(shù)能控制圖的稠密程度，一般來說，圖越稠密頂點(diǎn)染色的程序的實(shí)際耗時很可能越大，所以它們將是十分重要的參數(shù)。

3. 以后的算法中會出現(xiàn)其他一些概念，由于涉及圖論概念可能很多，所以我將不會一次性寫完，而是每次只寫這一篇所需要的概念。并在文章結(jié)尾處留下本篇所涉及者。

（三）本篇所列概念（依照出現(xiàn)次序）

圖；頂點(diǎn)集V(G)；邊集E(G)；關(guān)聯(lián)關(guān)系；

端點(diǎn)；相鄰的頂點(diǎn)；loop；平行邊，重邊；簡單圖；

k-頂點(diǎn)染色，k-染色；顏色；好的染色；

最優(yōu)的頂點(diǎn)染色；色數(shù)χ(G)；圖的頂點(diǎn)染色問題。

標(biāo)簽: 圖, 圖的頂點(diǎn)染色

我是一個數(shù)學(xué)工作者，專業(yè)方向是圖論。研究圖論已經(jīng)十年有余。一個月前，一個偶然的機(jī)會讓我萌生了一個念頭，那就是我想嘗試用C++寫出我所學(xué)過的圖論方面的算法。作為一個數(shù)學(xué)工作者，過去一直是紙上談兵，我之前并沒有真正寫過多少程序。確實(shí)，只知道寫證明的純理論的數(shù)學(xué)工作者往往自視甚高地看不起工程中實(shí)際寫程序的程序員（即使程序員圈子里也有不少厲害的數(shù)學(xué)工作者），另一個方向的鄙視鏈好像也一定程度上存在著。于是，我不想只作一個“思想上的巨人行動上的矮子”，便有了這個系列的博客。

首先聲明，我不是專業(yè)的程序員，只是大學(xué)里教數(shù)學(xué)的一個教書匠。程序?qū)懙貌缓眠€請諸位指教。另一方面，工作上壓力也蠻大，有不少教學(xué)工作和論文方面的工作。所以我的博客可能無法定期更新。

然后說說我們的主要目標(biāo)。目前我的目標(biāo)是寫一下有關(guān)“圖的頂點(diǎn)染色”方面的算法，如果我足夠“有毅力”可以堅持下去的話（其實(shí)，之前也想做這件事情，后來都慢慢放棄了），將來看情況再寫寫其他方面，甚至于純粹的離散數(shù)學(xué)方面的內(nèi)容。下面開始正題。

（一）圖論和頂點(diǎn)染色的相關(guān)簡介。

圖論的研究對象是“圖”，我們在數(shù)學(xué)上一般用G，H，F(xiàn)這幾個字母表示。設(shè)G是一個圖，一般認(rèn)為G有兩部分組成，分別是頂點(diǎn)集V(G)和邊集E(G)，它們有時也簡寫作V和E，因而有時也將圖G更準(zhǔn)確地表示為G(V,E)。畫在紙上看，一般是用小圓點(diǎn)表示圖的頂點(diǎn)，而用連接兩個小圓點(diǎn)的線表示邊。實(shí)際上，這恰恰暗示著圖G還有隱含的第三個部分，那就是頂點(diǎn)和邊的關(guān)聯(lián)關(guān)系，一般說，邊e與頂點(diǎn)u和v相關(guān)聯(lián)，直觀上看，就是圖上有一條線e將頂點(diǎn)u和v相連。由于這些“線”實(shí)際上只是體現(xiàn)邏輯上的關(guān)聯(lián)關(guān)系，所以這些具體的畫法一般沒有什么要求，當(dāng)然筆者專業(yè)的拓?fù)鋱D論以及和圖論有些沾邊的“組合幾何學(xué)”（幾何圖論）有些例外，一般情況下是不做要求的。

設(shè)e是一個邊，它關(guān)聯(lián)的兩個頂點(diǎn)是u和v，則稱u和v是它的兩個端點(diǎn)，并且稱u和v是相鄰的。如果u=v，那么我們稱這個邊e是一個loop（國內(nèi)中文書里翻譯這個loop有好幾種名字，為了不造成混亂，涉及學(xué)術(shù)名詞時，我盡量保持英文表述，除非中文已經(jīng)有了確切的約定俗成）。如果關(guān)聯(lián)著u和v的邊不只一條，那么我們就稱這一組邊是一組平行邊（也叫重邊）。如果一個圖沒有平行邊也沒有l(wèi)oop，那么我們就稱這種圖是一個簡單圖（simple graph）。

下面說一下頂點(diǎn)染色?？紤]圖G(V,E)。設(shè)c是一個從V到集合{1, 2, ... , k}的映射（如果“映射”這個詞你聽起來不習(xí)慣，也可以把它換成“函數(shù)”，完全沒毛?。?，那么我們就說c是圖G上的一個k-頂點(diǎn)染色，簡稱k-染色（k-colouring），c的像集（或者說值域）{1, 2, ... , k}中的每個數(shù)字都叫做這個染色所用的顏色。如果進(jìn)一步地，染色c能保證：任何邊不會連接顏色相同的頂點(diǎn)，那就說這個染色c是好的（proper）。

設(shè)c是圖G的所有好的染色中顏色個數(shù)最少的一個，那么就說c是G的最優(yōu)的頂點(diǎn)染色，并且稱c所用的顏色個數(shù)是G的色數(shù)（chromatic number），記作χ(G)。求圖G的色數(shù)的問題就是“圖的頂點(diǎn)染色問題”。

（二）游戲怎么玩？

1. 從圖的頂點(diǎn)染色的定義可以看出，平行邊的存在在染色問題中是沒有意義的，而loop的存在在染色問題中是致命的。所以，我們在染色問題中只考慮簡單圖。

2. 我們的程序需要用各種算例來檢驗(yàn)，我將把這些算例用文本文件的形式存儲。每個算例都是一個隨機(jī)圖，它的每條邊的存在性由一個指定的概率給出，換言之，這個圖的邊集是等概率的。所以我們首先需要一個生成隨機(jī)圖的程序，這個程序?qū)⒃谙乱黄薪o出，要求是輸入兩個參數(shù)，一是圖的頂點(diǎn)數(shù)，二是每條邊出現(xiàn)的概率。這兩個參數(shù)能控制圖的稠密程度，一般來說，圖越稠密頂點(diǎn)染色的程序的實(shí)際耗時很可能越大，所以它們將是十分重要的參數(shù)。

3. 以后的算法中會出現(xiàn)其他一些概念，由于涉及圖論概念可能很多，所以我將不會一次性寫完，而是每次只寫這一篇所需要的概念。并在文章結(jié)尾處留下本篇所涉及者。

（三）本篇所列概念（依照出現(xiàn)次序）

圖；頂點(diǎn)集V(G)；邊集E(G)；關(guān)聯(lián)關(guān)系；

端點(diǎn)；相鄰的頂點(diǎn)；loop；平行邊，重邊；簡單圖；

k-頂點(diǎn)染色，k-染色；顏色；好的染色；

最優(yōu)的頂點(diǎn)染色；色數(shù)χ(G)；圖的頂點(diǎn)染色問題。

標(biāo)簽: 圖, 圖的頂點(diǎn)染色

http://www.cnblogs.com/songningmath/p/6916015.html