圖論

內(nèi)容概要

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

作者簡介

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

書籍目錄

1 圖的定義
2 頂點的度
3 托蘭定理
4 樹
5 歐拉問題
6 哈密頓問題
7 平面圖
8 拉姆賽問題
9 競賽圖
習(xí)題解答

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    圖論 PDF格式下載

---