图论

清疚 2022-09-25 15:21 258阅读 0赞

http://[blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_article_details_52518118]

## 最大团    ##

给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。

### 完全子图complete subgraph    ###

如果U∈V，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图。也就是如果图X中的任意两个节点均由一条边连接，那么X上的子图是完全子图。

### 团 ###

G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。

### 最大团 ###

G的最大团是指G中所含顶点数最多的团。[  
][Link 1]

[皮皮blog][Link 1]

## 连通图 ##

在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点 v i \{\\displaystyle v\_\{i\}\} ![v\_i][v_i]到顶点 v j \{\\displaystyle v\_\{j\}\} ![v\_\{j\}][v_j]有路径相连（当然从 v j \{\\displaystyle v\_\{j\}\} ![v\_\{j\}][v_j]到 v i \{\\displaystyle v\_\{i\}\} ![v\_i][v_i]也一定有路径），则称 v i \{\\displaystyle v\_\{i\}\} ![v\_i][v_i]和 v j \{\\displaystyle v\_\{j\}\} ![v\_\{j\}][v_j]是连通的。如果G是有向图，那么连接 v i \{\\displaystyle v\_\{i\}\} ![v\_i][v_i]和 v j \{\\displaystyle v\_\{j\}\} ![v\_\{j\}][v_j]的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。

### 相关概念    ###

**连通分量**：无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

**强连通图**：有向图G= (V,E)中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图（Strongly Connected Graph）。相应地有强连通分量（Strongly Connected Component）的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量。

**弱连通图**：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

**初级通路**：通路中所有的顶点互不相同。初级通路必为简单通路，但反之不真。

### 性质 ###

一个无向图G= (V,E)是连通的，那么边的数目大于等于顶点的数目减一： | E | ≥ | V | − 1 \{\\displaystyle |E|\\geq |V|-1\} ![\{\\displaystyle |E|\\geq |V|-1\}][displaystyle _E_geq _V_-1]，而反之不成立。

如果G= (V,E)是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目： | E | ≥ | V | \{\\displaystyle |E|\\geq |V|\} ![\{\\displaystyle |E|\\geq |V|\}][displaystyle _E_geq _V]，而反之不成立。

没有回路的无向图是连通的当且仅当它是树，即等价于： | E | = | V | − 1 \{\\displaystyle \\displaystyle |E|=|V|-1\} ![\{\\displaystyle \\displaystyle |E|=|V|-1\}][displaystyle _displaystyle _E_V_-1]。

\[ [wikipedia连通图][wikipedia]\]

from: [http://blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_article_details_52518118]

ref:

[blog.csdn.net_pipisorry_article_details_52518118]: http://blog.csdn.net/pipisorry/article/details/52518118
[Link 1]: http://blog.csdn.net/pipisorry
[v_i]: https://wikimedia.org/api/rest_v1/media/math/render/svg/7dffe5726650f6daac54829972a94f38eb8ec127
[v_j]: https://wikimedia.org/api/rest_v1/media/math/render/svg/73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5
[displaystyle _E_geq _V_-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/085d6b8c5e7103c19a7a1944c126942b4e176d6e
[displaystyle _E_geq _V]: https://wikimedia.org/api/rest_v1/media/math/render/svg/1831ce3a2f8c3be1d772944b4c06f5a0e8fa30fc
[displaystyle _displaystyle _E_V_-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/a9d05785eef65460568e6e72bb8b144ad1f0745f
[wikipedia]: https://zh.wikipedia.org/zh-hans/%E8%BF%9E%E9%80%9A%E5%9B%BE