sequential_vertex_coloring

[szablon funkcji] Algorytm kolorowania wierzchołków grafu.

Składnia

#include <boost/graph/sequential_vertex_coloring.hpp>

namespace boost
{
template < class VertexListGraph, class OrderPA, class ColorMap >
typename property_traits < ColorMap >::value_type
sequential_vertex_coloring
(
const VertexListGraph & G,
OrderPA order,
ColorMap color
);

template < class VertexListGraph, class ColorMap >
typename property_traits < ColorMap >::value_type
sequential_vertex_coloring
(
const VertexListGraph & G,
ColorMap color
);

}

Argumenty

Argument	Opis
const VertexListGraph& G	[wejście] Opis grafu - wierzchołki i krawędzie.
OrderPA order	[wejście] Tablica transformacji wierzchołków z dowolnej numeracji wierzchołków na numerację będącą zakresem wartości od 0 do g-1 włącznie, gdzie g jest liczbą wierzchołków występującą w grafie wejściowym.
ColorMap color	[wyjście] Kolory wierzchołków.

Zwracana wartość

Liczba kolorów użytych do pokolorowania grafu.

Opis szczegółowy

Funkcja koloruje wierzchołki grafu w taki sposób, że każda krawędź łącząca wierzchołki w grafie, łączy wierzchołki różnych kolorów. Algorytm stara się użyć przy tym minimalnej liczby kolorów, jednak nie gwarantuje on, że użyta liczba kolorów będzie optymalna. Problem optymalnego kolorowania grafów jest sklasyfikowany jako NP-trudny.

Dodatkowe informacje

Niniejsze pojęcie jeszcze nie zostało wyczerpująco przez nas opracowane. Więcej informacji na temat niniejszego hasła znajdziesz pod adresem http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/sequential_vertex_coloring.html.

Linki zewnętrzne

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/sequential_vertex_coloring.html

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.