[Algorytmy] Kolorowanie krawędzi grafu

anka0501
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 22 sty 2011, o 20:33
Płeć: Kobieta
Lokalizacja: sjjdl
Podziękował: 1 raz

[Algorytmy] Kolorowanie krawędzi grafu

Post autor: anka0501 »

Cześć ! Mam problem z pewnym zadaniem i nie mam pojęcia jak się do tego zabrać, proszę o pomoc.
Oto treść:
Dany jest skończony graf niezorientowany. Zaproponuj algorytm kolorowania krawędzi tego grafu, w taki sposób, by krawędzie incydentne miały przyporządkowane różne kolory. Zastosuj metodę zachłanną konstrukcji algorytmu i postaraj się aby algorytm używał możliwie małej liczby kolorów. Czy Twoje rozwiązanie pozwala wyznaczyć minimalną liczbę kolorów konieczną do pokolorowania krawędzi grafu?
Ostatnio zmieniony 16 sty 2012, o 22:26 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Kolorowanie krawędzi grafu

Post autor: adambak »

a to nie jest jakieś NP-trudne? pewnie nie, bo z krawędziami jest zawsze łatwiej.. temat ciekawy, więc podbijam.. wpadnie Zordon to napewno napisze coś konkretnego
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[Algorytmy] Kolorowanie krawędzi grafu

Post autor: Zordon »

To jest NP-zupełne, chociaż wydaje się, że na temat kolorowania krawędzie wiadomo więcej niż na temat kolorowania wierzchołków (ale to tylko złudzenie ), gdyż mamy tw. Vizinga, które wyznacza indeks chromatyczny z dokładnością do 1.

Rozwiązanie o jakie pewnie chodzi autorowi zadania jest następujące:
Poczynając od wierzchołków o największym stopniu koloruj kolejno ich krawędzie używając zawsze koloru o najmniejszym możliwie numerze.
Oczywiście nie ma nadziei, że to zwraca optymalne kolorowanie, ale można się zastanawiać jak złe w stosunku do optymalnego może ono być.
anka0501
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 22 sty 2011, o 20:33
Płeć: Kobieta
Lokalizacja: sjjdl
Podziękował: 1 raz

[Algorytmy] Kolorowanie krawędzi grafu

Post autor: anka0501 »

A ja postanowiłam użyć algorytmu NTL. Nie wiem czy to dobre rozwiązanie (czy jest algorytmem zachłannnym ? wydaje mi się, że tak)...A czy zgodzicie się ze mną, jeśli napisze, że nie można w nim użyć najmniejszej liczby kolorów ?
ODPOWIEDZ