C++ 程序实现 Vizing 定理
c++server side programmingprogramming更新于 2024/10/25 1:15:00
Vizing 定理指出，简单图的色度指数可以是 maxdegree 或 maxdegree+1。这里，色度指数表示图的边缘着色所需的最大颜色。
这是一个 C++ 程序来实现 Vizing 定理。
算法
开始 以顶点和边的数量作为输入。 取边的顶点对。 函数 EdgeColor():为图的边缘着色。 1) 将当前边的颜色指定为 c，即初始为 1。 2) 如果任何一条相邻边占用相同的颜色， 则丢弃此颜色并再次转到标志并尝试下一种颜色。 结束
示例
#include<iostream>
using namespace std;
void EdgeColor(int ed[][3], int e) {
int i, c, j;
for(i = 0; i < e; i++) {
c = 1; //最初将颜色分配给当前边 1。
// 如果任何一条相邻边占用相同的颜色，
// 然后丢弃此颜色并再次转到标志并尝试下一个颜色。
flag:
ed[i][2] = c;
for(j = 0; j < e; j++) {
if(j == i)
continue;
if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
if(ed[j][2] == ed[i][2]) {
c++;
goto flag;
}
}
}
}
}
int main() {
int i, n, e, j, max = -1;
cout<<"输入图的顶点数:";
cin>>n;
cout<<"输入图的边数:";
cin>>e;
int ed[e][3], deg[n+1] = {0};
for(i = 0; i < e; i++) {
cout<<"\n输入边"<<i+1;的顶点对
cout<<"\nN(1): ";
cin>>ed[i][0];
cout<<"N(2): ";
cin>>ed[i][1];
//计算每个顶点的度数
ed[i][2] = -1;
deg[ed[i][0]]++;
deg[ed[i][1]]++;
}
//找出最大度数。
for(i = 1; i <= n; i++) {
if(max < deg[i])
max = deg[i];
}
EdgeColor(ed , e);
cout<<"\n根据 Vizing 定理，此图可以使用最大数量的 <<<max+1<<" 颜色来生成有效的边着色。\n\n";
for(i = 0; i < e; i++)
cout<<"\n顶点 N(1):<<ed[i][0]<<" 和 N(2):<<<ed[i][1]<<" 之间的边的颜色为:color<<<ed[i][2]<<"。";
}
输出
输入图的顶点数:4 输入图的边数:3 输入边 1 的顶点对 N(1): 1 N(2): 2 输入边 2 的顶点对 N(1): 3 N(2): 2 输入边 3 的顶点对 N(1): 4 N(2): 1 根据 Vizing 定理，此图最多可使用 3 种颜色来生成有效的边着色。 顶点 N(1):1 和 N(2):2 之间的边的颜色为:color1。 顶点 N(1):3 和 N(2):2 之间的边的颜色为:color2。 顶点 N(1):4 和 N(2):1 之间的边的颜色为:color2。
