圖定義及相關(guān)概念

• 思維導(dǎo)圖：
• 圖的定義：
• 圖的基本概念：
• • 有向圖和無(wú)向圖：
  • 簡(jiǎn)單圖和多重圖：
  • 完全圖：
  • 子圖：
  • 生成子圖：
  • 連通和強(qiáng)連通：
  • 連通圖和強(qiáng)連通圖：
  • 連通分量和強(qiáng)連通分量：（極大連通子圖和極大強(qiáng)連通子圖）
  • 極小連通子圖和極小強(qiáng)連通子圖：
  • 生成樹和生成森林：
  • 頂點(diǎn)的度：
  • 網(wǎng)：
  • 稠密圖和稀疏圖：
  • 有向樹：
  • 路徑：
  • 路徑長(zhǎng)度：
  • 回路：

思維導(dǎo)圖：

圖的定義：

圖的基本概念：

有向圖和無(wú)向圖：

簡(jiǎn)單圖和多重圖：

完全圖：

子圖：

生成子圖：

滿足V(G’) = V(G)的子圖(即頂點(diǎn)集相同的子圖)

連通和強(qiáng)連通：

ps： 連通是無(wú)向圖中的概念，強(qiáng)連通是有向圖中的概念

連通圖和強(qiáng)連通圖：

Q1： n個(gè)頂點(diǎn)的連通圖和強(qiáng)連通圖最少有多少條邊？
連通圖有n-1條邊
強(qiáng)連通圖有n條邊（形成回路）
Q2: 在無(wú)向圖中，若為非連通圖，則最多可能的邊數(shù)：

連通分量和強(qiáng)連通分量：（極大連通子圖和極大強(qiáng)連通子圖）

結(jié)論： 若原圖為連通圖則連通分量只有一個(gè)；若原圖不是連通圖，則原圖存在幾個(gè)連通圖就有幾個(gè)連通分量

連通分量： 對(duì)無(wú)向圖而言

1、要點(diǎn)一：任意倆個(gè)節(jié)點(diǎn)連通2、要點(diǎn)二：子圖---->包括圖本身 3、要點(diǎn)三：極大---->沒有任意一個(gè)子圖可以包含該子圖

強(qiáng)連通分量： 對(duì)有向圖而言

1、要點(diǎn)一：任意倆個(gè)節(jié)點(diǎn)強(qiáng)連通2、要點(diǎn)二：子圖---->包括圖本身 3、要點(diǎn)三：極大---->沒有任意一個(gè)子圖可以包含該子圖4、要點(diǎn)四：強(qiáng)連通---->任意倆個(gè)頂點(diǎn)之間都有路徑

極小連通子圖和極小強(qiáng)連通子圖：

生成樹和生成森林：

頂點(diǎn)的度：

ps： 在有向圖中有出度和入度之分

網(wǎng)：

在圖中加入權(quán)值

稠密圖和稀疏圖：

有向樹：

路徑：

本質(zhì)：頂點(diǎn)序列

路徑長(zhǎng)度：

回路：

總結(jié)

以上是生活随笔為你收集整理的数据结构之图定义及相关概念的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。