圖論

內(nèi)容概要

　　1736年.數(shù)學(xué)家歐拉由解哥尼斯堡七橋問(wèn)題而創(chuàng)立了圖論這門(mén)學(xué)科.到現(xiàn)在已經(jīng)二百多年了。圖論是離散數(shù)學(xué)的骨干內(nèi)容。而離散數(shù)學(xué)則是計(jì)算機(jī)科學(xué)技術(shù)與網(wǎng)絡(luò)信息科學(xué)的理論基礎(chǔ)?！秷D論（第2版）》通過(guò)一些有趣的數(shù)學(xué)問(wèn)題和數(shù)學(xué)游戲，向讀者比較通俗地介紹了一些圖論的基本知識(shí)和圖論中常用的初等方法，以擴(kuò)大中學(xué)生的知識(shí)面，提高分析問(wèn)題和解決問(wèn)題的能力。

作者簡(jiǎn)介

熊斌第46屆、49屆、51屆、52屆和53屆國(guó)際數(shù)學(xué)奧林匹克中國(guó)隊(duì)領(lǐng)隊(duì)、主教練，華東師范大學(xué)數(shù)學(xué)系教授，博士生導(dǎo)師，華東師范大學(xué)國(guó)際數(shù)學(xué)奧林匹克研究中心主任。多次參與中國(guó)數(shù)學(xué)奧林匹克、全國(guó)高中數(shù)學(xué)聯(lián)賽、全國(guó)初中數(shù)學(xué)競(jìng)賽、西部數(shù)學(xué)奧林匹克、女子數(shù)學(xué)奧林匹克、國(guó)際城市青少年數(shù)學(xué)邀請(qǐng)賽等競(jìng)賽的命題工作。在國(guó)內(nèi)外發(fā)表了100余篇論文，主編和編著的著作150多本。

書(shū)籍目錄

1 圖的定義
2 頂點(diǎn)的度
3 托蘭定理
4 樹(shù)
5 歐拉問(wèn)題
6 哈密頓問(wèn)題
7 平面圖
8 拉姆賽問(wèn)題
9 競(jìng)賽圖
習(xí)題解答

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   當(dāng)圖G是完全圖時(shí)，每個(gè)頂點(diǎn)的度都是99，所以有100個(gè)度為99的頂點(diǎn)。 當(dāng)圖G是非完全圖時(shí)，G中必有兩個(gè)不相鄰的頂點(diǎn)u和v。顯然d（u）≤98，d（v）≤98。因此G中度為99的點(diǎn)的個(gè)數(shù)l≤98。 如果G中除u和v外另有兩個(gè)頂點(diǎn)x，y不相鄰，則“u”，v，x和y中不存在和其他三個(gè)頂點(diǎn)都相鄰的頂點(diǎn)，與題意矛盾（與G的性質(zhì)矛盾）。因此G中除“u，v外任意兩個(gè)頂點(diǎn)相鄰。這說(shuō)明對(duì)G中除u，v外的任意點(diǎn)x，均有d（x）≥97。 如果G中除u、v外的任何x都和u，v相鄰，則d（x）=99。此時(shí)G中度為99的頂點(diǎn)個(gè)數(shù)為98。 設(shè)G中除u、v外有個(gè)頂點(diǎn)x和u、v不都相鄰，則有G的性質(zhì)知，G中除u，v，x外的任意頂點(diǎn)y和u、v、x都相鄰。因此d（u）≤98，d（v）≤98，d（x）≤98，d（y）=99。所以G中度為99的頂點(diǎn)個(gè)數(shù)為97。 這表明含100個(gè)頂點(diǎn)的簡(jiǎn)單圖G中，如果任意四個(gè)頂點(diǎn)中必有一個(gè)頂點(diǎn)和其他三個(gè)頂點(diǎn)都相鄰，那么G中至少有97個(gè)度為99的頂點(diǎn)。 回到原問(wèn)題，即得：該團(tuán)體中認(rèn)識(shí)其他所有人的成員最少是97個(gè)。 注例題中的成員數(shù)100改為任意的n，其他條件不變，則結(jié)論為該團(tuán)體至少有n-3人認(rèn)識(shí)其他所有人。

編輯推薦

《數(shù)學(xué)奧林匹克小叢書(shū)?高中卷12:圖論(第2版)》由華南師范大學(xué)出版社出版。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    圖論 PDF格式下載

---