數(shù)論初步 (2)

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

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

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

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