目的:了解圖論的基本概念;
重點:圖論的基本概念;
難點:度、圖同構。
無向圖、有向圖
圖結點 (頂點)邊階
關聯、鄰接
自圈、平行邊、簡單圖
度孤立點、端點
零圖、平凡圖、d度正則圖、完全圖
同構目的:了解子圖和圖的基本概念;
重點:子圖、可運算、圖的運算;
難點:圖的運算、子圖。
子圖、真子圖、生成子圖
由結點集匯出的子圖
可運算、不相交
交、並、環和
補圖目的:了解與路徑、迴路、連通性、分支、非迴圈圖相關的基本概念;掌握求加權路徑的演算法、判乙個圖是否有迴路、有有向迴路、有半迴路的過程;
重點:路徑、迴路、連通、分支等重要概念;求加權路徑的演算法;判迴路、有向迴路、半迴路、迴圈圖;
難點:幾種判定方法及其原理。
路徑可達
距離直徑
加權無向圖的連通
有向圖的基礎圖
有向圖的連通
極大子圖
分支有向圖的分支
半路徑迴路、半迴路、有向迴路
有迴路、非迴圈圖
目的:熟悉尤拉定理的運用、判尤拉圖和hamilton圖的方法;
重點:判尤拉圖、hamilton圖的演算法;尤拉定理的運用;
尤拉路徑、尤拉閉路
尤拉圖、尤拉有向圖
哈密頓迴路
目的:圖的各種矩陣表示及性質、圖的各種表示之間的關聯性質;
重點:圖的各種矩陣表示、各種表示之間的關聯性質;
難點:圖的各種表示之間的關聯性質。
鄰接矩陣
路徑矩陣、可達性矩陣
距離矩陣
目的:樹的六種定義,了解分支、森林、生成樹、生成森林、最小生成樹、枝、弦、基本迴路、有向樹、有向森林、二叉樹、最優二叉樹、有序樹、有序森林、定位二元有序樹等概念和性質;掌握求最小生成樹、最優二叉樹的演算法、定位二元有序樹和有序森林的雙射關係,以及有關的證明方法;
重點:樹的六種定義,各種概念、演算法及基本的證明思路;
難點:通過樹的六種定義方式如何發現樹的各種性質,大量相關知識點在證明種的綜合運用。 樹森林
生成樹、生成森林
最小生成樹
枝、弦圈秩、餘圈秩
基本迴路
有向樹有向森林
m元有向樹
葉加權二叉樹
最優二叉樹
有序樹、有序森林
定位有序樹
離散數學圖論課後總結
第8章圖論 例1 下面哪些數的序列,可能是乙個圖的度數序列?如果可能,請試畫出它的圖.哪些可能不是簡單圖?a 1,2,3,4,5 b 2,2,2,2,2 c 1,2,3,2,4 d 1,1,1,1,4 e 1,2,2,4,5 解 a 不是,因為有三個數字是奇數.b c d 是.e 不是簡單圖,因為它...
離散數學教學大綱
4 代數系統 一般代數系統和子代數系統的基本概念及其基本性質,代數系統的同態與同構 同餘關係與商代數 半群與群的基本概念與性質 特殊的群 陪集與拉格朗日定理 商集 環和域的基本概念與判斷方法 格的定義和基本性質 偏序關係與代數系統的關係 特殊格 布林代數與布林表示式。16 22學時 代數系統在現代電...
離散數學教學大綱 64
5 代數系統的一般性質 二元運算的概念和性質,么元 零元 逆元的概念和計算,代數系統及其子代數的概念,代數系統的同態與同構。6 幾個典型的代數系統 半群 獨異點 群的概念,子群的概念和判定,迴圈群和置換群的概念和性質,環 域的概念,格 子格 分配格 有界格 有補格 布林代數的概念。7 圖的基本概念 ...