離散數(shù)學(xué)CH04圖論基本概念

1、會計(jì)學(xué)1離散數(shù)學(xué)離散數(shù)學(xué)CH04圖論基本概念圖論基本概念圖的基本概念4.1連通圖4.34.4圖的矩陣表示路和回路4.2歐拉圖和哈密頓圖4.5二部圖及匹配4.74.8平面圖樹4.6有趣的圖論問題能否從河岸或小島出發(fā)，通過每一座橋，且僅通過一次回到原地？問題ADBCabcdefg 圖論是一個重要的數(shù)學(xué)分支。數(shù)學(xué)家歐拉1736年發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題。克?；舴?qū)﹄娐肪W(wǎng)絡(luò)的研究、凱來在有機(jī)化學(xué)的計(jì)算中都應(yīng)用了樹和生成樹的概念。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的行走路線問題等等。這些古老的問題當(dāng)時吸引了許多學(xué)者的注意，從而在這些問題研究的基礎(chǔ)上，

2、又提出了著名的四色猜想和環(huán)游世界各國的問題。有趣的圖論問題（0，0）（0，3）（3，0）（5，1）（0，1） （1，0）（1，3）（3，3）（5，0） （2，3）（2，0） （0，2） （5，2） （4，3）（4，0）（5，3）圖 有趣的圖論問題有趣的圖論問題有趣的圖論問題有趣的圖論問題4.1 圖的基本概念abcdabcddcbabacdacbddcba4.1 圖的基本概念下面表示的是同一個圖4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念【例4.1】 解：G的圖形如圖所示。4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念有向圖無向圖混合圖4.1 圖

3、的基本概念4.1 圖的基本概念4.1 圖的基本概念2)deg(1v3)deg(2v2)deg(3v2)deg(4v5)deg(5v1v2v3v4v5v5)( G2)(G例4.1 圖的基本概念EvVvii2)deg(一個圖中有10個結(jié)點(diǎn)，每個結(jié)點(diǎn)的度數(shù)為6, 圖中有多少條邊？結(jié)點(diǎn)度數(shù)總和：6 10=60因?yàn)?2e = 60，所以 e = 30.解：4.1 圖的基本概念下面哪些可以作為一個圖的度數(shù)列（或稱為可圖化的）)5 , 4 , 4 , 3 , 2(.2)5 , 4 , 4 , 3 , 3 , 2(.1)3 , 3 , 3 , 1 (.3)6 , 6 , 5 , 4 , 3 , 3 , 1 (

4、.5)5 , 4 , 3 , 3 , 2 , 1 (.6)7 , 6 , 5 , 4 , 3 , 3 , 2(.4？V=v1, v2, , vn為無向圖G的頂點(diǎn)集，稱d(v1), d(v2), , d(vn)為G的度數(shù)列4.1 圖的基本概念 在任何有向圖中,所有結(jié)點(diǎn)入度之和等于出度之和.EvvVviVviii)(deg)(deg定理14.1.24.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念3K4K5K4.1 圖的基本概念).1(21nn因?yàn)?Kn 中任意兩點(diǎn)間都有邊相連，而 n 個

5、結(jié)點(diǎn)中任取兩點(diǎn)的組合數(shù)(即總邊數(shù))為:).1(212nnCn n階有向完全圖的邊數(shù)為？4.1 圖的基本概念4.1 圖的基本概念正則圖邊數(shù)（由握手定理得）2nkm 4.1 圖的基本概念4.1 圖的基本概念4.1 圖的基本概念G1 G24.1 圖的基本概念充要條件4.1 圖的基本概念4.1 圖的基本概念必要條件4.1 圖的基本概念1v1v2v2v3v3v6v6v4v4v5v5v例4.1 圖的基本概念ddaabbcc例4.1 圖的基本概念v1v2v3v4v5v6v1v2v3v4v5v6例4.1 圖的基本概念1v1v2v2v3v3v4v4v5v5v6v6v例4.1 圖的基本概念aabbccdd例4.1

6、 圖的基本概念GGGG例4.1 圖的基本概念例4.1 圖的基本概念5v1v2v3v6v10v9v7v8v4v例(續(xù))4.1 圖的基本概念1v6v10v9v7v8v2v3v4v5v1v2v3v6v10v9v7v8v4v5v例(續(xù))4.1 圖的基本概念1v2v3v6v4v5v10v9v7v8v1v2v3v6v10v9v7v8v4v5v例(續(xù))4.1 圖的基本概念1v2v3v6v4v5v10v9v7v8v1v2v3v6v10v9v7v8v4v5v例(續(xù))4.1 圖的基本概念1v2v3v6v4v5v10v9v7v8v例(續(xù))4.1 圖的基本概念GG4.1 圖的基本概念GGK54.1 圖的基本概念在圖中

7、，(b)是(a)的補(bǔ)圖，(a)與(b)同構(gòu)，所以(a)是自補(bǔ)圖。 ？解G 是一個有 15 條邊的簡單圖， 有 13 條邊，請問 G 中有多少個結(jié)點(diǎn)? G共有 15 + 13 = 28 條邊，GG 是一個完全圖，它的結(jié)點(diǎn)數(shù)與 G 相同，設(shè)為 n，則GG n(n-1)/2 = 28n = 8問題4.1 圖的基本概念4.1 圖的基本概念包含 G 的所有結(jié)點(diǎn)的子圖。生成子圖G2G1G生成子圖子圖3G子圖例4.1 圖的基本概念生成子圖子圖不是子圖v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4例4.1 圖的基本概念？請畫出 4 階 3 條邊的所有非同構(gòu)的無向簡單圖？問題4.1 圖的基本概

8、念【例】 畫出K4的所有非同構(gòu)的生成子圖。4.1 圖的基本概念【例】 設(shè)G1,G2,G3,G4均是4階3條邊的無向簡單圖，則它們之間至少有幾個是同構(gòu)的？4.1 圖的基本概念本節(jié)小結(jié)4.1 圖的基本概念 圖論是一個重要的數(shù)學(xué)分支。數(shù)學(xué)家歐拉1736年發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題?？讼；舴?qū)﹄娐肪W(wǎng)絡(luò)的研究、凱來在有機(jī)化學(xué)的計(jì)算中都應(yīng)用了樹和生成樹的概念。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的行走路線問題等等。這些古老的問題當(dāng)時吸引了許多學(xué)者的注意，從而在這些問題研究的基礎(chǔ)上，又提出了著名的四色猜想和環(huán)游世界各國的問題。有趣的圖論問題4.1 圖的基本概念EvVvii2)deg(一個圖中有10個結(jié)點(diǎn)，每個結(jié)點(diǎn)的度數(shù)為6, 圖中有多少條邊？結(jié)點(diǎn)度數(shù)總和：6 10=60因?yàn)?2e = 60，所以 e = 30.解：4.1 圖的基本概念 在任何有向圖中,所有結(jié)點(diǎn)入度之