數學競賽中圖論問題的相關分析

郁文娟

【摘 要】圖論不僅是數學競賽中的重要組成部分，同時在其他領域中也有應用到，如在計算機技術以及物理學中應用相當廣泛。可以利用圖論的相關知識來解決這些領域中出現的各類問題，因為它可以利用數學模型的形式把這些問題呈現出來，更直觀和清晰，利于人們對問題的認識和理解，從來更加快速方便的解決問題。本文主要分析在數學競賽中，圖論問題應用的重要性。

【關鍵詞】圖論問題；數學競賽；應用分析

中圖分類號： O157.5 文獻標識碼： A 文章編號： 2095-2457（2018）30-0152-002

DOI：10.19694/j.cnki.issn2095-2457.2018.30.066

Correlation analysis of graph theory in Mathematical Contest

YU Wen-juan

（School of modern science and technology， Taiyuan University of Technology， Taiyuan Shanxi 030027，China）

【Abstract】Graph theory is not only an important part of the mathematical contest， but also has been applied in other fields， such as computer technology and physics is widely used. Graph theory can be used to solve all kinds of problems in these fields， because it can be used in the form of mathematical models to present these problems， more intuitive and clear， conducive to people's understanding and understanding of the problem， has always been faster and more convenient to solve the problem. This paper mainly analyzes the importance of the application of graph theory in mathematical competition.

【Key words】Graph theory problem； Mathematical contest； Application analysis

1 數學競賽中應用圖論問題的意義

圖論問題在18世紀初期就已經開始有運用，由于現代計算機的出現，圖論的應用則越來越廣泛，包括結構化學、計算機網絡以及數學競賽等。使用圖論可以提供給我們一個快速解決問題的方式和角度。數學題中應用題相對偏多，而應用題往往都是在實際背景下產生出來的題型，在數學競賽中是一種相對比較重要且難度較大的題型，主要考查學生如何通過數學相關的知識來解決和分析實際問題的能力，而這個能力則是通過解決數學圖論的能力來展現。

1.1 圖論在數學競賽中的應用與生活緊密相關

圖論是研究空間模式德昂以及現實世界中的數量之間的關系。數學這門學科想要對問題處理的結果取得更加精確的結論，不能單靠一個不清晰的定義，而要追求更嚴密的概念。同時，利用圖論中的相關概念以及定義來思考和解決問題，也可以更加直觀的、更加自然的讓問題得到很好的解決。

1.2 圖論實現了科學技術在數學中的有效轉化

人們在用數學的方式解決每一個實際問題時，其本質就是簡化所表達的問題，然后將其中的抽象知識用一個數學模型的方式簡單的展現出來，利用一些先進的技術，如計算機技術來求解模型，最后再重復的推理以及完善結果的準確度，直至滿足事情原本所需的要求。

1.3 數學競賽中使用圖論促進數學教學的創新改革，適應社會的發展進度

數學教學的創新改革對社會發展的意義并不完全是傳授相關知識給學生，而是要促進學生更好的掌握數學這門學科的技能以及思想方法。然而，想要改善我們目前對數學教學的方式，既可以讓學生有效的學到知識，又可以提高教學效率和成果，利用數學圖論競賽是極其重要以及必要的。

2 數學競賽中常出現的與圖論相關的問題

2.1 圖的貫通性問題

在考察圖的貫通性時，一般會存在兩種題型，第一，至少應該除掉幾條邊來破壞原圖中的貫通性；第二，即使將原圖連通，在除掉有限條邊的情況下，這個圖是否依然可以連通。

2.2 圖的遍歷問題

不管在實際生活中，還是在理論依據上存在的某些問題，都有一部分跟遍歷性有著緊密聯系，如有名的哥尼斯堡七橋中出現的問題是最早引出遍歷問題的。哥尼斯堡城的城區分為四個部分，它們之間由七座橋相互連接而成，怎樣既可以將這七座橋都走完并且每座橋只能走一次，同時又可以環繞全程？1736年，歐拉用抽象分析法將問題簡化為圖論問題，這也是歷史上的首個圖論問題，順利的將這個問題得以解決。其實這個問題的實質就是要在圖中找到一條封閉式的路，這條路要包含這個圖中所有的邊，所以就可以將這個問題簡化為“一筆畫”的問題。

3 解決數學競賽中圖論問題的常用方法

數學與圖論跟其他有著完善理論和問題解決辦法的體系不同，其分支不同，問題涉及比較廣泛，同時有著多樣的問題解決方法，一般情況下，一類問題往往存在一種解法，然而不同的解法間缺少一些相關的聯系。有一句老話說道，“工欲善其事，必先利其器”，數學競賽中要使用圖論問題，就得先對圖論進行了解、探索，其中要了解圖論存在哪些問題以及常見的處理問題的方法，再具體進行運用。而在圖論問題中，主要研究其組合最值以及存在性兩個問題。

3.1 組合最值問題

解決組合最值問題時，往往還存在一些通過利用圖形特點來解決組合最值的問題，因為其自變量是離散量，并且要求的最小值或最大值的量與自變量的函數關系不允許用同一個解析式來表達，所以就使得先前代數最值的問題與解決組合最值的問題有所不同。常見的解決辦法主要有以下幾點：

3.1.1 構造法

關于構造圖論問題，通常會先將其進行轉換，主要運用各類圖的性質及自身特征的方式，此外，有時也會采用染色的方式進行標注，將具有不同性質但類別相同的圖區別分開，簡化問題，以避免圖論問題出現在數學競賽中，加深競賽的難度。

3.1.2 調整法

要將調整法運用到圖論問題中，必須先要確定存在可以取最值的結構組合，然后在取最值時要充分觀察以及分析研究，選擇組合對象可能滿足的特質，同時要用調整法來體現出它所具備的特質，在不具備該特質的情況下，應當及時調整改編組合對象的結構，促使其能夠滿足題目要求的條件，但會使相應的函數值變大或變小，以致出現矛盾，最后通過在取最值時，滿足組合對象相應的條件來解出這個最值。

3.2 存在性問題

存在性問題的解決方法主要采用反證法、抽屜原理、計數法以及極端原理等方法。

3.2.1 反證法

如果要證明命題的的結論是成立的，但通過其他常規方法證明又比較困難時，可以采用反證法，即從這個結論的否定面著手，通過一系列推理研究致使該結論是矛盾的，則可以證明此結論成立。

3.2.2 抽屜原理

抽屜原理是將需要討論的元素按一定特質分類，當取出足夠多的元素時，再運用抽屜原理將范圍縮小，從而推導出屬于同一類的某幾種元素，它們均同時具備某種特質，由此推導出題目的結論。運用抽屜原理時通常會出現以下幾個特點：第一、題目中所討論的元素具備任意性；第二、題目的結論至少要有一類是具備某種特質的，是一個存在性命題；第三、結論不需要確定，但需存在。

3.2.3 計數法

某些組合問題從表面上觀察并不是圖論問題，但可以結合圖論中提到的有關概念，運用圖論中有關定理和性質來解決問題

3.2.4 極端原理

極端原理是以極端元素為出發點，經過理論推理，得出結論，或是從得到結論的否定面著手，通過極端元素推理，得出此推理導致矛盾的結果，進而推導出此結論成立。

4 如何在數學競賽中合理利用圖論

4.1 擴大視野，通過案例列舉的方式，代入需要掌握的知識點

為促進學生更好的吸收知識點，所以，在教學前就要找到合適的方法。而圖論則是數學競賽中最有利的工具。數學競賽中使用圖論的方法，對參賽學生自身的能力也有一定的要求，所以，為了更充分的了解到這些知識面，就需要在教學過程中通過案例分析進行講解，從這些案例中代入知識點，提高學生學習的氛圍及興趣，增加學生自身的代入感，讓他們的精力都集中在教學中來，最終達到提高學生學習效果以及教學質量的目的。

4.2 為促進學生的執行力，可以引入軟件教學的形式

從先前數學競賽中體現出來的有關圖論的知識點觀察到，由于比賽中題目的數據相對較多，所以，如果單純依靠人工計算的方式來計算數據，這就會使出現的問題越來越復雜，因此，這就必須應用計算機技術的方式，方便高效的處理，提高這些復雜數據的解決能力，讓學生能更輕松的學習知識，同時提高學習興趣。可以引入軟件教學的方式進行解決，避免物力、人力的浪費。而在引入教學軟件時，只需要運用一些簡單、基礎、易懂的軟件就行，比如Excel表格等，就不需要額外去學難度較大的軟件，反而增加學習的困難。

4.3 重視并發掘培養學生的應用性及發散性思維

將圖論應用到數學競賽中，相比于其他的競賽來說，其是一項通訊性的競賽，具有比較開放的特點。從研究數學競賽中用圖論解決問題的結果來看，其結果多種多樣，很多參賽選手因此不清晰結果的準確性，所以會對這個方案的使用產生猶豫。在這個時候，我們應該充分了解自己，發掘出自己的應用性和發散性思維，對結果不斷探討，找到正確的結果。因為數學競賽中存在的問題較多，同時也有很多解決辦法，所以，不可能解出一個答案是可以讓所有人都滿意。不同的問題存在，就有不同解決問題的思路，在解決過程中，會遇到很多知識點，所以這就要求學生重視并培養自身的發散性以及應用性思維，促進學生更加全面的對所有的知識點進行認知和理解，然后探討出一個絕大部分人都足夠滿意的結果。

5 結語

數學競賽中的問題專業、抽象并且難度較大，所以就促使其具有一定的趣味以及教育性。在準備使用圖論時，首先要先掌握圖論的使用原理、方法以及使用過程中存在的問題以及問題的解決方法。在競賽中使用圖論能增強學生對書本上知識的理解，從而簡單方便的解決社會活動中存在的各種問題，不僅培養學生分析問題的能力，還培養他們通過分析問題，擴散思路，從而提高解決問題的能力。針對教師，用一些教育軟件以及教育案例融入到教學中，不僅可以提高教師的教學水平，還可以提高學生對知識的清晰度和掌握能力。參加一場數學競賽，通過事前的準備及學習，學生們可以學到很多書本上以及生活中常見的解決問題的方法。

【參考文獻】

[1]周文清.數學競賽中的集合問題[J].中等數學，2017（12）：8-12.

[2]郭夢夏.數學競賽中圖論問題的探究[J].時代教育，2017（23）：173.

[3]劉勇.圖論知識在數學競賽中的應用[J].數學大世界（中旬），2017（08）：37.

[4]錢培星.淺談數學競賽中的圖論問題[J].課程教育研究，2017（07）：123-124.