(2022.07.01 Fri)
概念
圖G由頂點(diǎn)(vertices)集合V和連接V中頂點(diǎn)的邊(edge)的集合E組成舀瓢。有些書(shū)上成頂點(diǎn)為nodes啥容，稱(chēng)邊為arcs。
- 有向(directed)：圖中的邊或者有向或者無(wú)向(undirected)。如果兩個(gè)頂點(diǎn)u和v的連接是有序的助币，從u指向v静陈，則稱(chēng)該邊(u, v)有向燕雁。如果u和v無(wú)序，則邊(u, v)無(wú)向鲸拥。無(wú)向邊有時(shí)被表示成{u, v}拐格，但為了簡(jiǎn)單常使用(u, v)表示。對(duì)于無(wú)向邊(u, v)刑赶，等價(jià)于(v, u)捏浊。無(wú)向邊的兩個(gè)頂點(diǎn)對(duì)稱(chēng)(symetric)，有向邊的兩頂點(diǎn)非對(duì)稱(chēng)(asymetric)撞叨。如果圖中的所有邊都是無(wú)向邊金踪，稱(chēng)該圖為無(wú)向圖；相應(yīng)的牵敷，所有邊有向胡岔，稱(chēng)之為有向圖(digraph)。如果圖中有的邊有向有的邊無(wú)向枷餐，稱(chēng)之為混合圖(mixed graph)靶瘸。
- 邊的兩個(gè)端點(diǎn)被稱(chēng)為邊的end vertices/endpoints。如果邊有向，則第一個(gè)endpoint稱(chēng)為源點(diǎn)(origin)怨咪，另一個(gè)endpoint稱(chēng)為終點(diǎn)(destination)屋剑。
- 相鄰(adjacent)：如果兩個(gè)頂點(diǎn)u和v是一個(gè)邊的兩個(gè)頂點(diǎn)，則稱(chēng)u和v相鄰诗眨。
- 附帶(incident)：如果一個(gè)頂點(diǎn)是一條邊的終點(diǎn)唉匾，則稱(chēng)這條邊附帶于(be incident to)這個(gè)頂點(diǎn)
- 出發(fā)(outgoing)/進(jìn)入(incoming)邊：當(dāng)一個(gè)頂點(diǎn)是有向邊的起點(diǎn)，稱(chēng)該邊是頂點(diǎn)的出發(fā)邊匠楚；當(dāng)一個(gè)頂點(diǎn)是一條有向邊的終點(diǎn)肄鸽，稱(chēng)該邊是該頂點(diǎn)的進(jìn)入邊。
- 度(degree)：頂點(diǎn)v的度油啤，標(biāo)記為
deg(v)典徘，是該頂點(diǎn)附帶邊的個(gè)數(shù)。頂點(diǎn)的進(jìn)度(in-degree)和出度(out-degree)分別是該點(diǎn)的進(jìn)入邊數(shù)和出發(fā)邊數(shù)益咬，分別標(biāo)記為indeg(v)和outdeg(v)逮诲。 - 并行邊(parallel edges)/多邊(multiple edges)：兩個(gè)無(wú)向邊共享相同的頂點(diǎn)，或兩個(gè)有向邊共享相同的起點(diǎn)和終點(diǎn)幽告，比如飛機(jī)航線(xiàn)梅鹦，兩個(gè)城市之間有來(lái)往兩個(gè)航班
- 自環(huán)(self-loop)：如果一條有向或無(wú)向邊的兩個(gè)頂點(diǎn)為同一點(diǎn)，則稱(chēng)該邊self-loop冗锁。
- 簡(jiǎn)單圖(simple)：沒(méi)有并行邊或自環(huán)的圖稱(chēng)為簡(jiǎn)單圖齐唆。因此簡(jiǎn)單圖的邊可以表示為頂點(diǎn)對(duì)(vertex pair)的集(set)。
- 路徑(path)：路徑是頂點(diǎn)和邊交替的一個(gè)序列冻河，該序列始于一個(gè)頂點(diǎn)終于一個(gè)頂點(diǎn)箍邮，其中每個(gè)邊都是附帶于其predecessor和successor頂點(diǎn)。如果該路徑中的節(jié)點(diǎn)互不重復(fù)叨叙，則稱(chēng)該路徑簡(jiǎn)單(simple)锭弊。有向路徑(directed path)是路徑中的邊都是有向邊，且沿著各邊的方向行進(jìn)擂错。
- 環(huán)(cycle)：是以同一個(gè)點(diǎn)為起點(diǎn)和終點(diǎn)的路徑味滞，并至少包括一條邊。如果該環(huán)中除了起點(diǎn)和終點(diǎn)钮呀，其他點(diǎn)都互不重復(fù)剑鞍，則稱(chēng)該環(huán)簡(jiǎn)單。有向圖概念類(lèi)似有向邊爽醋。
- 無(wú)環(huán)(acyclic)：有向圖如果沒(méi)有有向環(huán)蚁署，則稱(chēng)為無(wú)環(huán)。
- 可達(dá)(reachable)：有向圖中子房，如果從頂點(diǎn)u到頂點(diǎn)v有有向路徑形用，則稱(chēng)u到達(dá)(reaches)v，或v從u可達(dá)(v is reachable from u)证杭。在無(wú)向圖中田度，可達(dá)性是對(duì)稱(chēng)的，u可達(dá)v則v可達(dá)u解愤。在有向圖中镇饺，很可能出現(xiàn)u到達(dá)v但v不能到達(dá)u的情況。
- 聯(lián)通(connected)：如果一個(gè)圖中任意兩點(diǎn)都有路徑連接送讲，則稱(chēng)該圖聯(lián)通奸笤。一個(gè)有向圖是強(qiáng)聯(lián)通的，如果任何兩點(diǎn)都能到達(dá)對(duì)方哼鬓。
- 子圖(subgraph)：一個(gè)圖如果其頂點(diǎn)和邊是另一個(gè)圖的子集监右，則稱(chēng)該圖為另一個(gè)圖的子圖。
- 生成子圖(spanning subgraph)：一個(gè)圖是另一個(gè)圖G的子圖异希，且包含G的所有頂點(diǎn)健盒，則該圖是G的生成子圖。如果圖G不聯(lián)通称簿，則它的最大聯(lián)通子圖被稱(chēng)為聯(lián)通分量(connected components of G)扣癣。
- 森林(forest)：沒(méi)有環(huán)的圖成為森林。
- 樹(shù)(tree)：聯(lián)通的樹(shù)憨降，即無(wú)環(huán)的聯(lián)通圖稱(chēng)為樹(shù)父虑。
- 生成樹(shù)(spanning tree)：圖的生成樹(shù)是樹(shù)形生成子圖。
定理
- 圖G中有m條邊授药，頂點(diǎn)集V士嚎，則有
說(shuō)明：在計(jì)算度時(shí)，每條邊都會(huì)被它的兩個(gè)頂點(diǎn)計(jì)算一次悔叽，所以頂點(diǎn)度的和是邊數(shù)的2倍航邢。 - 有向圖G有m條邊，和頂點(diǎn)集合V骄蝇，有
- 圖G是簡(jiǎn)單圖膳殷，含有n個(gè)頂點(diǎn)和m條邊，若G無(wú)向九火，則有
赚窃，如果G有向，則有
岔激。即勒极，n個(gè)頂點(diǎn)的圖，其邊數(shù)為
虑鼎。
說(shuō)明：用排列辱匿、組合的思路解決键痛。 - 圖G是無(wú)向圖，有n個(gè)頂點(diǎn)和m條邊
- 如果G聯(lián)通匾七，則
- 如果G是樹(shù)絮短，則
- 如果G是森林，則
- 如果G聯(lián)通匾七，則
Reference
1 Goodrich and etc., Data Structures and Algorithms in Python
