图的邻点可区别的边染色和分数染色的任务书.docx

图的邻点可区别的边染色和分数染色的任务书
任务书：
1.问题描述：
给定一张无向图G，定义每个顶点的邻点为与该顶点有边相连的所有顶点，现在需要对图G进行边染色或分数染色。
邻点可区别的边染色：要求对与每个顶点相邻的边进行染色，且相邻的边颜色不相同。
分数染色：要求对每条边进行染色，边染色时的分数为一个非负整数，且相邻的边颜色不相同。
请设计一个算法实现以上两种染色任务，使得染色后的图不存在相邻边重复染色的情况。
2.输入输出格式
输入格式：首先输入一个整数n表示图G中顶点的个数，接下来n行输入矩阵A[n][n]，其中A(i,j)=1表示顶点i与顶点j间有一条无向边，否则A(i,j)=0；
输出格式：输出若干行，表示染色后的图，每行表示一条边和它的颜色/分数，格式为“ijc/s”，i、j分别表示边的两个端点的编号，c/s分别表示边的染色结果为颜色/分数。边的顺序可以任意，只要满足不同颜色/分数的边不能相邻就可以。
3.输入样例：
输入样例说明：下面输入一个包含4个顶点的无向图，其邻接矩阵表示如下：
0110
1011
1101
0110
3.输出样例：
输出样例说明：染色后的图如下所示，其中颜色相同的边用相同的数字表示，分数相同的边用相同的数字表示。
011
022
123
134
235
246
347
4.算法设计
①邻点可区别的边染色：
该算法采用简单的贪心策略，从第一条边开始，依次染色，染色时优先选择没有使用过的最小颜色，如果所有颜色都已被使用，则新开辟一个颜色，重复操作直到所有边都染色。
②分数染色：
该算法同样采用贪心策略，从第一条边开始，依次给边染色，染色时选择当前未使用的最小分数，如果所有分数都已被使用，则新开辟一个分数，重复操作直到所有边都染色。
5.算法实现