Graph Färbung Algorithmus: typische Planungsproblem

Question

Ich trainiere Code Probleme wie UVA- und ich habe dieses eine, in der ich haben , eine Reihe von n Prüfungen gegeben und k Schüler in den Prüfungen eingeschrieben, ob es ist möglich, alle Prüfungen in zwei Zeitschlitzen zu planen.

Eingabe Mehrere Testfälle. Jeder beginnt mit einer Zeile, die n verschiedener Prüfungen geplant werden. Die zweite Linie hat die Zahl der Fälle k, in denen es existiert mindestens 1 Teilnehmer in zwei Prüfungen eingeschrieben. Dann werden k Linien folgen, die jeweils 2 Zahlen, die das Paar von Prüfungen für jeden Fall, der oben angegeben. (Ein Eingang mit n = 0 bedeutet Ende des Eingangs und soll nicht bearbeitet werden).

Ausgang: Sie müssen entscheiden, ob der Prüfungsplan ist möglich oder nicht für zwei Zeitschlitze.

Beispiel:

Eingang:

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 

Ouput:

NOT POSSIBLE. 
POSSIBLE. 

Ich denke, die allgemeine Ausrichtung Graphenfärbungs ist, aber ich bin wirklich ein newb und ich bekenne, dass Ich hatte Probleme, das Problem zu verstehen. Wie auch immer, ich versuche es zu tun und dann abschicken. Könnte mir bitte jemand helfen, Code für dieses Problem zu machen? Ich werde zu handhaben und diese algo verstehen jetzt, um es später zu verwenden, immer und immer wieder.

Ich ziehe C oder C++, aber wenn Sie wollen, ist Java gut zu mir;)

Vielen Dank im Voraus

Answer 1

Ich habe den Pseudocode des Polygenelubricants in JAVA-Code übersetzt, um eine Lösung für mein Problem zu finden. Wir haben eine Submission-Plattform (wie uva/ACM-Wettbewerbe), also weiß ich, dass es sogar in dem Problem mit mehr und härteren Fällen bestanden hat.

Hier ist sie:

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(); 
    } 
} 

ich noch nicht optimiert war, ich habe nicht die Zeit richtig neu, aber wenn Sie möchten, können Sie/können wir es hier diskutieren.

Ich hoffe, Sie genießen es! ;)

Answer 2

Sie sind richtig, dass dies ein Graphenfärbungsproblem ist. Insbesondere müssen Sie bestimmen, ob das Diagramm 2-färbbar ist. Das ist trivial: Machen Sie ein DFS auf dem Graphen und färben Sie abwechselnd schwarze und weiße Knoten. Wenn Sie einen Konflikt finden, ist das Diagramm nicht 2-färbbar und die Planung ist nicht möglich.

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) 

Dies läuft in O(|V| + |E|) mit Adjazenzliste.

Answer 3

In der Praxis stellt sich die Frage, ob man die n Untersuchungen in zwei Teilmengen A und B (zwei Zeitschlitze) aufteilen kann, so dass für jedes Paar in der Liste von k Untersuchungspaaren entweder a zu A gehört und b zu B gehört, oder a gehört zu B und B gehört zu A.

Sie haben Recht, dass es ein 2-Färbungsproblem ist; es ist ein Graph mit n Ecken und es gibt einen ungerichteten Bogen zwischen den Ecken a und b, wenn das Paar oder in der Liste erscheint. Dann stellt sich die Frage nach der 2-Färbbarkeit des Graphen, wobei die beiden Farben die Partition zu den Zeitschlitzen A und B bezeichnen.

Ein 2-färbbarer Graph ist ein "zweiteiliger Graph". Sie können die Zweiteilung leicht testen, siehe http://en.wikipedia.org/wiki/Bipartite_graph.