Problem kolorowania wierzchołków grafu.
Każdemu wierzchołkwi grafu przyporządkowujemy liczbę naturalną w taki sposób,
aby oba końce żadnej krawędzi nie miały przypisanej tej samej liczby.

Szukamy przyporządkowania wykorzystującego jak najmniej różnych liczb.

Powyżej treść problemu

Rozwiązanie poniżej...
problem jest w tym, że dla grafów ostatnich pojawia się dość duża liczba obrotów licznika.... Graph.Counter (jest taki counter)
Czy można ten algorytm jeszcze jakoś zoptymalizować dla poszczególnych klas grafów (wiem, że to NP-trudny problem). Algorytm musi być z powrotami...

[code]
using System.Collections.Generic ;
using System;

namespace ASD.Graph
{

public static class ColoringExtender
{

// koloruje graf algorytmem zachlannym (byc moze niepotymalnie)
public static int GreedyColor(this IGraph g, out int[] colors)
    {
    // kazdemu wierzcholkowi 
    // przydzielamy najmniejszy kolor nie kolidujacy z juz pokolorowanymi sasiadami
    // (wpisujemy go do tablicy colors)
    // zwracamy liczbe uzytych kolorow

        int n = g.VerticesCount;
        colors = new int[n];

        int nr_koloru = 1;
    
        for (int i = 0; i < n; i++)
        {
            HashSet<int> NodeColors = new HashSet<int>();
            foreach (Edge e in g.OutEdges(i))
            {
                int kolor = colors[e.To];
                if (!NodeColors.Contains(kolor) && kolor != 0)
                    NodeColors.Add(kolor);
            }
            if (NodeColors.Count == nr_koloru)
            {
                ++nr_koloru;
                colors[i] = nr_koloru;
            }
            else
            {
                for (int j = 1; j <= nr_koloru; j++)
                {
                    if (!NodeColors.Contains(j))
                    {
                        colors[i] = j;
                        break;
                    }
                }
            }
        }
    
    /* ZMIENIC */ //int k=g.VerticesCount;
    /* ZMIENIC */ //colors=new int[k];
    /* ZMIENIC */ //for ( int i=0 ; i<k ; ++i )
    /* ZMIENIC */ //    colors[i]=i+1;
        /* ZMIENIC */
        return nr_koloru;
    }

// koloruje graf algorytmem z powrotami (optymalnie)
public static int BacktrackingColor(this IGraph g, out int[] colors)
    {
    var gc = new Coloring(g);
    /*
    int EdgesCountFull = -1;
    if (g.Directed)
        EdgesCountFull = g.VerticesCount * (g.VerticesCount - 1);
    else
        EdgesCountFull = g.VerticesCount * (g.VerticesCount - 1) / 2;

    if (g.EdgesCount == EdgesCountFull)
    {
        colors = new int[g.VerticesCount];
        int n = g.VerticesCount;
        for (int i = 1; i <= g.VerticesCount; i++)
            colors[i-1] = i;
        return n;
    }
    */
    gc.Color(0, new int[g.VerticesCount], 0);
    colors = gc.bestColors;

    return gc.bestColorsNumber;
    }

// klasa pomocnicza dla algorytmu z powrotami
private sealed class Coloring
    {
    
    // tablica pamietajaca najlepsze dotychczas znalezione pokolorowanie
    internal int[] bestColors=null;

    // zmienna pamietajaca liczbe kolorow w najlepszym dotychczas znalezionym pokolorowaniu
    internal int bestColorsNumber;

    // badany graf
    private IGraph g;
    
    // konstruktor
    internal Coloring(IGraph g)
        {
        this.g=g;
        bestColorsNumber=g.VerticesCount+1;
        }

    // rekurencyjna metoda znajdujaca najlepsze pokolorowanie
    // v - wierzcholek do pokolorowania
    // colors - tablica kolorow
    // n - liczba kolorow uzytych w pokolorowaniu zapisanym w colors
    internal void Color(int v ,int[] colors, int n)
        {
        // tu zaimplementowac algorytm z powrotami
        
        /* ZMIENIC */ //int k=g.VerticesCount;
        /* ZMIENIC */ //bestColors=new int[k];
        /* ZMIENIC */ //for ( int i=0 ; i<k ; ++i )
        /* ZMIENIC */ //    bestColors[i]=i+1;
        /* ZMIENIC */ //bestColorsNumber=k;
        
        //if (n >= colors.Length)
        //    throw new Exception("Coś się zwaliło");

        if (n >= bestColorsNumber)
            return;

        if (v >= g.VerticesCount)
        {
            if (n < bestColorsNumber)
            {
                bestColorsNumber = n;
                bestColors = (int[])colors.Clone();
              //  Console.WriteLine("ALA");
            }
            return;
        }

        HashSet<int> NodeColors = new HashSet<int>();
        foreach (Edge e in g.OutEdges(v))
        {
            if (e.To < v)
            {
                if (e.To == v)
                    throw new Exception();
                int color = colors[e.To];
                if (color != 0 && !NodeColors.Contains(color))
                    NodeColors.Add(color);
            }
        }

        if (n < NodeColors.Count)
            throw new Exception();

        int OutDegree = g.OutDegree(v);

        if (v % 2 == 0)
        {
            for (int i = 1; i <= n; i++)
                if (!NodeColors.Contains(i))
                {
                    colors[v] = i;
                    Color(v + 1, colors, n);
                }
        }
        else
        {
            for (int i = n; i >= 1; i--)
                if (!NodeColors.Contains(i))
                {
                    colors[v] = i;
                    Color(v + 1, colors, n);
                }
        }
            colors[v] = n + 1;
            Color(v + 1, colors, n + 1);
        

            //colors[v] = 0;

      

        }

    }  // class Coloring

}  // class ColoringExtender

} // namespace ASD.Graph

[/code]

main.cs
[code]

using System;
using ASD.Graph;

class Zad09
{
public static void Main()
{
int[] backtrackingColors;
int[] greedyColors;
int n,i,j,mb,mg;
long counter0, counter1, counter2;
string[] message1 = { "Zwykly maly graf:",
"Maly dwudzielny:",
"Mala klika:" };
int[] bestColorsNumbers1 = { 4, 2, 9 };
string[] message2 = { "Zwykly graf:",
"Graf dwudzielny:",
"Cykl parzysty:",
"Klika:" };
int[] bestColorsNumbers2 = { 6, 2, 2, 200 };
string[] message3 = { "Zwykly duzy graf:",
"Duzy dwudzielny:",
"Duza klika:" };
int[] bestColorsNumbers3 = { 59, 2, 4000 };
IGraph[] g1 = new IGraph[message1.Length];
IGraph[] g2 = new IGraph[message2.Length];
IGraph[] g3 = new IGraph[message3.Length];
var rgg = new RandomGraphGenerator();
//GraphExport ge = new GraphExport(true, "C:\Users\polgrabiat\Desktop\Graphviz2.26.3\Graphviz2.26.3\bin\dot.exe");

    Console.WriteLine();
    Console.WriteLine("Generowanie grafow");
    Console.WriteLine();

    rgg.SetSeed(101);
    g1[0] = rgg.UndirectedGraph(typeof(AdjacencyMatrixGraph),8,0.5);
    rgg.SetSeed(102);
    g1[1] = rgg.BipariteGraph(typeof(AdjacencyMatrixGraph),5,3,0.75);
    n=9;
    g1[2] = new AdjacencyMatrixGraph(false,n);
    for ( i=0 ; i<n ; ++i )
        for ( j=i+1 ; j<n ; ++ j )
            g1[2].AddEdge(i,j);

    rgg.SetSeed(103);
    g2[0] = rgg.UndirectedGraph(typeof(AdjacencyMatrixGraph), 20, 0.5);
    rgg.SetSeed(104);
    g2[1] = rgg.BipariteGraph(typeof(AdjacencyMatrixGraph), 30, 20, 0.25);
    n = 50;
    g2[2] = new AdjacencyListsGraph(false, n);
    for (i = 1; i < n; ++i)
        g2[2].AddEdge(i - 1, i);
    g2[2].AddEdge(n - 1, 0);
    rgg.SetSeed(105);
    g2[2] = rgg.Permute(g2[2]);
    n = 200;
    g2[3] = new AdjacencyMatrixGraph(false, n);
    for (i = 0; i < n; ++i)
        for (j = i + 1; j < n; ++j)
            g2[3].AddEdge(i, j);

    rgg.SetSeed(106);
    g3[0] = rgg.UndirectedGraph(typeof(AdjacencyMatrixGraph), 75, 0.99);
    rgg.SetSeed(107);
    g3[1] = rgg.BipariteGraph(typeof(AdjacencyMatrixGraph), 2000, 2000, 0.55);
    n = 5000;
    g3[2] = new AdjacencyMatrixGraph(false, n);
    for (i = 0; i < n; ++i)
        for (j = i + 1; j < n; ++j)
            g3[2].AddEdge(i, j);

    //Console.WriteLine("{0}", g3[2].EdgesCount);
    
    Console.WriteLine();
    for ( i=0 ; i<g1.Length ; ++i )
        {
       //     ge.Export(g1[i], "ala");
        counter0=Graph.Counter;
        mb=g1[i].BacktrackingColor(out backtrackingColors);
        counter1=Graph.Counter;
        mg=g1[i].GreedyColor(out greedyColors);
        counter2=Graph.Counter;
        Console.WriteLine("{0,-17}  liczba wierzcholkow  {1,4},  optymalna liczba kolorow  {2,4}", message1[i], g1[i].VerticesCount, bestColorsNumbers1[i]);
        Console.WriteLine("  Backtracking:    liczba kolorow  {0,4},  zlozonosc  {1,8}", mb, counter1-counter0);
        Console.WriteLine("  Greedy:          liczba kolorow  {0,4},  zlozonosc  {1,8}", mg, counter2-counter1);
        Console.WriteLine();
        }

    Console.WriteLine();
    for (i = 0; i < g2.Length; ++i)
    {
        counter0 = Graph.Counter;
        mb = g2[i].BacktrackingColor(out backtrackingColors);
        counter1 = Graph.Counter;
        mg = g2[i].GreedyColor(out greedyColors);
        counter2 = Graph.Counter;
        Console.WriteLine("{0,-17}  liczba wierzcholkow  {1,4},  optymalna liczba kolorow  {2,4}", message2[i], g2[i].VerticesCount, bestColorsNumbers2[i]);
        Console.WriteLine("  Backtracking:    liczba kolorow  {0,4},  zlozonosc  {1,8}", mb, counter1 - counter0);
        Console.WriteLine("  Greedy:          liczba kolorow  {0,4},  zlozonosc  {1,8}", mg, counter2 - counter1);
        Console.WriteLine();
    }

    Console.WriteLine();
    for (i = 0; i < g3.Length; ++i)
    {
        counter0 = Graph.Counter;
        mb = g3[i].BacktrackingColor(out backtrackingColors);
        counter1 = Graph.Counter;
        mg = g3[i].GreedyColor(out greedyColors);
        counter2 = Graph.Counter;
        Console.WriteLine("{0,-17}  liczba wierzcholkow  {1,4},  optymalna liczba kolorow  {2,4}", message3[i], g3[i].VerticesCount, bestColorsNumbers3[i]);
        Console.WriteLine("  Backtracking:    liczba kolorow  {0,4},  zlozonosc  {1,8}", mb, counter1 - counter0);
        Console.WriteLine("  Greedy:          liczba kolorow  {0,4},  zlozonosc  {1,8}", mg, counter2 - counter1);
        Console.WriteLine();
    }

    Console.WriteLine("Koniec");
    Console.WriteLine();
    }

}

[/code]