离散数学教程与范例.ppt

有101个人参加乒乓球淘汰赛（每一轮比赛
在参加人数是奇数时，让一人轮空），共需
进行多少场比赛方可决出优胜者（一场比赛
指两人的一次对垒）
解（一）解（二）土耳其商人和帽子的故事聪明的囚徒哥尼斯堡城位于普雷格尔河畔，河中有两个岛，七座桥使两个河心岛及两岸彼此相连。十八世纪的城中居民热衷于这样一个问题：游人从四块陆地中的任何一地出发，能否找到一条路线，通过每桥一次且仅一次，最后返回原地？欧拉对七桥问题的解
1736年，著名数学家欧拉研究了七桥问题，他将这个问题用结点和弧边组成的图来表示，问题归结为从图中任一结点出发，经过每边一次且仅一次的回路是否存在？他找到了存在这样一条回路的充分必要条件，并由此判断七桥问题无解而结束了哥尼斯堡城民的烦恼。同构發現者這是在西元1852年，由畢業於英國倫敦大學的弗朗西斯(FrancisGuthrie)發現的。當時他正在畫英國各郡的地圖，而發現了這個有趣的現象。格里斯覺得這其中一定有什麼奧妙，於是便寫信告訴他那數學很好的哥哥佛德雷克(FrederickGuthrie)。佛德雷克百思不得其解，又求教於他的老師----數學家摩根(Morgan)。摩根也無法確定這個說法對不對，於是又寫信給他的好朋友哈彌爾頓(Hamilton)，希望他要嘛就證明出這個說法是正確的，要不就舉一個反例，建構出一張需要5種顏色的地圖來。大師級的哈彌爾頓耗了13年心血，仍一籌莫展，抱憾而逝。公開徵答1878年，英國數學家Cayley將上述問題曝光取名為「四色猜想」(因為還不確定對不對，所以說是猜想)，公開徵求解答。問題一傳出後，馬上就有了回應。1879年和1880年，Kempe和Tait分別發表論文證明了四色問題。轟動一時的熱度終於平息。不料事隔11年後，一個名叫Heawood的年輕人指出了Kempe證明中的錯誤，並利用Kempe的方法證明出若用5種顏色就保證一定能區分出地圖上相鄰的區域。雖然四色問題未被破解，但是至此算是邁出了一大步。而另一方面，Tait的論文亦被陸陸續續發現多處錯誤，甚至最後一個錯誤是一直到1946年才被發現的。從這裡我們可看出這些人的研究精神是多麼可敬，被發現錯誤的東西並未被棄之如敝屣般丟在一旁，仍舊不斷有人去研究它，甚至是在事隔半個多世紀之後。當然這兩篇錯誤的論文在數學上仍然有其貢獻，不可小覷。解題花絮一番風風雨雨下來，四色問題更加受到矚目了。由於Heawood的「五色定理」的證明並不難，因此就有許多人也小看了「四色問題」的難度。最有趣的是以下這個例子。1902年秋天，閔可夫斯基教授(HermannMinkowsky，1864-1909，愛因斯坦的數學導師)在上拓樸學的課堂上就當著學生面前說：「四色問題之所以尚未被解決是因為世界上第一流的數學家都還沒空去研究它。」而且興之所至，當場就證了起來；但是寫了好幾個黑板，卻依舊未能得證。接下來幾個星期的課，他繼續證下去，課一堂一堂地過去了，他如身陷泥沼，仍舊無法證明出來。他終於投降，承認自己也無能為力了。就在這個時候，天空正好霹靂一聲巨響，他感嘆地說：「上帝在責備我的狂妄！」然後就繼續上他的拓樸課了。离散数学是现代数学的一个重要分支，是计算机科学与技术的基础理论的核心课程之一。离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、机器定理证明等课程息息相关。
基本内容包括数理逻辑、集合论、代数系统、图论等几大部分。离散数学离散数学左孝凌等上海科技文献出版社
离散数学耿素云等清华大学出版社
离散数学方世昌主编西安电子科大出版社
DiscreteMathematicsStructures
BemardKolman
RobertC.Busby
SharonRoss
Prentice-HallInternational,Inc.1997.11
(英文原版影印)清华大学出版社离散数学是培养抽象思维和逻辑推理的学科，因此要重视基本概念的学习，一定要认真研读教材，特别要从实例和习题中搞清众多概念的涵义。
适当多做习题，至少要按时完成作业，强迫自己通过特定条件下运用所学的概念和理论，才能真正掌握和理解它们，提高分析和解决问题的能力。
与教材配套的习题解答是离散数学的初学者必备的参考书，钻研习题解答，从中领会典型问题的解题方法。不会求解的作业题，可以看习题解答，但务求读懂，决不可一抄了事，养成依赖习惯，白白浪费宝贵的时光！手机（关机）
作业（及时）
考试（改革）2025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025/3/72025