图着色算法:典型的调度问题

Question

我正在训练代码问题，比如UvA，我有这个问题，如果有一组n考试和k学生报名参加考试，我必须找到是否有可能在2时隙中安排所有的考试。

输入几个测试用例。每一次检查都从一条包含1 的行开始，该行将安排不同的考试。第二行为k，其中至少有1名学生参加了2次考试。然后，k行将跟随，每一行包含2个数字，指定上述每一种情况的一对考试。(n=0的输入意味着输入的结束，不被处理)。

输出：--您必须决定考试计划是否为，对于2个时隙，是否可行。

示例：

输入：

3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

输出：

NOT POSSIBLE.
POSSIBLE.

我认为一般的方法是图着色，但我真的是个新手，我可能承认我在理解这个问题上遇到了一些困难。不管怎么说，我正试着去做然后提交。有人能帮我做些关于这个问题的代码吗？我将不得不处理和理解这个algo，以便以后，一遍又一遍地使用它。

我更喜欢C或C++，但是如果你愿意的话，Java对我来说很好;)

提前感谢

Answer 1

我已经将多源洗脱剂的伪代码翻译成JAVA代码，以便为我的问题提供一个解决方案。我们有一个提交平台(比如uva/ACM竞赛)，所以我知道即使在有更多和最困难的情况下，它也通过了。

下面是：

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Scanner;

/**
 *
 * @author newba
 */
public class GraphProblem {

    class Edge {
        int v1;
        int v2;

        public Edge(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }
    }

    public GraphProblem () {
        Scanner cin = new Scanner(System.in);

        while (cin.hasNext()) {

            int num_exams = cin.nextInt();
            if (num_exams == 0)
                break;
            int k = cin.nextInt();
            Hashtable<Integer,String> exams = new Hashtable<Integer, String>();
            ArrayList<Edge> edges = new ArrayList<Edge>();
            for (int i = 0; i < k; i++) {
                int v1 = cin.nextInt();
                int v2 = cin.nextInt();
                exams.put(v1,"UNKNOWN");
                exams.put(v2,"UNKNOWN");
                //add the edge from A->B and B->A
                edges.add(new Edge(v1, v2));
                edges.add(new Edge(v2, v1));
            }

            boolean possible = true;
            for (Integer key: exams.keySet()){
                if (exams.get(key).equals("UNKNOWN")){
                    if (!colorify(edges, exams,key, "BLACK", "WHITE")){
                        possible = false;
                        break;
                    }
                }
            }

            if (possible)
                System.out.println("POSSIBLE.");
            else
                System.out.println("NOT POSSIBLE.");

        }
    }

    public boolean colorify (ArrayList<Edge> edges,Hashtable<Integer,String> verticesHash,Integer node, String color1, String color2){

        verticesHash.put(node,color1);
        for (Edge edge : edges){
            if (edge.v1 == (int) node) {
                if (verticesHash.get(edge.v2).equals(color1)){
                    return false;
                }
                if (verticesHash.get(edge.v2).equals("UNKNOWN")){
                    colorify(edges, verticesHash, edge.v2, color2, color1);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        new GraphProblem();
    }
}

我还没有优化，我没有时间正确的新，但如果你想，你/我们可以在这里讨论它。

希望你喜欢它！)

Answer 2

你是对的，这是一个图着色问题。具体来说，你需要确定这个图形是否是2-可着色的.这很简单:在图上做一个DFS，对黑白节点进行着色。如果你发现一个冲突，那么这个图就不是2色的，调度也是不可能的。

possible = true

for all vertex V
  color[V] = UNKNOWN

for all vertex V
  if color[V] == UNKNOWN
    colorify(V, BLACK, WHITE)

procedure colorify(V, C1, C2)
  color[V] = C1
  for all edge (V, V2)
    if color[V2] == C1
      possible = false
    if color[V2] == UNKNOWN
      colorify(V2, C2, C1)

这是在O(|V| + |E|)中运行的邻接列表。

Answer 3

在实践中，问题是，如果你能将n个考试划分成两个子集A和B(两个时隙)，使得在k对中的每一对，要么a属于A和b属于B，要么a属于B和b属于A。

你是对的，这是一个2-着色问题；它是一个有n个顶点的图，在点a和b之间有一个无向的弧线当且仅当这对图或出现在列表中。然后，问题是关于图的2-可着色性，这两种颜色表示对时隙A和B的分割。

2-可着色图是“二部图”。您可以很容易地测试两分区性，请参阅http://en.wikipedia.org/wiki/Bipartite_graph。