圖論初步課件

圖論初步課件一、關(guān)于圖論ABCD哥尼茨堡城區(qū)歐拉(1736)ACBD七橋問(wèn)題的圖例1證明任何6個(gè)人中，其中總存在3個(gè)人，他們或者相互認(rèn)識(shí)或者相互不認(rèn)識(shí).例29名數(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ò)舞）.會(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ò)手.(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í)，相互比賽過(guò)，有直通航線，相互握過(guò)手等.用點(diǎn)來(lái)表示上述現(xiàn)象的“對(duì)象”，用連接兩點(diǎn)之間的“線”來(lái)表示上述現(xiàn)象中的“關(guān)系”圖n階圖同構(gòu)同構(gòu)同構(gòu)有向圖（競(jìng)賽圖）ACBD這是因?yàn)锳CBD七橋問(wèn)題的圖必是連通圖所以此圖不是哈密頓圖所以此圖不