竞赛图
竞赛图是通过在无向完整图中为每个边缘分配方向而获得的有向图（有向图）。 也就是说，它是一个完整图形的方向，等价于一个有向图，其中每对不同的顶点通过单个有向边连接，即每对顶点之间都有一条边相连的有向图称为竞赛图。
- 总的概括就是一个有向完全图。
与哈密顿路径的关系
任何有限数量n个顶点的竞赛图都包含一个哈密尔顿路径，即所有n个顶点上的直线路径。假设该语句适用于n，并考虑n + 1个顶点上的任何竞赛图T。 选择T的顶点v0，并考虑 的一个有向路径 。现在让 是最大的，所以对于每个 都有一个从 到 的有向边。
哈密顿图
- 哈密顿通路 ：设G=
为一图（无向图或有向图）.G中经过每个顶点一次且仅一次的通路称作哈密顿通路
- 哈密顿回路：G中经过每个顶点一次且仅一次的回路（通路基础上+回到起始点）称作哈密顿回路
- 哈密顿图：若G中存在哈密顿回路，则称它是哈密顿图
定义
判定
（1）设无向图 G = < V , E > G=
其中， p ( G − V 1 ) p(G-V1) p(G−V1) 为 G G G 中删除 V 1 V1 V1 后的所得图的联通分支数目， ∣ V 1 ∣ |V1| ∣V1∣ 为 V 1 V1 V1 集合中包含的顶点个数。
【哈密顿图存在的必要条件】推论：有割点的图一定不是哈密顿图。
设 v v v 是图中的割点，则 p ( G − v ) > = 2 p(G-v)>=2 p(G−v)>=2 ,由上述定理知 G G G 不是哈密顿图
好理解的吧，就是过去就过不来了，毕竟两块之间只有一条桥嘛。
（2）设 G G G 是 n ( n > = 3 ) n(n>=3) n(n>=3) 阶无向简单图，若对于 G G G 中的每一对不相邻的顶点 u , v u,v u,v ,均有 d ( u ) + d ( v ) > = n − 1 d(u)+d(v)>=n-1 d(u)+d(v)>=n−1 则 G G G 中存在哈密顿通路。又若 d ( u ) + d ( v ) > = n d(u)+d(v)>=n d(u)+d(v)>=n 则 G G G 中存在哈密顿回路，即 G G G 为哈密顿图。
【哈密顿图存在的充分条件，不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。
推论：设 G G G 是 n ( n > = 3 ) n(n>=3) n(n>=3) 阶无向简单图，若 G G G 的最小度 > = n / 2 >=n/2 >=n/2 ,则 G G G 是哈密顿图。
由推论知，对于完全图 K n K_n Kn ,当 n > = 3 n>=3 n>=3 时，是哈密顿图，完全二部图 K r , s K_{r,s} Kr,s当 r = = s > = 2 r==s>=2 r==s>=2 时是哈密顿图。
（3）在 n ( n > = 2 ) n(n>=2) n(n>=2) 阶有向图 D = < V , E > D=
推论：n(n>=3)阶有向完全图是哈密顿图。
常用方法判断是哈密顿图：
- 若能通过观察找出图G中的一条哈密顿回路，则G当然是哈密顿图。
- 若一个无向图G满足上述（2）中的条件，一个有向图D满足上述（3）的推论的条件，则G、D都是哈密顿图。
一道找哈密顿路径的例题
链接 https://nanti.jisuanke.com/t/43394
题意
给出一个 n ( n ≤ 500 ) n(n ≤ 500) n(n≤500) 个点的有向图，任意两个点之间有且仅一条有向边。
求一条不重复经过一个点的最长的简单路径。
做法
我们可以根据如下方法构造一条哈密顿路径：
维护一个 list，整个 list 相当于当前维护的路径。
- 每次加入一个点?， 若?连向 list 中的所有点，则把?加入 list 的头部。
- 若 list 中的所有点连向?，则把?加入 list 的尾部。
- 否则，list 维护的路径中一定存在一条边< ?, ? >，且存在边< ?, ? >, < ?, ? >，于是把?插入至?和?之间。
时间复杂度 O ( N 2 ) O(N^2) O(N2)。
#include
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/221625.html原文链接：https://javaforall.net
