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

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

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

每一個基本邊割集把連通圖分成恰好2個連通分支，因而導出圖的頂點集的一個分成兩組的劃分(同一個連通分支中的頂點組成一個劃分塊)。本題中，頂點集V是個5元集,正整數(shù)5分成兩個數(shù)的劃分有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

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

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

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

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

由握手定理：但因r，si(i=1,2,…,n)均為奇數(shù)，上面等式不可能成立。故不存在這樣的無向圖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是頂點數(shù),m是邊數(shù)。證：令V1,V2是G的兩個互補頂點集合,|V1|=n1,|V2|=n2

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

2023/2/5計算機學院2315、若u與v是G中僅有的兩個奇數(shù)度結點，證明u和v必是連通的。證：（反證法）設v與u不連通∴G={V1，V2}，v與u分別屬于V1，V2二個子圖∵v與u是G中僅有的二個奇數(shù)度結點∴v與u即是V1與V2中僅有的一個奇數(shù)度結點，與握手定理的推論相矛盾，故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個結點的簡單圖，其邊數(shù)與矛盾；如d(v)=k,則G是一個完全圖，與假設矛盾）2023/2/5計算機學院26∴從G中刪除該結點v所得子圖

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

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

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