图论杂项

哈密顿图

定义

• 哈密顿路（通路）：无向图G中，通过图中每个结点一次而且仅一次的路径。
• 哈密顿回路：无向图G中，通过图中每个结点一次而且仅一次的回路。
• 哈密顿图：具有哈密顿回路的图。
• 半哈密顿图：有哈密顿路径而没有哈密顿回路的图。

推论

简单图 : 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图

• 图G具有n个结点的无向简单连通图，G中任意两个不相邻的结点度数之和 ≥ n-1，则G是半哈密顿图
• 图G具有n个结点的无向简单连通图，如果图G中任意一对不相邻结点的度数之和 ≥ n，则G是哈密顿图

判断哈密顿回路

例题：1122 Hamiltonian Cycle - PAT (Advanced Level) Practice (pintia.cn)

根据哈密顿回路的定义证明即可。

bool judge(){
	memset(vis,0,sizeof(vis));
	int cnt = 0;
	for(int i = 1 ; i < len ; i ++){
		if(!edge[v[i-1]][v[i]] || vis[v[i]]) return false;
		vis[v[i]] = true;
		cnt++;
	}
	return v[len-1] == v[0] && cnt == n;
}

一个可用于判断的必要条件：回路长度为n+1。

此外，还需要注意：编号是否在范围内；边是否存在 等

欧拉图

定义

• 欧拉（通路）路径：无向图G中，通过图中每个边一次而且仅一次的路径。
• 欧拉回路：无向图G中，通过图中每个边一次而且仅一次的回路。
• 欧拉图：具有欧拉回路的图。
• 半欧拉图：有欧拉路径而没有欧拉回路的图。

推论

• 图G是无向简单连通图，G中每个节点的度都为偶数，则G是欧拉图。
• 图G是无向简单连通图，G中恰好有两个节点的度数为奇数，其他节点的度数都是偶数（这两个奇数度的节点恰是所有欧拉回路的起点S和终点T）。

判断欧拉图

1126 Eulerian Path - PAT (Advanced Level) Practice (pintia.cn)

int judge(){
    //1-非欧拉图 2-半欧拉图 3-欧拉图
    
    //并查集判断是否连通
	int scc = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(i == find(i)) scc++;
	}
	if(scc != 1) return 1;
	
    //求奇数度的点的个数
	int cnt = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(d[i] % 2 != 0){
			cnt++;
		}
	}
	if(cnt == 0) return 3;
	if(cnt == 2) return 2;
    
	return 1;
}

完全子图（团）

定义

• 图G的团（完全子图）就是一个两两之间有边的顶点集合

• 极大团：增加任一顶点都不再符合团定义的团

• 最大团：顶点最多的极大团，称之为图G的

判断团

1142 Maximal Clique - PAT (Advanced Level) Practice (pintia.cn)

void solve(){
	memset(visited,0,sizeof(visited));
	cin>>k;
	v.clear();
	for(int i = 0 ; i < k ; i ++){
		int t;cin>>t;
		v.push_back(t);
		visited[t] = true;
	}
    //是否为完全子图
	for(int i = 0 ; i < k ; i ++){
		for(int j = 0 ; j < k ; j ++){
			if(j == i) continue;
			if(!edge[v[i]][v[j]]){
				cout<<"Not a Clique"<<endl;
				return;
			}
		}
	}
    //是否为极大完全子图
	for(int i = 1 ; i <= n ; i ++){
		if(visited[i]) continue;
		bool f = true;
		for(int j = 0 ; j < k ; j ++){
			if(!edge[v[j]][i]){
				f = false;
				break;
			}
		}
		if(f){
			cout<<"Not Maximal"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
}

旅行商环路（TSP）

定义

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路

给一张带权边的无向图G，求访问每个节点（可重复走边和点）的最短回路。

判断TSP

1150 Travelling Salesman Problem - PAT (Advanced Level) Practice (pintia.cn)

//检查是否能走通，并求路径长度
int dis = 0;
for(int i = 1 ; i < k ; i ++){
    if(dist[v[i-1]][v[i]] == INF){
        dis = -1;
        break;
    }else{
        dis += dist[v[i-1]][v[i]];
    }
}
if(dis == -1){
    cout<<"Path "<<x<<": NA"<<" (Not a TS cycle)"<<endl;
    return;
}

//检查是否为经过每个点的环
memset(visNode,0,sizeof(visNode));
int cnt = 0;
for(int i = 0 ; i < k ; i ++){
    if(!visNode[v[i]]){
        visNode[v[i]] = true;
        cnt++;
    }
}
if(v[0] != v[k-1] || cnt != n){
    cout<<"Path "<<x<<": "<<dis<<" (Not a TS cycle)"<<endl;
    return;
}

//检查是否存在重边
memset(visEdge,0,sizeof(visEdge));
bool isSimple = true;
for(int i = 1 ; i < k ; i ++){
    if(visEdge[v[i]][v[i-1]] || v[i] == v[i-1]){
        isSimple = false;
        break;
    }
    visEdge[v[i]][v[i-1]] = visEdge[v[i-1]][v[i]] = true;
}
if(isSimple){
    cout<<"Path "<<x<<": "<<dis<<" (TS simple cycle)"<<endl;
}else{
    cout<<"Path "<<x<<": "<<dis<<" (TS cycle)"<<endl;
}