專必計(jì)算機(jī)科學(xué)導(dǎo)論復(fù)習(xí)第12章離散結(jié)構(gòu)

1、第12章離散結(jié)構(gòu)學(xué)習(xí)目標(biāo) 了解離散結(jié)構(gòu)的研究對(duì)象及主要內(nèi)容、代數(shù)結(jié)構(gòu)、離散概率。 掌握數(shù)理邏輯與簡(jiǎn)單推理、集合論基礎(chǔ)知識(shí)、圖論基本知識(shí)。2計(jì)算機(jī)科學(xué)導(dǎo)論12.1離散結(jié)構(gòu)的研究對(duì)象及主要內(nèi)容 離散結(jié)構(gòu)(Discrete Structure)是現(xiàn)代數(shù)學(xué)的一個(gè)重要學(xué)科，它所涉及的概念、方法和理論，被大量應(yīng)用于計(jì)算機(jī)科學(xué)與技術(shù)的研究。 本章將系統(tǒng)傳統(tǒng)離散數(shù)學(xué)包含的數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論等4部分的基本內(nèi)容，使讀者初步了解離散結(jié)構(gòu)的基本知識(shí)。3計(jì)算機(jī)科學(xué)導(dǎo)論12.1.1離散結(jié)構(gòu)的研究對(duì)象 離散結(jié)構(gòu)的研究對(duì)象是離散量的結(jié)構(gòu)和相互關(guān)系，以及離散系統(tǒng)結(jié)構(gòu)的數(shù)學(xué)模型以及建模方法。4計(jì)算機(jī)科學(xué)導(dǎo)論12.1

2、.2離散結(jié)構(gòu)研究的主要內(nèi)容 離散結(jié)構(gòu)研究的內(nèi)容主要有傳統(tǒng)離散數(shù)學(xué)包含的數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu) 和圖論等4個(gè)部分，另外還包括計(jì)算機(jī) 應(yīng)用對(duì)象的離散結(jié)構(gòu)的研究，離散概率、運(yùn)籌學(xué)、數(shù)值計(jì)算、數(shù)學(xué)建模與模擬等。5計(jì)算機(jī)科學(xué)導(dǎo)論12.212.2.1數(shù)理邏輯命題邏輯u命題在數(shù)理邏輯中，稱能夠分辨真假、但不能同時(shí)既的陳述句為命題 。u原子命題在命題中，有些命題是簡(jiǎn)單的陳述句，并且它們不能夠被分成更為簡(jiǎn)單的陳述語句，這樣題稱為簡(jiǎn)單命題，或者原子命題。6計(jì)算機(jī)科學(xué)導(dǎo)論12.2.1命題邏輯u 復(fù)合命題一個(gè)簡(jiǎn)單命題再加上了一個(gè)表示合命題。的連接詞形成的復(fù)簡(jiǎn)單命題與復(fù)合命題都可以用簡(jiǎn)單的英文字母來表示。例 用Q表

3、示命題：8是奇數(shù)！用P表示命題：不是學(xué)生。復(fù)合命題的連接詞連接詞，記作“” 合取連接詞，也稱“與”，記作“” 或取連接詞，也稱“或”，記作“” 蘊(yùn)涵連接詞，也稱“條件”，記作“” 等價(jià)連接詞，也稱“雙條件”，記作“ ”7計(jì)算機(jī)科學(xué)導(dǎo)論12.2.1命題邏輯u 2命題公式由命題常元、命題變?cè)c各種邏輯連接詞組合形成的更為復(fù)雜題，稱為命題公式，又稱為合式公式。u 3等值演算 (1)重言式如果對(duì)命題公式A中命題變?cè)囊磺兄概?，A的真值均為真，則稱命題公式A為重言式，重言式又稱 (2)等價(jià)式設(shè)A,B為兩個(gè)命題公式，若等價(jià)式A B是重言式，則稱A邏輯等價(jià)于B，或A與B是等值的，記作AB。A B式。不是命題

4、公式。8計(jì)算機(jī)科學(xué)導(dǎo)論12.2.1u 4命題推理推理是從前提出發(fā)推出結(jié)論的思維過程，命題邏輯前提是已知題公式，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出題公式。推理常用的方法: 真值表法 等價(jià)證明法 構(gòu)造證明法9計(jì)算機(jī)科學(xué)導(dǎo)論12.2.1命題邏輯例 證明PQ和 Q的結(jié)論是P。證明：只需證明(PQ) 真值表法QP是重言式。按真值表的構(gòu)造步驟，構(gòu)造真值表如下：PQPQQP00010101100110111111100110計(jì)算機(jī)科學(xué)導(dǎo)論12.2.1命題邏輯例 證明PQ和 Q的結(jié)論是P。證明：只需證明(PQ)QP是重言式。 等價(jià)證明法QP (P Q) Q Q)P(PQ)(P Q)PPQ PTQT11計(jì)算機(jī)科學(xué)

5、導(dǎo)論12.2.1例證明：pr, qs, pq證明：命題邏輯 rs 。構(gòu)造證明法1) pr前提1) 等價(jià)置換2) 等價(jià)置換3) 等價(jià)置換前提5) 等價(jià)置換6) 等價(jià)置換4)7)假言 前提8)9)假言10) 等價(jià)置換2) pr3) r p4) r p5) pq6) p q 7) p q 8) r q9) qs10) r s11) rs12計(jì)算機(jī)科學(xué)導(dǎo)論12.2.2 謂詞邏輯u 對(duì)簡(jiǎn)單命題做進(jìn)一步的分解，分析命題內(nèi)部的邏輯結(jié)構(gòu)和命題間的內(nèi)在，它是命題邏輯的擴(kuò)充和發(fā)展。 1.詞原子命題中所描述的對(duì)象，是可以，可以是具體的，也可以是抽象的。 2.謂詞存在的客體詞的性質(zhì)或詞之間關(guān)系的詞。 3.量詞表示常變

6、元之間數(shù)量關(guān)系的詞稱為量詞。13計(jì)算機(jī)科學(xué)導(dǎo)論12.2.2 謂詞邏輯例 將以下命題用謂詞邏輯符號(hào)化。(1)(2)(3)所有的自然數(shù)都是大于零的。沒有不犯錯(cuò)誤的人。這個(gè)班有些學(xué)生請(qǐng)假了。解：(1) 設(shè)A(x)：x是自然數(shù)；B(x)：x大于零。則原命題符號(hào)化為：x(A(x) B(x)。(2) 設(shè)A(x)：x是人；B(x)：x犯錯(cuò)誤。則原命題符號(hào)化為：x(A(x) B(x)。(3) 設(shè)A(x)：x是這個(gè)班的學(xué)生；B(x)：x請(qǐng)假了。則原命題符號(hào)化為：x(A(x)B(x)。14計(jì)算機(jī)科學(xué)導(dǎo)論12.2.2 謂詞邏輯u 4謂詞推理 (1) 全稱量詞消去規(guī)則。如果謂詞公式xA(x)為真， 則可推出A(c)

7、為真，即xA(x) A(c) 式中，c是域中任意一個(gè)確定的。 (2) 存在量詞消去規(guī)則。如果謂詞公式xA(x)為真， 則可推出A(c) 為真，即xA(x) A(c) 式中，c是域中滿足條件A的常元。15計(jì)算機(jī)科學(xué)導(dǎo)論12.2.2 謂詞邏輯(3) 全稱量詞引入規(guī)則。如果謂詞公式A(x)中的變?cè)獂無論取論域中的任何值，A(x)自由都為真，則可推出xA(x)為真，即A(x) xA(x) 式中，x是域中任意一個(gè)。(4) 存在量詞引入規(guī)則。如果謂詞公式A(c)為真，則可推出xA(x) 為真，即A(c)xA(x) 式中，c是域中滿足條件A的常元。16計(jì)算機(jī)科學(xué)導(dǎo)論12.3集合論12.3.1集合的基本概念與

8、運(yùn)算對(duì)簡(jiǎn)單命題做進(jìn)一步的分解，分析命題內(nèi)部的邏輯結(jié)構(gòu)和命題間的內(nèi)在，它是命題邏輯的擴(kuò)充和發(fā)展。u1.集合的概念與表示事物匯集在一起組成的一個(gè)整體叫做集合，而這些事物就可以稱為這個(gè)集合的元素或者成員。集合通常用大寫的英文字母來標(biāo)記。表示一個(gè)集合的方法：A1,2,3,n,：Bx|x是大于等于8的正整數(shù)列舉法描述法17計(jì)算機(jī)科學(xué)導(dǎo)論12.3.1u 2.集合間關(guān)系 設(shè)A ，B是集合，如果B中的每個(gè)元素都是A中的元素，則稱B是A的子集合，簡(jiǎn)稱子集。這時(shí)也稱B被A包含，或A包含B。 設(shè)A，B為集合，如果A B且B A，則稱A與B相等，記作AB 。 設(shè)A，B為集合，如果BA且BA，則稱B是A的真子集。記作B

9、 A。 不含任何元素的集合叫做空集，記作。集合的基本概念與運(yùn)算 給定集合A，由集合A的集為元素組成的集合，稱為集合A的冪集，記作P(A) 。 在一個(gè)具體問題中，如果所涉及的集合都是某個(gè)集合 的子集，則稱這個(gè)集合為全集，記作E(或U)。18計(jì)算機(jī)科學(xué)導(dǎo)論12.3.1u 3.集合運(yùn)算 (1) 定義：設(shè)A與B為集合，A與B的并運(yùn)算、交運(yùn)算、差運(yùn)算 - ，分別定義為，AB=x|(x A) (x B)AB=x|(x A) (x B)A - B =x|(x A) (x B) (2) 定義：設(shè)E為全集，A E，則A的補(bǔ)運(yùn)算，記作，定義為，AE -AxxExA 或 AxxA (3) 定義：設(shè)A與B為集合，A與

10、B的對(duì)稱差，記作，定義為集合的基本概念與運(yùn)算AB(AB)(AB )19計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2u 1.笛卡兒積 (1) 序偶由兩個(gè)元素x和y(關(guān)系與函數(shù)x =y)按一定的順序排列成的二元組叫做一個(gè)有序?qū)?也稱序偶)，記作，其中x是它的第一元素，y是它的第二元素。u 有序?qū)Φ奶攸c(diǎn)： 當(dāng)x y時(shí)，。 兩個(gè)有序?qū)ο嗟?，?的充分必要條件是xu且yv。20計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù) (2)笛卡兒積設(shè)A，B為集合，用A中元素作為第一元素，B中元素作為第二元素，有序?qū)?，所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積，記作AB。符號(hào)化表示為AB(x,y)|xAyB例 有兩個(gè)集合Aa,b，B0,1

11、,2，則AB,BA,21計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù)u 2.二元關(guān)系(1) 二元關(guān)系定義如果一個(gè)集合為空集或者它的元素都是有序?qū)?，則稱這個(gè)集合是一個(gè)二元關(guān)系，一般記作R對(duì)于二元關(guān)系R，如果有序?qū)，則記作x R y設(shè)A,B為集合，AB的任何子集所定義的二元關(guān)系稱作從A到B的二元關(guān)系，特別當(dāng)AB時(shí)，則叫做A上的二元關(guān)系22計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2 關(guān)系與函數(shù)u 3種特殊的關(guān)系： 其中之一就是空集，稱做空關(guān)系。 另外兩種就是全域關(guān)系EA和恒等關(guān)系IA。 對(duì)任何集合A，EAxAyAAA IAxA23計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2u (2) 關(guān)系的表示 通常用關(guān)系圖來表示一個(gè)關(guān)系。關(guān)系與函數(shù)例A

12、=1,2,3,4，R=,，可以畫出如下的關(guān)系圖。24計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù)u (3) 關(guān)系的基本運(yùn)算Dom(R)x $y(R)Ran(R)y | $x(R) F的逆記作：|F。 F與G的左復(fù)合記作GF ，GF $z(GF) F與G的右復(fù)合記作F G，F(xiàn)G $z(FG)25計(jì)算機(jī)科學(xué)導(dǎo)論u(4) 關(guān)系的性質(zhì)自反性若對(duì)于任意x屬于集合A，都有x A R ，那么，就說R在A 上是自反的。反自反性若對(duì)于任意x屬于集合A，都不存在x A R ，那么，就說R在A上是反自反的。對(duì)稱性若對(duì)于任意x,y屬于集合A，都有x, y A R R，那么，就稱R為A上的對(duì)稱關(guān)系。稱性若對(duì)于任意x,y屬于集合

13、A，都不存在 R R，那么，就稱R為A上的稱關(guān)系。例如A上的全域關(guān)系，恒等關(guān)系，空關(guān)系都是A上的對(duì)稱關(guān)系。而恒等關(guān)系和空關(guān)系也是A上傳遞性稱關(guān)系。若對(duì)任意的x,y,z都屬于集合A，假如都存在 x, y, z A R R R，那么，就稱R為A上的傳遞關(guān)系。26計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù)u (5) 兩類重要的二元關(guān)系 等價(jià)關(guān)系設(shè)R為非空集合A上的二元關(guān)系，若R具有自反性、對(duì)稱性和傳遞性，則稱R為A上的等價(jià)關(guān)系。利用等價(jià)以對(duì)一些對(duì)象進(jìn)行分類。例如，集合上的恒等關(guān)系即是等價(jià)關(guān)系。 偏序關(guān)系設(shè)R為非空集合A上的二元關(guān)系，若R具有自反性、 稱性和傳遞性，則稱R為A上的偏序關(guān)系，偏序關(guān)系可以記為。

14、集合A和A上的偏序關(guān)系R一起叫做偏序集，記為(A,)，如果有(a,b)R，可以表示為ab 。根據(jù)偏序以畫出關(guān)系圖，通常稱為。27計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù)例 已知為偏序集，集合A=a,b, c,d,e,f，關(guān)系=(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，畫出關(guān)系的。解：按照偏序集的規(guī)則，可以得到如下28計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù)u 4.函數(shù)函數(shù)(Functions)也稱(Mapping)。函數(shù)也是一種二元關(guān)系，與普通的二元關(guān)系相比，函數(shù)可以看作是一種特殊的二元關(guān)系。 (1) 函數(shù)的定義設(shè)F為二元關(guān)系，若對(duì)于任意的x，都存在惟一的讓

15、xFy成立，則稱F為函數(shù)。對(duì)于任意函數(shù)F， 如果都有xFy，則記做，并稱y為F在x上的值。29計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2u (2) 特殊函數(shù) 函數(shù)的性質(zhì) 設(shè)函數(shù)f :AB若對(duì)于任何的x1,x2A，x1x2，都有f(x1)f(x2)，則關(guān)系與函數(shù)稱f是的。 若Ran(f)B，則稱f是。的，則稱f是 若f既是的，又是的。30計(jì)算機(jī)科學(xué)導(dǎo)論12.3.2關(guān)系與函數(shù) 復(fù)合函數(shù)設(shè)f是從集合A到集合B的函數(shù)，g是從集合B到集合C的函數(shù)，f和g的復(fù)合用f g表示為f g =(a,c)|aAcC$b(bB)(a,b)f(b,c)g 反函數(shù)設(shè)函數(shù)f是集合X到集合Y的一個(gè)函數(shù)。則f的反函數(shù)是集合Y到集合X的函數(shù)，對(duì)

16、于yY，都分派一個(gè)惟一的xX和它對(duì)應(yīng)，使得f(x)=y 。f的反函數(shù)記作：f 1: YX，即f 1(y)=x。31計(jì)算機(jī)科學(xué)導(dǎo)論12.4代數(shù)結(jié)構(gòu)12.4.1代數(shù)結(jié)構(gòu)概述u 1.運(yùn)算的定義及性質(zhì) （以二元運(yùn)算為例）設(shè)S為集合，函數(shù) f：S SS 稱為S上的二元運(yùn)算，簡(jiǎn)稱為二元運(yùn)算。 二元運(yùn)算的一些性質(zhì)： (1) 設(shè) 為S上的二元運(yùn)算，如果對(duì)于任意的x,yS都有x y =y x，則稱運(yùn)算 在S上滿換律。 (2) 設(shè) 為S上的二元運(yùn)算，如果對(duì)于任意的x,y,zS都有 (x y)z =x (y z)，則稱運(yùn)算 在S上滿足結(jié)合律。32計(jì)算機(jī)科學(xué)導(dǎo)論12.4.1代數(shù)結(jié)構(gòu)概述 (3) 設(shè) S上的二元運(yùn)算，如

17、果對(duì)于任意的xS有x x=x則稱運(yùn)算 在S上滿足冪等律。 (4) 設(shè) 和*為S上兩個(gè)二元運(yùn)算，如果對(duì)于任意的x,y,zS，有x*(y z) (x*y) (x*z)(左分配律)(右分配律)(y z)*x (y*x) (z*x)則稱運(yùn)算*對(duì)運(yùn)算滿足分配律。 (5) 設(shè) 和*為S上兩個(gè)可交換的二元運(yùn)算，如果對(duì)于任意的x,yS，都有x *(x y)xx (x *y)x 則稱運(yùn)算和*滿足吸收律。33計(jì)算機(jī)科學(xué)導(dǎo)論u 2運(yùn)算中的特殊元素集合中有些元素在運(yùn)算過程中具有特殊的性質(zhì)，它們 是集合運(yùn)算中的特殊元素。 (1)元。設(shè)*為S上的二元運(yùn)算，如果元素eS且對(duì)任意元素xS，有x*e=e*x=x則稱e為S上關(guān)于

18、*運(yùn)算的元，且唯一。 (2)零元。設(shè)*為S上的二元運(yùn)算，如果元素OS且對(duì)任 意元素xS，有x*O=O*x=O則稱O為S上關(guān)于*運(yùn)算的零元，且唯一。 (3)逆元。設(shè)*為S上的二元運(yùn)算，eS為運(yùn)算*的 對(duì)于元素xS，且對(duì)任意元素yS，有元。x*y=y*x=e則稱y為x的逆元。34計(jì)算機(jī)科學(xué)導(dǎo)論12.4.1代數(shù)結(jié)構(gòu)概述u 3.代數(shù)結(jié)構(gòu)的定義代數(shù)結(jié)構(gòu)通常指由以下三個(gè)部分組成的數(shù)學(xué)結(jié)構(gòu)：一個(gè)非空集合S，稱為代數(shù)結(jié)構(gòu)的載體。S上的若干運(yùn)算。一組刻畫載體S上各運(yùn)算所滿足性質(zhì)的公理。通常，代數(shù)結(jié)構(gòu)用一個(gè)多元序組來表示，其中，S是載體， ，*，為各種運(yùn)算。有時(shí)，S中地位比較特殊的元素(如也會(huì)被列入這個(gè)多元組的末

19、尾。元、零元、逆元)例如，以自然數(shù)集N為載體，“+”運(yùn)算可以作為二元運(yùn)算組成一個(gè)代數(shù)結(jié)構(gòu)，記為。35計(jì)算機(jī)科學(xué)導(dǎo)論12.4.2格與布爾代數(shù)u 1.格 (1)格的定義：有序集稱為格(lattice)，如果A的任何兩個(gè)元素的子集都有上確界和下確界。通常，用ab表示a,b的上確界，用ab表示a,b的下確界。(b)(a) 格36計(jì)算機(jī)科學(xué)導(dǎo)論12.4.2格與布爾代數(shù) (2)分配格稱格為分配格，如果它滿足分配律，即對(duì)任意a,b,cA,a(bc)=(ab) (ac)a(bc)=(ab) (ac)37計(jì)算機(jī)科學(xué)導(dǎo)論12.4.2格與布爾代數(shù) (3)有界格格稱為有界格，如果A中既有上確界1，又有下確界0。則，0

20、和1稱為A的界。對(duì)于A中的一個(gè)元素a，如果有 ab =1，ab=0則稱b為a 的補(bǔ)補(bǔ)。記為a。如果A中的每個(gè)元素都有補(bǔ)元，則有界格稱為有補(bǔ)格。38計(jì)算機(jī)科學(xué)導(dǎo)論12.4.2格與布爾代數(shù)u 2.布爾代數(shù)的定義定義：代數(shù)系統(tǒng)稱為布爾代數(shù)，如果 B滿足以下條件： 運(yùn)算，滿換律。 運(yùn)算對(duì)運(yùn)算滿足分配律，運(yùn)算對(duì)運(yùn)算也滿足分配律。 B有運(yùn)算元1和運(yùn)算零元0、運(yùn)算元0和運(yùn)算零元1。 對(duì)B中的每一個(gè)元素a，均存在元素a，使aa=1， aa=039計(jì)算機(jī)科學(xué)導(dǎo)論12.5圖論12.5.1圖的基本概念u 1圖的由來 哥七橋問題40計(jì)算機(jī)科學(xué)導(dǎo)論12.5.1圖的基本概念u 2.圖的基本概念(1) 圖的定義圖(grap

21、h)G由三個(gè)部分所組成： 非空集合V(G)，稱為圖G的節(jié)點(diǎn)集，其成員稱為節(jié)點(diǎn)或頂點(diǎn)(nodes or vertices)。 集合 E(G)，稱為圖G的，其成員稱為邊(edges)。 函數(shù)(G):E(G)(V(G)，V(G)，稱為邊與頂點(diǎn)的關(guān)聯(lián)(associatve mapping)。41計(jì)算機(jī)科學(xué)導(dǎo)論12.5.1圖的基本概念u (2) 關(guān)于圖的概念設(shè)圖G為 當(dāng)V和E為有限集時(shí)，稱G為有限圖，否則稱G為無限圖。在此只討論有限圖。 當(dāng)G為，稱G為；當(dāng)G為非，稱G為重圖，又稱滿足(e1) = (e2)的不同邊e1、e2為重邊，或平行邊。 當(dāng)(e)(v,v)(或)時(shí)，稱e為環(huán)(loops)。無環(huán)。當(dāng)G

22、為有限簡(jiǎn)和重邊的無向稱為簡(jiǎn)時(shí)，也常用(n,m)表示圖G，其中n = V，m = E 。42計(jì)算機(jī)科學(xué)導(dǎo)論12.5.1圖的基本概念 在G中，(e)(u,v)(或)時(shí)，也用(u,v)(或)表示邊e，這時(shí)稱u,v鄰接e, u,v是e的端點(diǎn)(或稱u為e的起點(diǎn)，v為e的終點(diǎn))；也稱e關(guān)聯(lián)結(jié)點(diǎn)u,v 。不是任何邊的端點(diǎn)的節(jié)點(diǎn)稱為孤立結(jié)點(diǎn)，僅由孤立結(jié)點(diǎn)構(gòu) 成的圖(E = )稱為零圖。43計(jì)算機(jī)科學(xué)導(dǎo)論12.5.1圖的基本概念u (3) 結(jié)點(diǎn)的度 定義：在無，結(jié)點(diǎn)v的度(degree)d(v)是v作為邊的端點(diǎn)的數(shù)目。在有，結(jié)點(diǎn)v的出度d +(v)(out-degree)是以v作為有向邊起點(diǎn)的數(shù)目，v的入度d

23、-(v)(in-degree)是v 作為有向邊終點(diǎn)的數(shù)目。結(jié)點(diǎn)的度是v的出度與入度之和。44計(jì)算機(jī)科學(xué)導(dǎo)論12.5.2路徑、回路及連通性 定義：圖G的頂點(diǎn)v1到頂點(diǎn)vl的擬路徑(pseudo path)是指如下頂點(diǎn)與邊的序列：v1 ,e1 ,v2 ,e2 ,v3 , ,v l -1 ,el-1 , v l 其中v1 ,v2 ,v3 , ,v l -1 ,v l為G的頂點(diǎn)，e1 ,e2 , ,e l -1為G的邊，且e i( i= 1,2, ,l-1 )以v i及v i +1為端點(diǎn)，(對(duì)有G，ei以vi為起點(diǎn)，以v i +1為終點(diǎn))；擬路徑的邊數(shù)l1稱為該擬路徑的長(zhǎng)度。當(dāng)e i( i= 1,2,

24、 , l-1 )各不相同時(shí)，該擬路徑稱為路徑(walk)，又當(dāng)v i(i = 1,2, ,l)各不相同時(shí)(除v1與v1)，則稱此路徑為通路(Path)。v1v1 的路徑稱為閉路徑(closed walk)；v1= v1的通路稱為回路(circuit)。45計(jì)算機(jī)科學(xué)導(dǎo)論12.5.2 定義：稱無路徑、回路及連通性G是連通的(Connected)，如果G的任何兩個(gè)頂點(diǎn)都是相互可達(dá)的。 定義：稱有G是強(qiáng)連通的，如果G的任何兩個(gè)G是單向連通的，頂點(diǎn)都是相互可達(dá)的；稱有如果G的任何兩個(gè)頂點(diǎn)中，至少從一個(gè)頂點(diǎn)到另一G是弱連通的，如果G是連通的。個(gè)頂點(diǎn)是可達(dá)的；稱有的有向邊被看作無(a) 強(qiáng)連通圖(b) 單

25、向連通圖(c)弱連通圖46計(jì)算機(jī)科學(xué)導(dǎo)論12.5.3圖的矩陣表示 (1)關(guān)聯(lián)矩陣47計(jì)算機(jī)科學(xué)導(dǎo)論12.5.3圖的矩陣表示 (2) 鄰接矩陣48計(jì)算機(jī)科學(xué)導(dǎo)論12.6離散概率概率(Probability)在推理過程中具有非常重要的作用，它通常用來衡量發(fā)生的可能性的大小，或者說用來衡量人們期待的占總體的比例u 離散概率(Discrete Probability)的一些基本知識(shí)： 定義：概率試驗(yàn)通常指人們對(duì)隨機(jī)現(xiàn)象的結(jié)果進(jìn)行的過程，通常記為E。觀察、 定義：樣本空間指的是概率試驗(yàn)的所有結(jié)果的集合，通常記為S。樣本空間中的每個(gè)元素分別稱為樣本點(diǎn)。如果樣本空間含有有限個(gè)或可數(shù)的離散的樣本點(diǎn)， 該樣本空間就是離散樣本空間。 同一個(gè)概率試驗(yàn)可以有不同的樣本空間。49計(jì)算機(jī)科學(xué)導(dǎo)論12.6離散概率 定義：離散樣本空間S的任意子集，稱為S