概念:
 
　　哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,（那么，问题来了，既然要回到起始点，是不是应该说除了起点以外的点通过一次且仅一次，而起点这个点，作为哈密顿回路的时候需要两次到达）就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.
 
　　与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关.
 
判定:
 
一:Dirac定理(充分条件)
 
　　设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在.(N/2指的是⌈N/2⌉,向上取整)，用
 
二:基本的必要条件
 
　　设图G=<V, E>是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图,则W(G-S)<=|S|成立.其中W(G-S)是G-S中联通分支数.
 
三:竞赛图(哈密顿通路)
 
　　N(N>=2)阶竞赛图一定存在哈密顿通路.
 
算法:
 
一:在Dirac定理的前提下构造哈密顿回路
 
过程:
 
　　1:任意找两个相邻的节点S和T,在其基础上扩展出一条尽量长的没有重复结点的路径.即如果S与结点v相邻,而且v不在路径S -> T上,则可以把该路径变成v -> S -> T,然后v成为新的S.从S和T分别向两头扩展,直到无法继续扩展为止,即所有与S或T相邻的节点都在路径S -> T上.
 
　　2:若S与T相邻,则路径S -> T形成了一个回路.
 
　　3:若S与T不相邻,可以构造出来一个回路.设路径S -> T上有k+2个节点,依次为S, v1, v2, ..., vk, T.可以证明存在节点vi(i属于[1, k]),满足vi与T相邻,且vi+1与S相邻.找到这个节点vi,把原路径变成S -> vi -> T -> vi+1 -> S,即形成了一个回路.
 
　　4:到此为止,已经构造出来了一个没有重复节点的的回路,如果其长度为N,则哈密顿回路就找到了.如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相邻.那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径.再按照步骤1的方法尽量扩展路径,则一定有新的节点被加进来.接着回到路径2.
 
证明:
 
　　可利用鸽巢原理（抽屉原理）证明.
 
抽屉原理
 
原理1： 把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
 
证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n×1，而不是题设的n+k(k≥1)，故不可能。
 
原理2：把多于mn(m乘n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
 
证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。
 
原理3：把无数还多件物体放入n个抽屉，则至少有一个抽屉里有无数个物体。
 
原理1 、2 、3都是第一抽屉原理的表述 [2]  。
 
 
第二抽屉原理
 
把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体(例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。
 
伪代码:
 
　　设s为哈密顿回路的起始点，t为哈密顿回路中终点s之前的点。ans[ ]为最终的哈密顿回路。倒置的意思指的是将数组对应的区间中数字的排列顺序方向。
 
　　1:初始化,令s = 1,t为s的任意一个邻接点.
 
　　2:如果ans[]中元素的个数小于n,则从t开始向外扩展,如果有可扩展点v,放入ans[]的尾部,并且t=v,并继续扩展,如无法扩展进入步骤3.
 
　　3:将当前得到的ans[]倒置,s和t互换,从t开始向外扩展,如果有可扩展点v,放入ans[]尾部,并且t=v,并继续扩展.如无法扩展进入步骤4.
 
　　4:如果当前s和t相邻,进入步骤5.否则,遍历ans[],寻找点ans[i],使得ans[i]与t相连并且ans[i +１]与ｓ相连,将从ans[i + 1]到t部分的ans[]倒置,t=ans[i +１],进如步骤5.
 
　　5:如果当前ans[]中元素的个数等于n,算法结束,ans[]中保存了哈密顿回路(可看情况是否加入点s).否则,如果s与t连通,但是ans[]中的元素的个数小于n,则遍历ans[],寻找点ans[i],使得ans[i]与ans[]外的一点(j)相连,则令s=ans[i - 1],t = j,将ans[]中s到ans[i - 1]部分的ans[]倒置,将ans[]中的ans[i]到t的部分倒置,将点j加入到ans[]的尾部,转步骤2.
 
时间复杂度:
 
　　如果说每次到步骤5算一轮的话,那么由于每一轮当中至少有一个节点被加入到路径S -> T中,所以总的轮数肯定不超过n轮,所以时间复杂度为O(n^2).空间上由于边数非常多,所以采用邻接矩阵来存储比较适合。
 
哈密顿回路代码
 
const int maxN = 1e2 + 7;
int ans[maxN], N;
inline void reverse(int l, int r)   //将l到r部分翻转
{
    while(l < r)
    {
        swap(ans[l], ans[r]);
        l++; r--;
    }
}
bool vis[maxN], mp[maxN][maxN];
void Hamilton()
{
    for(int i=1; i<=N; i++) vis[i] = false;
    int s = 1, t;//初始化取s为1号点
    int have_node = 2;
    int i, j;
    int w;
    for(i = 1; i <= N; i++) if(mp[s][i]) break;
    t = i;//取任意邻接与s的点为t
    vis[s] = vis[t] = true;
    ans[0] = s; ans[1] = t;
    while(true)
    {
        while(true) //从t向外扩展
        {
            for(i = 1; i <= N; i++){
                if(mp[t][i] && !vis[i]){
                    ans[have_node++] = i;
                    vis[i] = true;
                    t = i;
                    break;
                }
            }
            if(i > N) break;
        }
        w = have_node - 1;//将当前得到的序列倒置,s和t互换,从t继续扩展,相当于在原来的序列上从s向外扩展
        i = 0;
        reverse(i, w);
        swap(s, t);
        while(true) //从新的t继续向外扩展,相当于在原来的序列上从s向外扩展
        {
            for(i = 1; i <= N; i++){
                if(mp[t][i] && !vis[i]){
                    ans[have_node++] = i;
                    vis[i] = true;
                    t = i;
                    break;
                }
            }
            if(i > N) break;
        }
        if(!mp[s][t])   //如果s和t不相邻,进行调整
        {
            for(i = 1; i < have_node - 2; i++)   //取序列中的一点i,使得ans[i]与t相连,并且ans[i+1]与s相连
                if(mp[ans[i]][t] && mp[s][ans[i + 1]])break;
            w = have_node - 1;
            i++;
            t = ans[i];
            reverse(i, w);  //将从ans[i +１]到ｔ部分的ans[]倒置
        }   //此时s和t相连
        if(have_node == N) return;   //如果当前序列包含n个元素,算法结束
        for(j = 1; j <= N; j++)   //当前序列中元素的个数小于n,寻找点ans[i],使得ans[i]与ans[]外的一个点相连
        {
            if(vis[j]) continue;
            for(i = 1; i < have_node - 2; i++)if(mp[ans[i]][j])break;
            if(mp[ans[i]][j]) break;
        }
        s = ans[i - 1];
        t = j;  //将新找到的点j赋给t
        reverse(0, i - 1);  //将ans[]中s到ans[i-1]的部分倒置
        reverse(i, have_node - 1);   //将ans[]中ans[i]到t的部分倒置
        ans[have_node++] = j;    //将点j加入到ans[]尾部
        vis[j] = true;
    }
}
 
 
 
哈密顿通路
 
二:N(N>=2)阶竞赛图构造哈密顿通路
 
N阶竞赛图:含有N个顶点的有向图,且每对顶点之间都有一条边.对于N阶竞赛图一定存在哈密顿通路.
 
数学归纳法证明竞赛图在n >= 2时必存在哈密顿路:
 
(1)n = 2时结论显然成立；
 
(2)假设n = k时,结论也成立,哈密顿路为V1, V2, V3, ..., Vk;
 
  设当n = k+1时,第k + 1个节点为V(k+1),考虑到V(k+1)与Vi(1<=i<=k)的连通情况,可以分为以下两种情况.
 
    1:Vk与V(k+1)两点之间的弧为<Vk, V(k+1)>,则可构造哈密顿路径V1, V2,…, Vk, V(k+1).
 
    2:Vk与V(k+1)两点之间的弧为<V(k+1),Vk>,则从后往前寻找第一个出现的Vi(i=k-1,i>=1,--i),满足Vi与V(k+1)之间的弧为<Vi,V(k+1)>,则构造哈密顿路径V1, V2, …, Vi, V(k+1), V(i+1), …, V(k).若没找到满足条件的Vi,则说明对于所有的Vi(1<=i<=k)到V(k+1)的弧为<V(k+1),V(i)>,则构造哈密顿路径V(k+1), V1, V2, …, Vk.
 
证毕.
 
竞赛图构造哈密顿路时的算法同以上证明过程.
 
 
 
用图来说明:
 
假设此时已经存在路径V1 -> V2 -> V3 -> V4,这四个点与V5的连通情况有16种,给定由0/1组成的四个数,第i个数为0代表存在弧<V5,Vi>,反之为1,表示存在弧<Vi,V5>
 
 
sign[]={0, 0, 0, 0}.
 
很显然属于第二种情况,从后往前寻找不到1,即且不存在弧<Vi, V5>.
 
则构造哈密顿路:V5 -> V1 -> V2 -> V3 -> V4.
 
 
 
 
 
 
sign[]={0, 0, 0, 1}.
 
属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)
 
则构造哈密顿路: V1 -> V2 -> V3 -> V4 -> V5.
 
 
 
 
 
 
 
 
sign[]={0, 0, 1, 0}.
 
属于第二种情况,从后往前找到1出现的第一个位置为3.
 
构造哈密顿路: V1 -> V2 -> V3 -> V5 -> V4.
 
 
 
 
 
 
 
 
sign[]={0, 0, 1, 1}.
 
属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)
 
则构造哈密顿路: V1 -> V2 -> V3 -> V4 -> V5.
 
 
 
 
 
 
 
 
sign[]={0, 1, 0, 0}.
 
属于第二种情况,从后往前找到1出现的第一个位置为2.
 
构造哈密顿路: V1 -> V2 -> V5 -> V3-> V4.
 
 
 
 
 
 
 
 
sign[]={0, 1, 0, 1}.
 
属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)
 
则构造哈密顿路:V1 -> V2 -> V3 -> V4 -> V5.(就不举末尾为1的栗子了~~)
 
 
 
 
 
 
 
 
sign[]={1, 0, 1, 0}.
 
属于第二种情况,从后往前找到1出现的第一个位置为3.
 
构造哈密顿路: V1 -> V2 -> V3 -> V5-> V4.
 
 
 
 
 
 
 
 
sign[]={1, 1, 1, 0}.
 
属于第二种情况,从后往前找到1出现的第一个位置为3.
 
构造哈密顿路: V1 -> V2 -> V3 -> V5-> V4.
 
 
 
 
 
 
 
 
(还是举一个吧~~~)
 
sign[]={1, 1, 1, 1}.
 
同样最后一位为1,代表存在<Vi, V5>且i=4(最后一位)
 
则构造哈密顿路:V1 -> V2 -> V3 -> V4 -> V5.以上是当N=4时(N+1=5),用图来阐述算法的过程.
 
注意从后往前找不是找这个点编号之前的点,即不是按照编号来的,而是按照当前哈密顿序列从后往前找的.举个栗子:
 
4
 
2 1
 
1 3
 
3 2
 
4 1
 
4 2
 
4 3
 
第一步ans={1}
 
第二步ans={2,1}
 
第三步sign={0, 1}(map[3][2] = 0,map[3][1] = 1,当前序列为2,1) ,而不是{1, 0}(1,2),因为存在弧<V1, V3>和<V3, V2>.这里需要注意下.
 
代码：
 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e2 + 7;
int ans[maxN], mp[maxN][maxN], N;
inline void Insert(int &len, int l, int r)    //The ans[] length is len, insert key befor arv[index]
{
    len++;
    for(int i=r; i>=l; i--)
    {
        ans[i + 1] = ans[i];
    }
    ans[l] = len;
}
void Hamilton()
{
    int have_node = 0;
    ans[++have_node] = 1;
    for(int i = 2; i <= N; i++) //插入点i
    {
        if(mp[ans[have_node]][i]) ans[++have_node] = i; //第一种情况,直接把当前点添加到序列末尾
        else
        {
            bool flag = false;
            for(int j = have_node - 1; j; j--)   //在当前序列中,从后往前找到第一个满足条件的点j,使得存在<Vj,Vi>且<Vi, Vj+1>.
            {
                if(mp[ans[j]][i])  //找到后把该点插入到序列的第j + 1个点前.
                {
                    flag = true;
                    Insert(have_node, j + 1, have_node);
                    break;
                }
            }
            if(!flag) Insert(have_node, 1, have_node);    //否则说明所有点都邻接自点i,则把该点直接插入到序列首端.
        }
    }
}

int main()
{
    int t; scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &N);
        memset(mp, 0, sizeof(mp));
        int M = N * (N - 1) / 2;
        for(int i = 0; i < M; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            mp[u][v] = 1;
        }
        Hamilton();
        for(int i = 1; i <= N; i++) printf(i == 1 ? "%d":" %d", ans[i]);
        printf("\n");
    }
    return 0;
}
 
 

竞赛图
 
竞赛图是通过在无向完整图中为每个边缘分配方向而获得的有向图（有向图）。 也就是说，它是一个完整图形的方向，等价于一个有向图，其中每对不同的顶点通过单个有向边连接，即每对顶点之间都有一条边相连的有向图称为竞赛图。
 
总的概括就是一个有向完全图。
 
与哈密顿路径的关系
 
任何有限数量n个顶点的竞赛图都包含一个哈密尔顿路径，即所有n个顶点上的直线路径。假设该语句适用于n，并考虑n + 1个顶点上的任何竞赛图T。 选择T的顶点v0，并考虑 的一个有向路径 。现在让 是最大的，所以对于每个 都有一个从 到 的有向边。
 
哈密顿图
 
 
哈密顿通路 ：设G=<V,E>为一图（无向图或有向图）.G中经过每个顶点一次且仅一次的通路称作哈密顿通路
 
 
哈密顿回路：G中经过每个顶点一次且仅一次的回路（通路基础上+回到起始点）称作哈密顿回路
 
 
哈密顿图：若G中存在哈密顿回路，则称它是哈密顿图
 
 
定义
 
（1）存在哈密顿通路（回路）的图一定是连通图；
 （2）哈密顿通路是初级通路，哈密顿回路是初级回路；
 （3）若G中存在哈密顿回路，则它一定存在哈密顿通路，反之不真（看课本的话，是必要条件，而不是充分条件，故不可反推！）
 （4）只有哈密顿通路，无哈密顿回路的图不叫哈密顿图；即，哈密顿图是回路
 
判定
 （1）设无向图 $G=<V,E>$ 为哈密顿图，$V1$是$V$的任意真子集，则 $p(G-V1)<=|V1|$
 
其中， $p(G-V1)$ 为 $G$ 中删除 $V1$ 后的所得图的联通分支数目， $|V1|$ 为 $V1$ 集合中包含的顶点个数。
 
【哈密顿图存在的必要条件】推论：有割点的图一定不是哈密顿图。
 
设 $v$ 是图中的割点，则 $p(G-v)>=2$ ,由上述定理知 $G$ 不是哈密顿图
 
好理解的吧，就是过去就过不来了，毕竟两块之间只有一条桥嘛。
 
（2）设 $G$ 是 $n(n>=3)$ 阶无向简单图，若对于 $G$ 中的每一对不相邻的顶点 $u,v$ ,均有 $d(u)+d(v)>=n-1$ 则 $G$ 中存在哈密顿通路。又若 $d(u)+d(v)>=n$ 则 $G$ 中存在哈密顿回路，即 $G$ 为哈密顿图。
 
【哈密顿图存在的充分条件，不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。
 
推论：设 $G$ 是 $n(n>=3)$ 阶无向简单图，若 $G$ 的最小度 $>=n/2$ ,则 $G$ 是哈密顿图。
 
由推论知，对于完全图 $K_n$ ,当 $n>=3$ 时，是哈密顿图，完全二部图$K_{r,s}$当 $r==s>=2$ 时是哈密顿图。
 
（3）在 $n(n>=2)$ 阶有向图 $D=<V,E>$ 中，如果略去所有有向边的方向，所得无向图中含生成子图 $K_n$ ,则 $D$ 中存在哈密顿通路。
 
推论：n(n>=3)阶有向完全图是哈密顿图。
 
常用方法判断是哈密顿图：
 
若能通过观察找出图G中的一条哈密顿回路，则G当然是哈密顿图。
若一个无向图G满足上述（2）中的条件，一个有向图D满足上述（3）的推论的条件，则G、D都是哈密顿图。
 
一道找哈密顿路径的例题
 
链接 https://nanti.jisuanke.com/t/43394
 
题意
 
给出一个 $n(n\le 500)$ 个点的有向图，任意两个点之间有且仅一条有向边。
 求一条不重复经过一个点的最长的简单路径。
 
做法
 
任意两个点之间有且仅一条有向边，这是一个竞赛图。
 竞赛图一定存在哈密顿路径，所以𝑛个点的竞赛图的不重复经过一个点的最长的简单路径的长度为𝑛。
 
我们可以根据如下方法构造一条哈密顿路径：
 
维护一个 list，整个 list 相当于当前维护的路径。
 
每次加入一个点𝑢， 若𝑢连向 list 中的所有点，则把𝑢加入 list 的头部。
若 list 中的所有点连向𝑢，则把𝑢加入 list 的尾部。
否则，list 维护的路径中一定存在一条边< 𝑣, 𝑤 >，且存在边< 𝑣, 𝑢 >, < 𝑢, 𝑤 >，于是把𝑢插入至𝑣和𝑤之间。
 
时间复杂度$O(N^2)$。
 
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++)
#define pb push_back
using namespace std;
const int maxn=505;
typedef long long ll;
typedef pair<int,int> pii;

list<int> L;
int mp[maxn][maxn];
int n;

int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        rep(i,1,n)rep(j,1,n) scanf("%d",&mp[i][j]);
        L.clear();
        L.push_front(1);
        rep(i,2,n){
            int Ci=0,Co=0;
            for(auto x:L){
                if(mp[x][i]) Co++;
                if(mp[i][x]) Ci++;
            }
            if(Co==i-1) L.push_back(i);
            else if(Ci==i-1) L.push_front(i);
            else {
                auto pre=L.begin();
                for(;pre!=L.end();pre++){
                    auto lat=pre; lat++;
                    if(lat==L.end()) break;
                    int p=*pre,l=*lat;
                    if(mp[p][i]&&mp[i][l]) break;
                }
                L.insert(++pre,i);
            }
        }
        int f=0;
        for(auto x: L){
            if(f) printf(" ");
            f=1;
            printf("%d",x);
        }
        printf("\n");
    }
    return 0;
}

 
哈密顿图与半哈密顿图
 
前言
一、半/哈密顿图定义
二、半/哈密顿图的必要条件
三、判别二部图是否为哈密顿图
四、判断哈密顿路的充分条件
五、图的闭包、竞赛图
六、哈密顿图的充要条件
七、旅行商问题

 
前言
 
提示：本文主要介绍哈密顿图和半哈密顿图的定义以及判定条件，文中的图片来源于杨映雪老师的ppt。
 
 
一、半/哈密顿图定义
 
1.哈密顿路：给定无向图G中，通过图中每个结点一次而且仅一次的路径。
 2.哈密顿回路：给定无向图G中，通过图中每个结点一次而且仅一次的回路。
 3.哈密顿图：具有哈密顿回路的图。
 4.半哈密顿图：有哈密顿路径而没有哈密顿回路的图。哈密尔顿图和半哈密尔顿图是连通图。
 哈密顿图和欧拉图联系：两者都是遍历问题，但是欧拉图考虑的是边，而哈密顿考虑的是结点。同时判定欧拉图具有充要条件。但是哈密顿图没有简单的充要条件，只有必要条件和充分条件。
 
二、半/哈密顿图的必要条件
 
必要条件用于判定一个图不是半/哈密顿图。（p59）
 
定理1.设无向图G=<V,E>是哈密顿图，S是V的任意的非空真子集， ==w(G-S)≤|S| ==其中，w(G-S)为从G中删除S(删除S中各顶点及关联的边)后所得到的图的连通分支数。
 
证明：设C是G的一条哈密顿回路，C是G的子图，在回路C中每删去S的一个结点，最多增加一个连通分支，且删去S中的第一结点时分支数不变，所以有w(C-S)≤|S|。又因为C是G的生成子图，所有C-S是G-S的生成子图，且w(G-S)≤w(C-S),因此w(G-S)≤|S|
 
推论：设无向图G=<V,E>是半哈密顿图，则对于结点集V的任意非空真子集S均有w(G-S)≤|S| +1。
 
证明：设P是G中起始于u终止于v的哈密顿图，令G’=G∪(u,v) （在G的结点u，v之间添加新边），易知G’为哈密顿图。所以有 w(G-S)≤|S| ，则：
 w(G-S) = w(G’ - S - (u,v) ) ≤ w(G’-S) + 1 ≤ |S| +1
 
三、判别二部图是否为哈密顿图
 
一般情况下，设二部图G(V1,V2,E),|V1|≤|V2|,且|V1|≥2，|V2|≥2，由上述定理以及推论有：
 1.若G是哈密顿图，则|V1| = |V2|;
 2.图G是半哈密顿图，则|V2| = |V1| +1；
 3.若|V2| ≥ |V1| +2，则图G既不是哈密顿图，也不是半哈密顿图。
 
四、判断哈密顿路的充分条件
 
定理2：无向简单图G中任意两个不相邻的 结点度数之和 ≥ n-1，则图G中存在一条哈密顿路。图G是半哈密顿图。
 
 例题2：
 
 定理3：图G具有n个结点的无向简单图，如果图G中任意一对不相邻结点的度数之和 ≥ n，则G是哈密顿图
 
证明：由上述定理2知，图G一定是半哈密顿图，即存在一条哈密顿路F = V1V2V3…Vn。如果V1和Vn相邻，则F是哈密顿回路。如果不相邻，由定理2可知图G一定存在一条包含V1V2V3…Vn的回路，这个回路是哈密顿回路。所有图G是哈密顿图。
 
例题：
 
 
五、图的闭包、竞赛图
 
闭包：
 
 竞赛图：
 
竞赛图中每对不同的顶点通过单个有向边连接，即每对顶点间都有一条有向边。设 D 为 n 阶有向简单图，若 D 的基图为 n 阶无向完全图，则 D 为 n 阶竞赛图。简单来说，竞赛图就是将完全无向图的无向边给定了方向。
 
六、哈密顿图的充要条件
 

 
 
 
 
七、旅行商问题