国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁(yè)  >  技術(shù)干貨  > 什么是極大強(qiáng)連通子圖?

什么是極大強(qiáng)連通子圖?

來(lái)源:千鋒教育
發(fā)布人:xqq
時(shí)間: 2023-10-11 03:49:38 1696967378

一、極大強(qiáng)連通子圖是什么

極大強(qiáng)連通子圖

(1)極大連通子圖是連通圖的一個(gè)連通分量,連通分量本身是一個(gè)連通圖。
(2)連通圖的極大連通子圖只有一個(gè)就是其本身,是少數(shù)的。
(3)非連通的極大連通子圖有多個(gè),每一個(gè)都是一個(gè)連通圖。
為什么稱為極大?如果將連通分量外的任意一個(gè)頂點(diǎn)添加進(jìn)連通分量都會(huì)造成不連通。

極小連通子圖

(1)一個(gè)連通圖的生成樹是該連通圖的極小連通子圖。同一個(gè)連通圖可以有不同的生成樹,所以生成樹不是少數(shù)的。

(2)極小連通子圖=生成樹,則有n個(gè)頂點(diǎn),必然有n-1條邊。

(3)為什么稱為最小?如果去極小連通子圖的一條邊就無(wú)法構(gòu)成樹,不滿足樹的定義。意味著在極小連通子圖中每一條邊都是必不可少的。如果給極小連通子圖增加一條邊,n個(gè)節(jié)點(diǎn),n條邊,則必然會(huì)構(gòu)成環(huán)。意味只有能夠連通圖中所有頂點(diǎn)而又不會(huì)構(gòu)成回路的任意的子圖都是他的生成樹。

延伸閱讀:

二、強(qiáng)連通分量

強(qiáng)連通分量是有向圖的極大的強(qiáng)連通子圖,所謂“極大”意味著,把圖劃分為若干個(gè)強(qiáng)連通分量后,不存在兩個(gè)強(qiáng)連通分量相互可達(dá)。處理強(qiáng)連通分量的一個(gè)有力的工具是dfs生成樹:在dfs時(shí),每當(dāng)通過(guò)某條邊e訪問(wèn)到一個(gè)新節(jié)點(diǎn),就加入這個(gè)點(diǎn)和這條邊,最后得到的便是dfs生成樹。反向邊和橫叉邊都有一個(gè)特點(diǎn):起點(diǎn)的dfs序必然大于終點(diǎn)的dfs序。這可以導(dǎo)出一個(gè)有用的結(jié)論:對(duì)于每個(gè)強(qiáng)連通分量,存在一個(gè)點(diǎn)是其他所有點(diǎn)的祖先。若不然,則可以把強(qiáng)連通分量劃成 n個(gè)分支,使各分支的祖先節(jié)點(diǎn)互相不為彼此的祖先。這些分支間不能通過(guò)樹邊相連,只能通過(guò)至少n條橫叉邊相連,但這必然會(huì)違背上一段講的性質(zhì)。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請(qǐng)您保持通訊暢通,專屬學(xué)習(xí)老師24小時(shí)內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
在C語(yǔ)言下數(shù)組array與鏈表linklist各自的優(yōu)點(diǎn)和缺陷是什么?

一、在C語(yǔ)言下數(shù)組array與鏈表linklist各自的優(yōu)點(diǎn)和缺陷數(shù)組可以通過(guò)下標(biāo)訪問(wèn),隨機(jī)訪問(wèn)效率高,鏈表需要通過(guò)指針遍歷,訪問(wèn)效率低。數(shù)組在分配...詳情>>

2023-10-11 05:43:25
oa系統(tǒng)一般有哪些模塊?

一、組織架構(gòu)模塊組織架構(gòu)模塊記錄了企業(yè)的組織結(jié)構(gòu)、人員信息、部門職責(zé)、工作流程等基本信息,實(shí)現(xiàn)了組織架構(gòu)的可視化和管理。該模塊主要包括...詳情>>

2023-10-11 05:33:42
為什么python沒(méi)有大頂堆?

一、python沒(méi)有大頂堆的原因Python沒(méi)有內(nèi)置大頂堆,是因?yàn)樵趯?shí)際使用中,大頂堆并不是那么常用。相比之下,小頂堆和普通的堆操作更具有廣泛的應(yīng)...詳情>>

2023-10-11 05:30:39
什么是crm管理?

一、crm管理概念 CRM管理也叫客戶管理,亦即客戶關(guān)系管理(Customer Relationship Management)的簡(jiǎn)稱。CRM管理的主要含義就是通過(guò)對(duì)客戶詳細(xì)資...詳情>>

2023-10-11 05:28:00
單調(diào)棧什么時(shí)候從后向前遍歷,什么時(shí)候從前向后遍歷?

一、單調(diào)棧什么時(shí)候從后向前遍歷,什么時(shí)候從前向后遍歷如果是求右邊的名列前茅個(gè)最大,那么就是從右向左遍歷,構(gòu)建單調(diào)遞增棧。如果是求右邊的...詳情>>

2023-10-11 05:23:50
快速通道