數學遊戲「數三角形」的可編程圖論模型
華中師範大學
數學鑑賞課程論文
（本文僅供學習交流、參考 若需轉載 請註明出處）
題 目 數學遊戲「數三角形」的可編程圖論模型
指 導 老 師
院 系 物理科學與技術學院
專 業 電子信息工程
學 生 姓 名 XZH
學 號 2014xxxxxx
數學遊戲「數三角形」的可編程圖論模型
摘要
本文研究上課時所提到的數學遊戲「數三角形個數」問題。
首先，本文介紹了數學遊戲、圖論相關背景，重述、分析了上課時的「數三角形個數」問題。模型一爲老師上課介紹的分類討論，人工數數的方法。可讓人更有條理地分類、計數，得出題中共有35個三角形。但當圖中分割情況更復雜時，模型一無法用計算機實現，人工計算存在效率低下、錯誤率高等問題。
針對模型一的缺點，本文利用圖論、線性代數等知識，提出了一種可編程計數的圖論模型，即模型二、三、四。
模型二將形象的圖形轉化成模塊與模塊之間的鄰接圖，表示模塊之間的連通性，從而可使計算機讀取。若干個模塊若能拼接成一個三角形，那麼其中每個模塊必至少與其他一個模塊連通。因該鄰接圖爲無向圖，且爲稀疏矩陣，模型二幫助跳過了許多不需要進入判斷是否爲三角形環節的組合情況。實現時的算法複雜度低，運行速率快。
模型三通過建立點與點的鄰接圖矩陣，表示點之間的連通性。多個模塊拼接時，平面內存在多個點。結合平面幾何知識，通過座標最值取出決定三角形形狀的外圍點。僅當外圍點個數爲3，兩兩連通且不共線時，該組合纔有可能爲三角形。
模型四完善了模型三所不能考慮到的一些情況。當且僅當所有非外圍點在三角形邊上或內部時，所拼接圖形才爲三角形。通過利用模型三與平面幾何知識判斷點是否在邊上。通過線性代數向量叉乘知識，判斷點是否在三角形內。從而判決出該種模塊組合拼接成的圖形是否爲三角形。
本文通過上述模型，將該類問題純人工計數方法抽象爲數學化的、易用計算機計算的數學模型。當待數圖形分割更加複雜、模塊數量更多時，通過基礎的matlab編程驗證，計算機依然可根據這些模型快速、準確、高效地算出正確答案。
關鍵詞：圖論 鄰接圖 計算機求解 線性代數 數三角形遊戲
一、問題背景
1.1、數學遊戲概述
數學遊戲是一種智力遊戲。它主要是將各種各樣的數學問題滲透到遊戲當中，使人們在做遊戲的過程中用到相關的數學知識，並體現一定的數學思想和數學方法，從而激發大衆對數學的興趣，提高學習數學的自信心。相比一般遊戲它具有形象性、靈活性兩大特點。它通過生動有趣的事例將抽象的數學知識形象的表示出來，將枯燥的數學符號具體化。數學遊戲不同於數學習題，表現同一數學知識的形式靈活多樣，同時做遊戲的方式和方法也不拘一格，足以讓學生有較大的創造空間。[1]
1.2、 圖論知識背景
圖論是近年來發展迅速而又應用廣泛的一門學科。它最早起源於一些數學遊戲的難題研究，以及在民間廣泛流傳的一些遊戲難題。以後隨着科學的發展，圖論在解決工程科學、運籌學、網絡理論、信息論、控制論、博弈論以及計算機科學等各個領域的問題時，顯示出越來越大的效果[2]。在圖論發展的過程中，惠特尼、愛多士、塔特等[3]數學家做出了傑出的貢獻，最終利用圖論知識解決了四色問題。
1.3、圖論在數學問題與數學遊戲中的應用
圖論知識在數學問題、數學遊戲中有着十分廣泛的應用。如：經典的七橋問題[4]、渡河問題[5]、棋盤構形中同色矩形問題[6]、韓信勒馬分油問題[7]等。並在數學競賽[8]中有一定的應用。圖論知識可以將生活中形象的問題抽象成數學問題，將一些看似別的領域的知識抽象成數學可表示、計算機可求解的問題。
二、問題重述
在五月份的數學鑑賞課堂上，老師曾出過這樣一個數學遊戲問題：給出一個圖形，如圖一所示，數出圖形中三角形的個數。
圖一 問題原圖
三、問題分析
針對本問題，提出四個數學模型。
第一個模型爲上課時老師所介紹的模型，即分類討論、人工數數法。根據組成最終三角形的小模塊個數對其進行分類討論。先數由一個小模塊構成的三角形的個數，再數由兩個模塊構成的三角形的個數，以此類推。該方法不易用計算機實現，人工操作速度、精度難以保證。
第二個模型爲模塊與模塊的鄰接圖模型。將題目中的1~11模塊抽象成點，通過一個鄰接圖表達各個模塊之間的連通性。在模型一的方法基礎上，該模型可確保所數三角形無遺漏、跳過一些不必要的判斷，並易於計算機存儲問題數據的模型。
第三個模型爲點與點的圖模型。該圖表示任意兩點的連通關係。並利用平面幾何知識找出可能確定每種情況下的三角形形狀的三個「外圍點」。僅當三個「外圍點」兩兩連通並不共線，纔有可能組成三角形。
第四個模型爲判斷點與線關係的線性代數模型。通過模型三可判斷出某點是否在另外兩點所構成的線段上。通過向量叉乘的結果可知某點是否在三角形內部，從而決定這些點與模塊所構成的圖形是否爲三角形。至此即可讓計算機無遺漏、高效地數出圖中三角形個數，並可對一般化情況進行推廣。
定義n爲拼接成圖形的模塊數量，n2時，判斷流程如圖二所示：
圖二 判決圖形是否爲三角形流程圖
四、符號說明及名詞定義
4.1、外圍點
三角形由且僅由平面內三個點唯一確定。在此我們稱確定三角形形狀的三個點爲「外圍點」。每個外圍點的橫或縱座標中至少有一個座標爲平面上所有點的橫或縱座標的最值。非外圍點應位於三個外圍點所圍成的圖形邊上或內部，平面上所有點才能構成一個三角形。
4.2、模塊與點的定義
如下圖的圖三、圖四，爲該圖中11個小模塊、交點分別按照圖中所示進行1~11與A~G的編號。稱各模塊爲模塊1，模塊2……，各點爲點A,點B……以此類推。
圖三 原圖中各模塊定義示意圖
圖四 原圖各點定義示意圖
五、模型建立與求解
5.1.1、模型一的建立
模型一爲分類討論、人工數數法。即根據組成最終三角形的小模塊個數對其進行分類討論。先數由一個小模塊構成的三角形的個數，再數由兩個模塊構成的三角形的個數，以此類推。
5.1.2、模型一的求解
首先討論由一個小模塊組成的三角形。觀察易得1,2,3,4,5,8,9,11模塊爲三角形。故一個小模塊所組成的三角形共8個。
接下來討論由兩個小模塊所組成的三角形。觀察易得1和2,1和5,2和3,2和6,3和4，3和7,4和8,7和8，8和11，10和11模塊所組成圖形爲三角形。故由兩個小模塊所組成的三角形共10個。
同上可得，由三、四、五、六、七個模塊所組成的三角形各有8、5、1、2、1個。
根據上述分類討論結果可知，該圖形中共有8+10+8+5+1+2+1=35個三角形。
5.2.1、模型二的建立
當圖中模塊數足夠大時，模型一的方法因屬於人工判別法，難以用計算機實現，也將變得不可靠。且在數由若干個小模塊組成的三角形個數時，需要遍歷所有情況進行判斷是否爲三角形，否則易出現差錯，造成效率低下。
針對模塊一上述兩個缺點，提出模型二，即模塊與模塊的鄰接圖模型。根據圖論相關知識，將圖中每個模塊抽象成點，通過模塊與模塊的鄰接圖矩陣表示模塊與模塊之間的連通性。設k(i,j)表示矩陣中第i行第j列的位置，則
根據此規則，可對本題的圖形建立鄰接矩陣，如圖五所示。
圖五：根據本題原圖建立的模塊鄰接圖矩陣
該矩陣反應了模塊與模塊之間的連通性。由於1和2相聯通等價於2和1相聯通，因此該圖是一個無向圖。對於無向圖，我們只需考察其右上方部分或左下方部分即可。
由圖形可直觀地看出，處於邊緣的模塊大多隻與兩個模塊存在鄰接關係，處於中間的模塊至多也只與四個模塊存在鄰接關係。在圖論中，我們用度描述一個點連通的其他點的數量。顯然，在此類數三角形問題中，每個模塊的度都遠小於總模塊數。故該鄰接圖是一個0的數量遠大於1的稀疏矩陣。
易證明，若幾個模塊所拼成的圖形爲三角形，那麼在這幾個模塊中，每個模塊至少與其他一個模塊存在鄰接關係，以保證它們可以拼起來。如：考察模塊1,2,3,10是否有可能拼成三角形時，由鄰接圖可知，10與其餘三個模塊均不連通，則不需判斷該模塊是否爲三角形即可直接捨棄該情況。再如：考察模塊1,2,3,4是否有可能拼成三角形時，由鄰接圖可知，1與2連通，2與3連通，3與4連通，故1,2,3,4可以拼成一個連通的圖形，再去判斷其是否爲三角形。如圖六中模塊1與模塊2、3均不連通，因此模塊1,2,3無法構成一個三角形。
圖六 因模塊之間不連通所以無法構成三角形的情況
綜上可知，在對一個組合是否爲三角形進行判斷前，我們可以先根據鄰接圖快速地判斷出其是否能組成一個連通的圖，若無法組成，則可直接跳過該階段，若可組成，則對其進行判斷。又因爲模塊與模塊之間的鄰接圖是一個無向圖，且爲0的數量遠大於1的稀疏矩陣，故所需遍歷的情況將大大減少，且根據鄰接圖將不會出現遺漏等情況，易於用計算機實現求解。
5.2.2、模型二的求解
繼承模型一分類討論的思想，先考慮由一個模塊所組成的三角形的情況，此情況下有8個三角形。
接着考慮多個模塊組成三角形的情況。當考慮兩個模塊時，只需考慮鄰接圖中值爲1的組合情況，並將需判斷的連通組合情況記錄入一個表中。當考慮三個模塊時，對剛纔生成的表進行遍歷，假設表中的第n項的兩個模塊爲a,b，則找出a,b兩個模塊分別連通的模塊（除了a,b本身）構成一個集合。例如，假設a與b,c模塊連通，b與a,d模塊連通，則構成集合{c,d}。每次從集合中取出一個模塊加入該表該項中的情況進行判斷，如此時應分別討論a和b和c，a和b和d這兩種情況,並將本表所引出的討論情況記在一個新表中，方便下一輪繼續討論。以此類推，當考慮k個模塊的情況時，若k>11，則結束。
根據此方法判斷，不難求出三角形總數爲35個。
5.3、模型三的建立
模型二給出了一種可讓計算機無遺漏地遍歷、並大大減少了判斷次數的方法，但是判斷時仍需人工判斷其組合是否爲三角形。
5.3.1、鄰接圖矩陣
針對模型二仍存在的問題，提出模型三，即關於點的鄰接圖。設L(i,j)表示矩陣中第i行第j列的位置，則
根據此規則，可對本題的圖形建立點的鄰接矩陣，如圖七所示。
圖七：根據本題原圖建立的點與點鄰接圖矩陣
5.3.2、外圍點
在本文4.1節已定義過外圍點的定義，現給出其數學模型。
易知存在由多個模塊所確定的n個點時，若這些模塊可構成三角形，則外圍點的座標(xi,yi)需至少滿足如下條件之一：
由此可確定出多個模塊所拼接圖形的外圍點。僅當該圖形的外圍點有三個，即這三個點中有兩個點滿足上述條件之一，有一個點滿足上述條件中的兩個，且三點兩兩之間連通、不共線時，該圖形纔可能爲三角形。
5.4.1、模型四的建立
模型三已可判斷出多數情況下的圖形是否爲三角形，但存在這樣一種情況，滿足模型三條件但所拼接圖形不爲三角形，如圖八所示。此時A,B,C爲外圍點，兩兩連通且不共線上，但D點的存在使拼接圖形不爲三角形。
圖八 僅根據模型三無法正確判決的情況
因此在找出三個外圍點後，仍需對多餘的點進行考察。三角形由且僅由平面上三個點唯一確定。若平面上有其他點，則應位於該三點所組成線段上或圍成圖形的內部。對此，建立模型四，即線段與非外圍點的關係模型。
5.4.1.1、非外圍點在三角形邊上的情況
根據平面直線方程與座標關係可知，用Ax,Ay,Bx,By,Dx,Dy分別表示點A,B,D的橫縱座標，若點D的橫縱座標同時滿足如下關係時：
點A,B,D三點共線，且點D在線段A,B上。點A,B,D所組成的線段可用點A,B所組成的線段表示，此時點A,B,C,D組成的圖形仍爲三角形。
5.4.1.2、非外圍點在三角形內的情況
由平面幾何知識可得，假設點A,B,C爲某一拼接圖形的外圍點且不共線，點D爲非外圍點且不在AB,BC,AC所在的直線上時，若這四點所確定的圖形爲三角形，則點D必在該三角形內。
由線性代數知識可知，當點D在三角形內時，他們在座標上的關係應滿足：
其中涉及到的向量運算符號爲向量的叉乘。設二維向量,分別爲(ax,ay)，(bx,by),則叉乘運算結果爲：
僅當滿足模型三的組合滿足模型四兩種情況的任意一種時，才判決該組合組成了三角形。通過matlab編程可計算出圖中共有35個三角形，運行時間約1秒。
六、模型評價
模型一爲上課時老師介紹的方法，根據組成最終三角形的小模塊個數對其進行分類討論。此方法需要遍歷每一種組合情況，需進行大量通過圖論模型可以跳過的判斷，耗時較多，且因不便用計算機求解，無法避免人工數數難免會出現的誤差可能。
模型二利用圖論知識，決定了遍歷過程中哪些模塊組合情況需要進入判斷是否爲三角形的階段。相比模型一最大的優點是可通過計算機編程實現，代替人工。程序實現時，每輪通過建立一個表存儲上一輪判決情況，算法複雜度控制在O(a*n^2)。因該鄰接圖矩陣爲一個無向圖，算法複雜度將減小一半。又因爲其爲稀疏矩陣，故a實際爲一個遠小於1的係數。在n沒有非常大時（實際數學遊戲、生活問題中n一般小於20），算法複雜度可近似爲O(n)。
模型三、模型四利用圖論、線性代數等知識，使計算機可判斷模塊拼接圖形是否爲三角形。其優勢仍在於可用計算機編程解決，且算法複雜度爲O(n)，執行高效。當n很大、分割更復雜時，利用模型一的方法，人工判決耗時多、存在誤差，而計算機可通過上述模型在幾秒內給出精確結果。模型的一般性、可推廣性強，不會受n的大小、圖形分割情況等所影響。
七、參考文獻
[1]. 成繼紅與劉良華, 數學遊戲的價值及應用. 湖北科技學院學報, 2014(07): 第118-119頁.
[2]. 孫樂, 具有長度約束的路徑數研究, 2012, 河北工業大學. 第 50頁.
[3]. 王麗麗, 圖論的歷史發展研究, 2012, 山東大學. 第 60頁.
[4]. 肖鑑鏗, 歐拉巧解七橋問題. 初中生之友, 2003(Z3): 第65-67頁.
[5]. 達瓦與加央, 種種渡河問題及其算法. 科教文匯(上旬刊),2008(08): 第269-270頁.
[6]. 沈羣, 關於棋盤構形中同色矩形問題的一些探討. 太原科技大學學報,2006(03): 第210-213頁.
[7]. 降毅, 用圖論的方法解兩道智力題. 河套大學學報, 2004(01): 第14-16頁.
[8]. 吳康與劉芸, 圖論與中學數學競賽(一). 中學數學,1987(11): 第29-34頁.