北大離散數(shù)學(xué)chap-展示頁
2024-08-20 04:01本頁面
【正文】 樹， 39。 注意： (1) 生成樹不唯一， (2) 余樹不一定是樹。 樹枝 弦 余樹 —— G T在 中的邊， —— G T不在 中的邊， —— T 的所有的弦的集合的導(dǎo)出子圖。 二、生成樹。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (5) 1 1 2 2 2 26T例 (1) 一棵樹有 7片葉， 3個 3度頂點，其余都 是 4度頂點，求 4度頂點多少個？ 解： 設(shè)有 個 4度頂點，則頂點數(shù) x 73 x?? ， 邊數(shù) 7 3 1x? ? ? ， 由握手定理， 4 3 3 7 2 ( 7 3 1 )xx? ? ? ? ? ? ?， 解得 1x? ， 故這棵樹有 1個 4度頂點。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (3) 1 1 1 1 3 33T例 畫出所有的 6個頂點的非同構(gòu)的樹。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (1) 1 1 1 1 1 51T例 畫出所有的 6個頂點的非同構(gòu)的樹。 證明： 設(shè) 為 階非平凡樹， ,T V E? n設(shè) 有 片樹葉，則有 T k 個頂點度數(shù)大于等 ()nk?于 2， 12 ( ) 2 ( )niim d v k n k?? ? ? ??由握手定理， 又由 (1) 1mn?? ，代入上式，解得 2k ? ， 即 至少 2片葉。 (1) 樹中頂點數(shù)與邊數(shù)的關(guān)系： 1nm?? 。 (6) 是連通的，但刪除任何一條邊后，就不 G連通了。 樹的六個等價定義。 (4) 無回路且 G 1nm?? 。 G(2) 的每對頂點間具有唯一的路徑。 T???樹葉——度數(shù)為1的頂點樹 的頂點分支點——度數(shù)大于1的頂點例 ( 1 )fceadb( 2 )( 3 )例 (4)樹的六個等價定義。 T平凡樹 —— 平凡圖。 無向樹 —— 連通且不含回路的無向圖。 本章中所談回路均指簡單回路或初級回路。第九章 樹 第一節(jié) 無向樹及生成樹 內(nèi)容： 無向樹，生成樹。 重點： 無向樹的定義 (包括等價定義 )， 無向樹的性質(zhì)， 生成樹的定義，由連通圖構(gòu)造最小 生成樹的方法。 一、無向樹。 無向樹簡稱樹，常用 表示。 森林 —— 連通分支數(shù)大于等于 2，且每個連通 分支都是樹的無向圖。 (1) 連通且不含回路。 G(3) 連通且 G 1nm?? 。 定理： 設(shè) ,G V E? Vn? Em?， ， ， 則以下命題等價。 (5) 無回路，但在 G 中任兩個不相鄰的頂點 G之間增加一條邊，就形成唯一的一條初級 回路。 性質(zhì) 。 (2) 定理 ：非平凡樹至少 2片樹葉。 T例 畫出所有的 6個頂點的非同構(gòu)的樹。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種 度數(shù)序列： (2) 1 1 1 1 2 42T例 畫出所有的 6個頂點的非同構(gòu)的樹。 解： 所要畫的樹有 6個頂點，則邊數(shù)為 5，因此 6個頂點的度數(shù)之和為 10，可以產(chǎn)生以下五種
法律信息相關(guān)推薦
鄂ICP備17016276號-1