Aktywne Wpisy
![JoeGlodomor](https://wykop.pl/cdn/c0834752/1bfcffa77eb980f1ab6133c792da81043282e82d4f938fa0598f193e3c52819f,q60.jpg)
JoeGlodomor +489
![Jacinda](https://wykop.pl/cdn/c3397992/Jacinda_uNVSsHNDQH,q60.jpg)
Jacinda +396
hej Mireczki, nie wiem czy jest ktoś tutaj co pamięta mój post sprzed sześciu lat, kiedy chwaliłam się wynikami z matury:
mój wpis z 2018
Przyszłam się pochwalić, że studia skończyłam, udało się bez żadnej obsuwy - jestem oficjalnie lekarzem (⌐ ͡■ ͜ʖ ͡■)
tera jeszcze trochę papierkowej roboty i
mój wpis z 2018
Przyszłam się pochwalić, że studia skończyłam, udało się bez żadnej obsuwy - jestem oficjalnie lekarzem (⌐ ͡■ ͜ʖ ͡■)
tera jeszcze trochę papierkowej roboty i
![Jacinda - hej Mireczki, nie wiem czy jest ktoś tutaj co pamięta mój post sprzed sześc...](https://wykop.pl/cdn/c3201142/ab9b0514b8007be4a30f35a966a7490b28cda0b90c9a2f661860a9cf3a1d04a8,w150.png?author=Jacinda&auth=8b6c8801457161947c14e76dafb669ad)
źródło: obraz
Pobierz
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)
jak poradzić sobie z problemem dodania i usunięcia pojedynczej krawędzi bez przesadnych obliczeń
@wytrzzeszcz: (╯︵╰,)
@wytrzzeszcz: Wiec bedziesz potrzebowal w #!$%@? wiecej pamieci operacyjnej niz zajmuje graf. Niska zlozonosc czasowa to wysoka zlozonosc pamieciowa. Zasada jest prosta albo szybko i duzo pamieci albo wolno i malo pamieci.
@wytrzzeszcz: Zgodnie z twoimi zasadami, to po prostu kolorujemy jednym kolorem składowe spójności. Czyli dodanie krawędzi miedzy u i v możesz zrealizować poprzez zamianę wszystkich wierzchołków, które mają kolor taki jak u na kolor wierzchołka v. Żeby zrealizować jakoś szybko usuwanie krawędzi musiałbyś coś dodatkowo zapamiętywać podczas konstrukcji tego grafu (o ile ten graf w ogóle jest konstruowany).
@extern-int: a kiedy nie jest w przypadku przeprowadzenia poprawnego algorytmu? #!$%@? mozna wszystko ale chyba nie chodzi ci o #!$%@? bo tego przypadku nie ma sensu nawet przytaczac bo rownie dobrze mozna zalozyc ze koles ktory bedzie to implementowal bedzie #!$%@? mlotkiem w monitor i zastanawial sie dlaczego kod sam sie nie pisze.
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)
@wytrzzeszcz: a jakieś bardziej konkretne wartości?
@tell_me_more: wyglada jak to co chce
- podczas dodawania krawędzi jeśli wierzchołki były różnych kolorów - ta nowa krawędź jest mostem
- jeśli były tego samego koloru to nowa krawędź nie jest mostem, ale musisz przeliczyć mosty w tej spójnej składowej (w tym kolorze)
- po usunięciu krawędzi trzeba zawsze przeliczyć mosty w tym kolorze (albo obu klorach jeśli podzieliłeś)
Czy ja dobrze rozumiem, że masz operację pokolorwania całego podgrafu na jeden kolor?
Dodanie krawędzi:
- Bierzesz jeden wierzchołek i zmieniasz kolor na kolor tego drugiego. Wtedy oba podgrafy są tego samego koloru, łączysz je i masz spójną składową tego
@extern-int: no masz racje ze czasem mozna rozwiazac szybko uzywajac malo pamieci ale to rozwiazanie nie bedzie nastawione na szybkosc bo jesli zuzyjesz wiecej pamieci to mozesz rozwiazac zadanie jeszcze szybciej. Chociazby trzymanie wynikow w pamieci a algorytmem bedzie tylko wyciagniecie ich
@extern-int: nie brak logiki bo zlozonosc algorytmow oblicza sie dla ilosci wywolan dazacej do nieskonczonosci w czasie. Dlatego jesli robisz cos tylko raz to wiecej czasu zajmie ci implementacja algorytmu niz jego wywolanie.
@extern-int: ale przeciez nie piszemy o praktyce. Tutaj chodzi o to ze pytajacy nie podal zadnych informacji ktore moglyby zawezic temat.