圖論

內容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    圖論 PDF格式下載

---