离散数学-图论-欧拉图、哈密顿图、二部图、平面图（14）

客官°小女子只卖身不卖艺 2024-03-29 15:35 166阅读 0赞

### 欧拉图、哈密顿图、二部图、平面图 ###

### 1 欧拉图 ###

*  **无向图G**是**欧拉图** ⇔ \\Leftrightarrow ⇔G连通,且无奇度点。
 *  **无向图G**是**半欧拉图** ⇔ \\Leftrightarrow ⇔G连通,且仅有两个奇度点。
 *  **有向图G**是**欧拉图** ⇔ \\Leftrightarrow ⇔G强连通,且所有顶点的入度=出度。
 *  **有向图G**是**半欧拉图** ⇔ \\Leftrightarrow ⇔G单向连通,且仅有两个奇度点，其中一个顶点的出度-人度=1,另一个顶点的入度-出度=1,其余顶点的入度=出度。

![在这里插入图片描述][3fa643e7adda41348318e77c84e7c173.png]  
![在这里插入图片描述][ecb9372b632245aebf01b1efbfbe3741.png]

### 2 哈密顿图 ###

**定义：**

*  设G=<V，E>是**哈密顿图**，则对V的每个非空子集 V 1 V\_1 V1,均有下式成立: p ( G − V 1 ) ≤ ∣ V 1 ∣ p(G-V\_1) \\le|V\_1| p(G−V1)≤∣V1∣
 *  设G=<V，E>是**半哈密顿图**，则对V的每个非空子集 V 1 V\_1 V1,均有下式成立: p ( G − V 1 ) ≤ ∣ V 1 ∣ + 1 p(G-V\_1) \\le|V\_1|+1 p(G−V1)≤∣V1∣\+1

**判断方法：**  
（1）定义判断  
（2）G中存在**哈密顿回路**，是哈密顿图。（注意是哈密顿回路，不是哈密顿通路）G中存在**哈密顿通路路**，是半哈密顿图。  
![在这里插入图片描述][dff55f64b5bf41e19eb8913e89305695.png]  
![在这里插入图片描述][2e66d53130bd4e4197da637883104912.png]  
![在这里插入图片描述][5c8bf066e2ed40dcb0fbe5dc7e1a22a6.png]  
最中间的图存在哈密顿回路，则为哈密顿图，其他两边的只有哈密顿通路，则为半哈密顿图。

### 3 二部图 ###

![在这里插入图片描述][6ba6ec70d7c24427b13c96825db96421.png]

**判断二部图：** 无向图G=<V,E>是二部图 ⇔ \\Leftrightarrow ⇔G中 **无奇圈**。  
![在这里插入图片描述][3fe8b8044fd24f758dda669a33231ea9.png]  
图1存在奇度圈，图2，3都只有偶度圈，无奇圈。

### 4 平面图 ###

**定义：** 如果能将无向图G画在平面上使得除顶点处外无边相交，则称G是可平面图,简称**平面图**。画出的无边相交的图称为G的**平面嵌入**。无平面嵌入的图称为**非平面图**。  
![在这里插入图片描述][b69b8c54800949bb8e08a31e408ee1c9.png]  
![在这里插入图片描述][fab89c0a38074698acaf439227ec381f.png]  
![在这里插入图片描述][a68cc2912a2c41699e6335ad1be8b225.png]  
![在这里插入图片描述][bb19ed686a4a4f6c88bad8b144019ccb.png]

[3fa643e7adda41348318e77c84e7c173.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/795757b629574ad39c7397748d642bea.png
[ecb9372b632245aebf01b1efbfbe3741.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/488f93b728434372b80db9a5c08acec6.png
[dff55f64b5bf41e19eb8913e89305695.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/f933d48e0f924c52a476a59fdec3a96d.png
[2e66d53130bd4e4197da637883104912.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/14c564a33baa4e8ba1e19f77f8e42131.png
[5c8bf066e2ed40dcb0fbe5dc7e1a22a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/2ce16cf7238344cfab56f37d00f04265.png
[6ba6ec70d7c24427b13c96825db96421.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c68fd5de43a844268ed9eefaf32fdce9.png
[3fe8b8044fd24f758dda669a33231ea9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/182bb0af04624c8881cc84ef1f0494bc.png
[b69b8c54800949bb8e08a31e408ee1c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ac23ce1819ab4ea384b8019849e164e0.png
[fab89c0a38074698acaf439227ec381f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c22da4e9a33f4751aa7234e1a453c475.png
[a68cc2912a2c41699e6335ad1be8b225.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/bc83887520274f388253f332309bedca.png
[bb19ed686a4a4f6c88bad8b144019ccb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/3437f4d1f1494300afe09d3a99939be2.png