Wszystko

Wszystkie

Archiwum

wytrzzeszcz
wytrzzeszcz
  • 6
@92feliks: Drzewo – graf nieskierowany, który jest acykliczny i spójny, czyli taki graf, że z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność, brak możliwości chodzenia „w kółko”)[1].
  • Odpowiedz
wytrzzeszcz
wytrzzeszcz
  • 1
#programowanie #teoriagrafow #matematyka
mamy zadany graf który jest nie koniecznie spójny.
Jeśli z danego wieszchołka da się dojść po krawędziach do innego to oba muszą mieć ten sam kolor.
jesli nie da się przejść to kolor musza mieć różny. (czyli inaczej niż w standardowym problemie kolorowania grafu)

mamy 2 operacje drogą odwiedzenia wieszchołka i sprawdzenia z czym sąsiaduje i tanią w stosunku do wieschołka zmiany koloru wszystkich wieszchołków z jednego na 2. (Takie znajdz zamien w notatniku)
tell_me_more
tell_me_more
  • 2
@wytrzzeszcz: dodając krawędź możesz:

a) nic nie zmienić w kolorowaniu, jeśli krawędź ma oba wierzchołki tego samego koloru
b) połączyć 2 spójne składowe (kolory) w 1 (jeśli oba wierzchołki dodawanej krawędzi były innych kolorów)
  • Odpowiedz
wonsz_smieszek
wonsz_smieszek
  • 1
@MatexN: tak, zachłanne algorytmy kolorowania polegają po prostu na tym, że bierzesz kolejne wierzchołki i starasz się pokolorować używając jak najmniejszej liczby kolorów. Czyli kolorujesz kolorem 1 dopóki się da (nie ma krawędzi łączącej dwa wierzchołki o tym samym kolorze). Jak się nie da, to kolejny wierzchołek kolorem 2. Potem kolejny próbujesz znów kolorem 1, jak się nie da, to kolorem 2, jeżeli też się nie da, to wprowadzasz kolor
  • Odpowiedz
Marmite
Marmite
  • 5
Ej, mam w treści zadania o "problemie zanurzania grafu (z dylatacją 1)" - wiem czym jest zanurzanie grafu, ale za cholery nie mam pojęcia o co chodzi z tą dylatacją, ktoś wie? Sprawdzałem w google, ale wiadomo, że jak na 1. stronie czegoś nie ma, to to nie istnieje. #grafy #matematyka #teoriagrafow
Marmite
Marmite
  • 3
@anonim1133: Sama dylatacja to ja wiem czym jest, ale nie mam pojęcia jaki to ma związek z zanurzaniem grafu (i dlaczego akurat 1 - z późniejszego wyjaśnienia czym właściwie jest to zanurzanie z dylatacją 1:

dane są 2 grafy (G,H), G - gość, H - gospodarz. Czy istnieje odwzorowanie wierzchołków f: V(G) -> V(H) że każdej krawędzi {u,v} należącej do E(G) odpowiada krawędź {f(u), f(v)} należące do E(H)


nie wynika
  • Odpowiedz

Powiązane tagi