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?
[Algorytmy] Kolorowanie krawędzi grafu
-
- 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
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.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
-
- 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
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
- Zordon
- 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
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ć.
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ć.
-
- 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
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 ?