數(shù)論初步 (2)

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

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

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

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