數(shù)論初步 (2)

1、圖論初步,,一、關(guān)于圖論,七橋問題的圖,例1 證明任何6個人中，其中總存在3個人，他們或者相互認識或者相互不認識.,,,,,,,,,,例2 9名數(shù)學家在一次國際數(shù)學會議上相遇，已知他們?nèi)我?個人中至少有兩個可以用一種語言對話，且每個數(shù)學家至多會說3種語言，證明至少存在在3名數(shù)學家可以用同一種語言對話.,,,,,,,,,,,,,,,,,,,,,,,,,,,,例3 有4對夫婦參加一次舞會，會間某些人兩兩做舞伴跳舞（夫婦之間沒跳過

2、舞）.會后，其中一位趙先生統(tǒng)計其余每位與會者跳舞的次數(shù)，發(fā)現(xiàn)他們跳舞的次數(shù)各不相同，問：（1）趙夫人跳了幾次舞？（2）趙先生跳了幾次舞？（3）誰與誰是夫妻？,,,,,,,,,,,,,,,,,課后練： IMO評議會有34個國家參加，每個國家有領(lǐng)隊和副領(lǐng)隊兩個人參加，會前某些與會者之間握手相互問候（領(lǐng)隊與他的副手不握手）.會后，主辦國領(lǐng)隊統(tǒng)計其余每位與會者握手的次數(shù)，發(fā)現(xiàn)他們握手的次數(shù)各不相同，問：主辦國副領(lǐng)隊與多少個人握過手.(

3、IMO26),二、圖論基本知識,觀察如下一些現(xiàn)象：（1）一群人中，有些人相互認識，有些人相互不認識；（2）若干只球隊比賽，有些隊之間相互比賽過，有些隊之間沒有比賽過；（3）若干城市中，有些城市相互之間有直通航線，另一些城市相互之間無直通航線. …………………………,這些現(xiàn)象有以下特點：（1）存在一些“對象”：如人群，城市，球隊等；（2）對象之間存在某種二元“關(guān)系”：如相互認識，相互比

4、賽過，有直通航線，相互握過手等.,用點來表示上述現(xiàn)象的“對象”，用連接兩點之間的“線”來表示上述現(xiàn)象中的“關(guān)系”,,圖,n階圖,,,,,,,同構(gòu),同構(gòu),,,,,,,,,同構(gòu),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,這是因為,,,,,,,,,,,,,,,,,,,,七橋問題的圖,必是連通圖,,,,,,,所以此圖不是哈密頓圖,,,,,,,,,,,,,,,,,,,所以此圖不是哈密頓圖，無法實現(xiàn)題中想法