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

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

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

1 欧拉图

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

在这里插入图片描述
在这里插入图片描述

2 哈密顿图

定义：

  • 设G=是哈密顿图，则对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的每个非空子集 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中存在哈密顿通路路，是半哈密顿图。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
最中间的图存在哈密顿回路，则为哈密顿图，其他两边的只有哈密顿通路，则为半哈密顿图。

3 二部图

在这里插入图片描述

判断二部图： 无向图G=是二部图 ⇔ \Leftrightarrow ⇔G中 无奇圈。
在这里插入图片描述
图1存在奇度圈，图2，3都只有偶度圈，无奇圈。

4 平面图

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

发表评论

表情：
评论列表 （有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二部图

    多网站都喜欢让用户点击“喜欢/不喜欢”，“顶/反对”，也正是这种很简单的信息也可以利用起来对用户进行推荐！这里介绍一种基于网络结构的推荐系统！ 由于推荐系统深深植根于互...

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 180 阅读

    相关 关系图(关系图离散数学)

    仙剑关系图-提供仙剑1与3的关系图仙剑1与3的关系图 　　仙剑纪元： 　　前三十五年，神将飞蓬因与魔尊重楼在新仙界决战惊动天庭，被贬下世为人，名唤龙阳，为姜国太子。

    矫情吗；*矫情吗；*/ 0 赞/ 45 阅读

    相关 图论之欧拉图

    欧拉路径/欧拉回路 欧拉路径是一条经过图中所有边且只经过一次的路径（类似于一笔画问题）； 欧拉回路的话就是起点和终点相同的欧拉路径 欧拉通路（欧拉路径）：S点到T点的

    蔚落蔚落/ 0 赞/ 298 阅读