離散數(shù)學(xué)(第23講習(xí)題課4)

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

解：{v2,v3}是個(gè)基本點(diǎn)割集,而G的點(diǎn)割集必須含有點(diǎn)v2和v3,因?yàn)樗鼈冎忻恳粋€(gè)都與圖中除其自身外的各頂點(diǎn)鄰接.故{v2,v3}是該圖唯一的基本點(diǎn)割集.求出下圖G中的全部基本點(diǎn)割集和基本邊割集.v1v5v4v3v2aedcbfgh2023/2/5計(jì)算機(jī)學(xué)院8

每一個(gè)基本邊割集把連通圖分成恰好2個(gè)連通分支，因而導(dǎo)出圖的頂點(diǎn)集的一個(gè)分成兩組的劃分(同一個(gè)連通分支中的頂點(diǎn)組成一個(gè)劃分塊)。本題中，頂點(diǎn)集V是個(gè)5元集,正整數(shù)5分成兩個(gè)數(shù)的劃分有1+4和2+3。V的“1+4”的劃分有C15=5個(gè)。如下表所列,表中還列出了相應(yīng)的邊割集:邊割集 頂點(diǎn)集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計(jì)算機(jī)學(xué)院9V的“2+3”的劃分有C25=10個(gè),其中7個(gè)可以由基本邊割集導(dǎo)出,如下表所示:

基本邊割集 頂點(diǎn)集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個(gè)“2+3”的劃分不能由基本邊割集導(dǎo)出:{{v2,v3},{v1,v4,v5}},{{v1,v4},{v2,v3,v5}},{{v1,v5},{v2,v3,v4}})。所以該圖的基本邊割集有12個(gè)。 2023/2/5計(jì)算機(jī)學(xué)院10例2證明:在一個(gè)連通圖中,任意兩條最長(zhǎng)的基本道路有一個(gè)公共頂點(diǎn)。證：（反證法）v0u0vjukvpupL2023/2/5計(jì)算機(jī)學(xué)院11

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

設(shè)圖G中有從頂點(diǎn)u到v的兩條不同的簡(jiǎn)單道路,證明G中有圈。證：設(shè)P1和P2是從u到v的兩條不同的簡(jiǎn)單通路。設(shè)w是P1和P2的公共頂點(diǎn)使得隨后的頂點(diǎn)是不同的,再設(shè)w′是繼w后第一個(gè)P1和P2的公共頂點(diǎn)(注意到u和v是P1和P2上的公共頂點(diǎn),這樣的頂點(diǎn)w是存在的,否則P1和P2是相同的;這樣的頂點(diǎn)w′也是存在的,因?yàn)槔^w后P1和P2有公共頂點(diǎn)v)。uww′vP1P22023/2/5計(jì)算機(jī)學(xué)院14

那么在w和w′之間P1和P2的子通路除了w和w′之外沒有公共頂點(diǎn),因此這兩條子通路構(gòu)成一個(gè)圈(頂點(diǎn)不重復(fù)的回路)。2023/2/5計(jì)算機(jī)學(xué)院15例4

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

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

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

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

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

2023/2/5計(jì)算機(jī)學(xué)院1915、證：2023/2/5計(jì)算機(jī)學(xué)院20習(xí)題十1、解：2023/2/5計(jì)算機(jī)學(xué)院214、證：2023/2/5計(jì)算機(jī)學(xué)院226、證明簡(jiǎn)單二部圖G滿足,其中

n是頂點(diǎn)數(shù),m是邊數(shù)。證：令V1,V2是G的兩個(gè)互補(bǔ)頂點(diǎn)集合,|V1|=n1,|V2|=n2

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

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

,證明G必是連通圖。構(gòu)造一個(gè)

的非連通簡(jiǎn)單圖。證：（歸納法，對(duì)n進(jìn)行歸納）

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

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

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

因?yàn)镚是連通的，所以G-v的每個(gè)分支都至少有一個(gè)點(diǎn)與v相鄰接，而且存在一個(gè)分支，其與v相鄰接的點(diǎn)w只有一條邊與v相連（因?yàn)槿缑總€(gè)分支中有二個(gè)以上