|
本課程概況 《集合論與圖論》是為計算機專業本科開設的專業基礎課。它是計算機科學中基礎理論的核心課程，是學習專業理論不可少的數學工具。它是以研究離散量的結構和相互間的關係為主要目標，其研究對像一般是有限個或可數個元素，..集合論主要內容有集合及其運算、映射、關係、無窮集合及其運算；圖論主要內容有圖、樹和割集、連通度和匹配、平面圖和圖的著色、有向圖。課程的基本要求包括掌握集合論、圖論的基本概念、原理等基本知識，學會運用基本概念進行推理並初步應用到計算機科學領域解決實際問題，強調建立數學模型。
集合論- 概述
數學的一個基本的分支學科，研究對象是一般集合。集合論在數學中佔有一個獨特的地位，它的基本概念已滲透到數學的所有領域。[1] 集合論或集論是研究集合（由一堆抽像物件構成的整體）的數學理論，包含了集合、元素和成員關係等最基本的數學概念。在大多數現代數學的公式化中，集合論提供了要如何描述數學物件的語言。集合論和邏輯與一階邏輯共同構成了數學的公理化基礎，以未定義的「集合」與「集合成員」等術語來形式化地建構數學物件。
集合論是從一個物件o和集合A之間的二元關係開始：若o是A的元素，可表示為o ∈ A。由於集合也是一個物件，因此上述關係也可以用在集合和集合的關係。
另外一種二個集合之間的關係，稱為包含關係。若集合A中的所有元素都是集合B中的元素，則稱集合A為B的子集，符號為A ⊆ B。例如{1,2} 是{1,2,3} 的子集，但{1,4} 就不是{1,2,3} 的子集。依照定義，任一個集合也是本身的子集，不考慮本身的子集稱為真子集。集合A為集合B的真子集當且僅當集合A為集合B的子集，且集合B不是集合A的子集。
數的算術中有許多一元及二元運算，集合論也有許多針對集合的一元及二元運算：
集合A和B的並集，符號為A ∪ B，是在至少在集合A或B中出現的元素，集合{1,2,3} 和集合{2, 3, 4} 的聯集為集合{1, 2, 3, 4} 。
集合A和B的交集，符號為A ∩ B，是同時在集合A及B中出現的元素，集合{1,2,3} 和集合{2, 3, 4} 的交集為集合{2, 3} 。
集合U和A的相對差集，符號為U \ A，是在集合U中,但不在集合A中的所有元素，相對差集{1,2,3} \ {2,3,4} 為{1} ，而相對差集{2,3,4} \ {1,2,3} 為{4} 。當集合A是集合U的子集時，相對差集U \ A也稱為集合A在集合U中的補集。若是研究文氏圖，集合U為全集時，且可以借由上下文找到全集定義時，會使用A來代替U \ A。
集合A和B的對稱差，符號為A △ B或A⊕B，是指只在集合A及B中的其中一個出現，沒有在其交集中出現的元素。例如集合{1,2,3} 和{2,3,4} 的對稱差為{1,4} ，也是其並集和交集的相對差集(A ∪ B) \ (A ∩ B)，或是二個相對差集的聯集(A \ B) ∪ (B \ A)。
集合A和B的笛卡兒積，符號為A × B，是一個由所有可能的有序對(a,b)形成的集合，其中第一個物件是A的成員，第二個物件是B的成員。{1, 2}和{red, white}的笛卡兒積為{(1, red), (1, white), (2, red), (2, white)}。
集合A的冪集是指是以A的全部子集為元素的集合，例如集合{1, 2} 的冪集為{ {}, {1}, {2}, {1,2} } 。
一些重要的基本集合包括空集（唯一沒有元素的集合），整數集合及實數集合。
圖論 - 概述
圖論〔Graph Theory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係。一些由結點及邊構成的圖稱為線圖。在線圖中，結點的位置分佈和邊的長短曲直都可以任意描畫，這並不改變實際問題的性質。我們關心的是它有多少個結點，在哪些結點間有邊相連，以及整個線圖具有的某些特性。
圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符號上的混淆，我們總是默認V∩B=O。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連接這兩個小圓圈，如何繪製這些小圓圈和連線時無關緊要的，重要的是要正確體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。
圖論本身是應用數學的一部份，因此，歷史上圖論曾經被好多位數學家各自獨立地建立過。關於圖論的文字記載最早出現在歐拉1736年的論著中，他所考慮的原始問題有很強的實際背景。
在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。這一問題最早於1852年由Francis Guthrie提出，最早的文字記載則現於德摩根於同一年寫給哈密頓的信上。包括凱萊、肯普等在內的許多人都曾給出過錯誤的證明。泰特(Tait)、希伍德(Heawood)、拉姆齊和哈德維格(Hadwiger)對此問題的研究與推廣引發了對嵌入具有不同虧格的曲面的圖的著色問題的研究。一百多年後，四色問題仍未解決。1969年，Heinrich Heesch發表了一個用計算機解決此問題的方法。1976年，阿佩爾(Appel)和哈肯(Haken)借助計算機給出了一個證明，此方法按某些性質將所有地圖分為1936類並利用計算機，運行了1200個小時，驗正了它們可以用四種顏色染色。四色定理是第一個主要由電腦證明的理論，這一證明並不被所有的數學家接受，因為採用的方法不能由人工直接驗證。最終，人們必須對電腦編譯的正確性以及運行這一程序的硬件設備充分信任。主要是因為此證明缺乏數學應有的規範，以至於有人這樣評論「一個好的數學證明應當像一首詩——而這純粹是一本電話簿！」
雖然四色定理證明了任何地圖可以只用四個顏色著色，但是這個結論對於現實上的應用卻相當有限。現實中的地圖常會出現飛地，即兩個不連通的區域屬於同一個國家的情況（例如美國的阿拉斯加州），而製作地圖時我們仍會要求這兩個區域被塗上同樣的顏色，在這種情況下，四個顏色將會是不夠用的。
20世紀80-90年代曾邦哲的綜合系統論（結構論）觀將「四色猜想」命題轉換等價為「互鄰面最大的多面體是四面體」。每個地圖可以導出一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連接。所以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數拓撲圖論等分支的發展起到推動作用。
（下圖是在上下對折再左右對折以後形成一個輪胎形狀，有7個區域兩兩相連，就是說在一個環面上作圖，需要7種顏色，外國數學家構造林格證明：Np=[(7+√1+48p)/2]，p=1，N1=7。
圖論的廣泛應用，促進了它自身的發展。20世紀40-60年代，擬陣理論、超圖理論、極圖理論，以及代數圖論、拓撲圖論等都有很大的發展。
【課程重點】
第一章 集合及其運算
第二章映射
第三章 關係
第四章 無窮集合及其基數
第五章 圖的基本概念
第六章 樹和割集
第七章 連通度
第八章 平面圖和圖的著色
第九章 有向圖
集合論第1章
集合論第2章
集合論第3章
|
全學時授課 (共 48 講) 每講約 40~50 分鐘 
SR_7543