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