離散數(shù)學(xué)之圖論ppt課件(已修改)
2025-05-14 05:11 本頁面
【正文】 離散數(shù)學(xué)之圖論（ 1） 上海交通大學(xué)軟件學(xué)院 吳剛 2022年春 內(nèi)容 ? 圖的基本概念 ? 通路、回路、連通性 ? 歐拉圖 ? 漢密爾頓圖 ? 圖的矩陣表示 圖論 ? 圖論已有二百多年歷史，近四五十年來發(fā)展十分迅速，成為一個(gè)新興的數(shù)學(xué)分支 ? 計(jì)算機(jī)科學(xué)中許多概念、算法需要圖論支持（如二叉樹） ? 為計(jì)算機(jī)應(yīng)用建模提供數(shù)學(xué)工具 ? 圖論研究 圖的邏輯結(jié)構(gòu)與性質(zhì) ，不關(guān)注圖的具體幾何形態(tài) 圖的基本概念 ? 哥尼斯堡橋問題 圖的基本概念 ? 結(jié)點(diǎn)：用來表示事物 ? 邊：表示事物的聯(lián)系（與結(jié)點(diǎn)對相關(guān)） ? 定義：圖 G是由非空結(jié)點(diǎn)集合 V={v1, v2,… vn}和邊集合 E={e1, e2,… em}組成，其中 ek用結(jié)點(diǎn)對表示即 (vi, vj) ? 一個(gè)圖可表示為 G=V， E 圖的基本概念 ? 圖有兩種類型：有向圖和無向圖 ? 有向圖中結(jié)點(diǎn)對 (vi, vj)有方向性，稱為有向邊 ? 無向圖中結(jié)點(diǎn)對 (vi, vj)沒有方向性，稱為無向邊，也常表示為 {vi, vj} 圖的基本概念 ? 一個(gè)有 n個(gè)結(jié)點(diǎn)、 m條邊的圖稱為 (n,m)圖 ? 零圖：即（ n, 0）圖 ? 平凡圖：即（ 1, 0）圖 ? 其他概念 ? 自圈 (環(huán) )： (vi, vi) ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1