離散數學(第23講習題課4)

馮偉森Email：fws365@Tel:1380819227505二月2023離散數學計算機學院2023/2/5計算機學院2主要內容習題課四2023/2/5計算機學院3基本要求（第六章）掌握函數、單射、滿射和雙射的概念會正確判斷一個函數是否為單射、滿射和雙射掌握置換、循環(huán)和循環(huán)的積、復合函數、逆函數等基本概念掌握雙射和逆函數、復合函數的關系掌握集合的基數、等勢的基本概念掌握可數集、不可數集的定義了解Cantor定理掌握可數集、不可數集的基本性質2023/2/5計算機學院4第十章理解與圖的定義有關的諸多概念，以及它們之間的相互關系深刻理解握手定理及其推論的內容，并能熟練地應用它們深刻理解圖同構、簡單圖、完全圖、正則圖、子圖、補圖、二部圖等概念及其它們的性質和相互關系，并能熟練地應用它們深刻理解道路、簡單道路、基本道路與回路、圈的定義，掌握道路與回路的各種表示方法2023/2/5計算機學院5深刻理解無向圖的連通性，連通分支等概念深刻理解無向圖的點割集和邊割集、點連通度、邊連通度等概念及其之間的關系，并能熟練地求出給定的較為簡單的圖的點割集和邊割集、點連通度與邊連通度深刻理解有向圖連通性的概念及其分類，掌握判斷有向連通圖類型的方法深刻理解有向圖的鄰接矩陣、可達矩陣的基本概念2023/2/5計算機學院6熟練掌握用有向圖的鄰接矩陣及各次冪求圖中通路與回路數的方法熟練掌握用有向圖的鄰接矩陣及Warshall算法求有向圖的所有強分圖的方法了解關聯矩陣的基本概念及其基本性質2023/2/5計算機學院7例1

解：{v2,v3}是個基本點割集,而G的點割集必須含有點v2和v3,因為它們中每一個都與圖中除其自身外的各頂點鄰接.故{v2,v3}是該圖唯一的基本點割集.求出下圖G中的全部基本點割集和基本邊割集.v1v5v4v3v2aedcbfgh2023/2/5計算機學院8

每一個基本邊割集把連通圖分成恰好2個連通分支，因而導出圖的頂點集的一個分成兩組的劃分(同一個連通分支中的頂點組成一個劃分塊)。本題中，頂點集V是個5元集,正整數5分成兩個數的劃分有1+4和2+3。V的“1+4”的劃分有C15=5個。如下表所列,表中還列出了相應的邊割集:邊割集 頂點集V的劃分 {a,b} {{v1},{v2,v3,v4,v5}} {a,c,d,f} {{v2},{v1,v3,v4,v5}} {b,c,e,h} {{v3},{v1,v2,v3,v5}} {d,e,g} {{v4},{v1,v2,v3,v4}} {f,g,h} {{v5},{v1,v3,v3,v4}} 2023/2/5計算機學院9V的“2+3”的劃分有C25=10個,其中7個可以由基本邊割集導出,如下表所示:

基本邊割集 頂點集V的劃分 {b,c,d,f} {{v1,v2},{v3,v4,v5}} {a,c,e,h} {{v1,v3},{v2,v4,v5}} {a,c,e,f,g} {{v1,v3,v5},{v2,v4}} {a,c,d,g,h} {{v1,v3,v4},{v2,v5}} {b,c,d,g,h} {{v1,v2,v5},{v3,v4}} {b,c,e,f,g} {{v1,v2,v4},{v3,v5}} {d,e,f,h} {{v1,v2,v3},{v4,v5}}而V的以下3個“2+3”的劃分不能由基本邊割集導出:{{v2,v3},{v1,v4,v5}},{{v1,v4},{v2,v3,v5}},{{v1,v5},{v2,v3,v4}})。所以該圖的基本邊割集有12個。 2023/2/5計算機學院10例2證明:在一個連通圖中,任意兩條最長的基本道路有一個公共頂點。證：（反證法）v0u0vjukvpupL2023/2/5計算機學院11

設Γ1=v0v1…vp和Γ2=u0u1…up是G的兩條最長的基本道路(長為p)，且無公共頂點。因為G是連通圖.v0與u0之間有道路L.設vj是從v0出發(fā)沿L前進的最后一個和Γ1相交的頂點.而uk是道路L第一次與Γ2相交的結點。當j≥p/2(這時在基本道路Γ1上v0…vj的一段不比vj…vp的一段短)且k≥p/2時(這時在基本道路Γ2上u0…vk的一段不比uk…up的一段短)。2023/2/5計算機學院12構造一條新的路Γ′,它從v0出發(fā),沿Γ1到vj,然后沿L從vj到uk，最后沿Γ2從uk到u0，該道路是一條基本道路(點不重復.答圖中紅粗線所示),其長度≥j+1+k≥p+1>p,這與L1,L2是最長的基本道路相矛盾,所以Γ1和Γ2有公共頂點.對j,k的其他情況討論類似(分別在Γ1和Γ2上取分別被頂點vi和uk截出的兩段路徑中較長的一段,加上L上被頂點vi和uk截出的一段,構成一條比Γ1和Γ2都較長的基本道路)。2023/2/5計算機學院13例3

設圖G中有從頂點u到v的兩條不同的簡單道路,證明G中有圈。證：設P1和P2是從u到v的兩條不同的簡單通路。設w是P1和P2的公共頂點使得隨后的頂點是不同的,再設w′是繼w后第一個P1和P2的公共頂點(注意到u和v是P1和P2上的公共頂點,這樣的頂點w是存在的,否則P1和P2是相同的;這樣的頂點w′也是存在的,因為繼w后P1和P2有公共頂點v)。uww′vP1P22023/2/5計算機學院14

那么在w和w′之間P1和P2的子通路除了w和w′之外沒有公共頂點,因此這兩條子通路構成一個圈(頂點不重復的回路)。2023/2/5計算機學院15例4

證明:任意一場聚會,至少有兩個人與相同數目的人握過手。證：即證明非平凡的簡單無向圖必有兩個頂點的度相等。設簡單無向圖G有n個結點，則每個結點的度數最多為n-1，而每個結點都不可能為孤立結點，所以，任何結點的度均大于等于1,小于等于n?1,由鴿巢原理知,這樣的n個數中至少有兩個是相同的。所以必有兩個頂點的度相等。2023/2/5計算機學院16例5

證明空間中不可能存在有奇數個面且每個面都有奇數條棱的多面體。證：（反證法）若存在某個具有奇數個面,且每個面均有奇數條棱的多面體V。不妨設V有r(r為奇數)個面,設為R1，R2，…,Rr，s1，s2，…，sr

分別為它們的棱數，均為奇數。作無向圖G如下：在V的每個面中放一個頂點vi，i=1，2，…，r。且兩個面Ri與Rj

有公共棱就連邊。若存在這樣的無向圖G，則d(vi)均為奇數si。2023/2/5計算機學院17

由握手定理：但因r，si(i=1,2,…,n)均為奇數，上面等式不可能成立。故不存在這樣的無向圖G，從而也不存在滿足要求的多面體。2023/2/5計算機學院18習題講解習題六10、證：

2023/2/5計算機學院1915、證：2023/2/5計算機學院20習題十1、解：2023/2/5計算機學院214、證：2023/2/5計算機學院226、證明簡單二部圖G滿足,其中

n是頂點數,m是邊數。證：令V1,V2是G的兩個互補頂點集合,|V1|=n1,|V2|=n2

G的邊數m小于等于完全二部圖的邊數n1n2，而

2023/2/5計算機學院2315、若u與v是G中僅有的兩個奇數度結點，證明u和v必是連通的。證：（反證法）設v與u不連通∴G={V1，V2}，v與u分別屬于V1，V2二個子圖∵v與u是G中僅有的二個奇數度結點∴v與u即是V1與V2中僅有的一個奇數度結點，與握手定理的推論相矛盾，故v與u必連通。2023/2/5計算機學院2417、設(n,m)簡單圖G滿足

,證明G必是連通圖。構造一個

的非連通簡單圖。證：（歸納法，對n進行歸納）

n=2時,∵m>0∴二個結點至少有一條邊，即G是連通圖2023/2/5計算機學院25設n=k時，結論成立,即時，G是連通圖證n=k+1時，結論成立，即時，G是連通圖（用反證法）如果G是非連通圖，必存在一個結點v，使1≤d(v)<k(否則，如d(v)=0，則G-{v}是一個有k個結點的簡單圖，其邊數與矛盾；如d(v)=k,則G是一個完全圖，與假設矛盾）2023/2/5計算機學院26∴從G中刪除該結點v所得子圖

G′=G-v=（m′,k)其邊數

由歸納假設，G′=G-v的結點數為k，所以G′是連通圖，∵G=G′+{v}，而v至少有一條邊，∴G連通故由歸納法，結論成立2023/2/5計算機學院27vw2023/2/5計算機學院28證：（反證法）設結論不成立，即存在

因為G是連通的，所以G-v的每個分支都至少有一個點與v相鄰接，而且存在一個分支，其與v相鄰接的點w只有一條邊與v相連（因為如每個分支中有二個以上