正文內容

離散數學復習資料-資料下載頁

2026-07-27 10:25本頁面

　　

【正文】變換乘法，E(A)構成一個群，稱為集合A上的一一變換群. E(A)的子群稱為變換群.h置換群，n元集合M上的所有n元置換Sn，關于置換乘法構成n元對換群，它的子群叫置換群. 4. 置換，h置換，有限集合M＝{a1,a2,…,an}上的雙射s：M174。M，n元置換 h置換復合(乘法)，設, 那么h單位置換， h逆置換，s－1=n元集合M上的n元置換有n!個，有n元置換構成的集合，記作Sn. h輪換，滿足：(1)s(a1）=a2, s(a2）=a3, …,s(am）=a1； (2)s(a)=a，當a185。ak,(k=1,2,…,m)時. 則s是一個長度為m的輪換，記作(a1,a2,…,am). h重要結論：置換有結合律；不相交的輪換有交換律；Sn中任一置換都可以唯一地表示成一系列不相交的輪換之積. 5. 同態與同構h同態，代數系統(G,*)和(S, 176。)，f是從G到S上的一個映射. a,b206。G，有f(a*b)=f(a) 176。f(b)則稱f是由(G,*)到(S, 176。)的一個同態映射. 并稱G與S同態. 如果f 是滿射，則稱G與S是滿同態，記作G～S；如果f是單射，則稱G與S是單同態. (f(G), 176。)稱為(G,*)在f下的同態象.. h同構，代數系統(G,*)到(S, 176。)，如果f是從G到S的一個雙射，則稱f是從G到S的同構，h群同構，設群(G,*)和(S, 176。)，存在從(G,*)到(S, 176。)的同態雙射，則稱群(G,*)與(S, 176。)同構. 第7章幾種特殊的圖本章重點：歐拉圖和哈密頓圖、平面圖和樹的基本概念. 一、重點內容 1. 歐拉圖 h 歐拉通路(回路)與歐拉圖通過圖G的每條邊一次且僅一次，而且走遍每個結點的通路(回路)，就是歐拉通路(回路). 存在歐拉回路的圖就是歐拉圖. 歐拉回路要求邊不能重復，結點可以重復. 筆不離開紙，不重復地走完所有的邊，且走過所有結點，就是所謂的一筆畫. h歐拉圖或通路的判定 (1) 無向連通圖G是歐拉圖219。G不含奇數度結點(G的所有結點度數為偶數):(定理1) (2) 非平凡連通圖G含有歐拉通路219。G最多有兩個奇數度的結點；(定理1的推論) (3) 連通有向圖D含有有向歐拉回路(即歐拉圖)219。D中每個結點的入度＝出度連通有向圖D含有有向歐拉通路219。D中除兩個結點外，其余每個結點的入度＝出度，且此兩點滿足deg－(u)－deg＋(v)＝177。1. (定理2) 2. 哈密頓圖h哈密頓通路(回路)與哈密頓圖通過圖G的每個結點一次，且僅一次的通路(回路)，就是哈密頓通路(回路). 存在哈密頓回路的圖就是哈密頓圖. 判斷哈密頓圖是較為困難的. h哈密頓圖的充分條件和必要條件 (1) 在無向簡單圖G=V,E中189。V189。179。3,任意不同結點,則G是哈密頓圖.(充分條件，定理4) (2) 有向完全圖D＝V,E, 若，則圖D是哈密頓圖. (充分條件，定理5推論)(3) 設無向圖G=V,E,V1204。V，則P(G－V1)163。189。V1189。(必要條件，定理3)若此條件不滿足，即$V1204。V，使得P(G－V!)189。V1189。,則G一定不是哈密頓圖(非哈密頓圖的充分條件).h 平面圖一個圖能畫在平面上，除結點之外，再沒有邊與邊相交. 面、邊界和面的次數由連通平面圖G的邊圍成的其內部不含G的結點和邊的區域是面，常用r表示. 圍成面的各邊組成的回路是邊界. 邊界回路的長度是面的次數，記作deg(r). h重要結論(1)平面圖(所有面的次數之和＝邊的2倍)(定理6). (2)歐拉公式：平面圖面數為r，則(結點數與面數之和＝邊數＋2)(定理7)(3)平面圖(定理8) h判定條件：圖G是平面圖的充分必要條件是G不含與K3，3或K5在2度結點內同構的子圖. 4. 樹h樹連通無回路的無向圖. h樹的判別圖,T是樹的充分必要條件是(六個等價定義) (定理14):(1) T是無回路的連通圖； (2) 圖T無回路且m＝n－1；(3) 圖T連通且m＝n－1 (4) 圖T無回路，若增加一條邊，就得到一條且僅一條回路；(5) 圖T連通，若刪去任一邊，G則不連通；(6) 圖T的每一對結點之間有一條且僅有一條通路. h生成樹圖G的生成子圖是樹，該樹就是生成樹. h權與帶權圖 n個結點的連通圖G，每邊指定一正數，稱為權，每邊帶權的圖稱為帶權圖. G的生成樹T的所有邊的權之和是生成樹T的權，記作W(T). h最小生成樹帶權最小的生成樹. h有向樹有向圖刪去邊的方向為樹，該有向圖就是有向樹. h根樹與樹根非平凡有向樹，恰有一個結點的入度為0(該結點為樹根)，其余結點的入度為1，該樹為根樹. h每個結點的出度小于或等于2的根樹為二元樹(二叉樹)；每個結點的出度等于0或2的根樹為二元完全樹(二叉完全樹)；每個結點的出度等于2的根樹稱為正則二元樹(正則二叉樹).h哈夫曼樹用哈夫曼算法得到的最優二叉樹. 4. 有關樹的求法 h生成樹的破圈法和避圈法求法； h最小生成樹的克魯斯克爾求法； h哈夫曼樹的哈夫曼求法.

點擊復制文檔內容

范文總結相關推薦

離散數學復習資料-資料下載頁

離散數學-數論-資料下載頁

離散數學總結-資料下載頁

離散數學——樹-資料下載頁

離散數學題庫答案-資料下載頁

離散數學習題-資料下載頁

離散數學作業冊-資料下載頁

離散數學自學-資料下載頁

離散數學-學校教案-資料下載頁

離散數學講義-資料下載頁

離散數學-函數-資料下載頁

離散數學例題-資料下載頁

電大離散數學期末復習要點與重點考試資料小抄-資料下載頁

離散數學作業7最終-資料下載頁

離散數學1--資料下載頁

離散數學2-資料下載頁

離散數學復習資料-文庫吧

離散數學復習資料-wenkub

離散數學復習資料(已修改)

離散數學復習資料(編輯修改稿)

離散數學復習資料-wenkub.com