algorytm.org

Kolorowanie grafu

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Kolorowanie grafu
Ocena użytkowników:***** / 35
SłabyŚwietny 
Wpisany przez Marek Rudolf, 02 listopada 2005 21:31

Kolorowanie grafu polega na przyporządkowaniu koloru każdemu węzłowi w grafie przy wykorzystaniu jak najmniejszej liczby kolorów(liczby chromatycznej). Jednakże przy założeniu, że dwa różne ale przyległe do siebie węzły nie będą miały tego samego koloru. Takie kolorowanie stosuje się często na mapach do oznaczenia terenów lub do określenia jak składować chemikalia bo jak wiadomo niektóre substancje po zetknięciu się ze sobą mogą spowodować eksplozje.

Algorytm działa w następujący sposób:

G-Graf;
nowy_kolor - zbiór kolorów użytych;
kolor=0;

Dopóki istnieją nie pokolorowane wierzchołki w G to
{
  nowy_kolor = pusty;
  kolor = kolor+1;
  V = pierwszy nie pokolorowany wierzchołek w G;
  Dopóki V nie jest puste to
  {
    jest_p = fałsz;
    W = pierwszy wierzchołek w zbiorze nowy_kolor;
    Dopóki W nie jest puste to
    {
      Jeżeli istnieje krawędź pomiędzy V i W w G to
      {
        jest_p = prawda;
      }
      W = następny wierzchołek w zbiorze nowy_kolor;
    }
    Jeżeli jest_p=fałsz to
    {
      oznacz V jako pokolorowany kolorem kolor;
      dołącz V do zbioru nowy_kolor;
    }
    V = następny nie pokolorowany wierzchołek w G;
  }
}


Przykład działania algorytmu:

Przykład kolorowania grafu




Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Marek RudolfC/C++Borland Builder 5
.cpp
.cpp
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2010 18:52
Komentarze
photo
-6 # ja 2010-02-19 21:05
to jest metodą w głąb?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz