[wytrzzeszcz]

#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)

jak poradzić sobie z problemem dodania i usunięcia pojedynczej krawędzi bez przesadnych obliczeń

[karer]

@wytrzzeszcz: zalezy co chcesz osiagnac i co rozumiesz przez przesadne obliczenia. Chcesz metode efektywna pamieciowo czy efektywna obliczeniowo? Chcesz uzywac grafu jako grafu czy tylko go przeanalizowac?

[wytrzzeszcz]

@karer: graf jest w #!$%@? wielki i siedzi w bazie danych. Raczej wolę małą złożoność czasową

[a.....y]

wieszchołka

@wytrzzeszcz: (╯︵╰,)

[karer]

graf jest w #!$%@? wielki

wolę małą złożoność czasową

@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.

[GotoFinal]

@karer: Albo najczęsciej spotykany wariant: wolno i dużo pamięci. ʕ•ᴥ•ʔ

[extern-int]

@karer: To nie zawsze jest prawda.
@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).

[karer]

To nie zawsze jest prawda.

@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.

[tell_me_more]

@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)

[extern-int]

@karer: Zależy od problemu, czasem problem można rozwiązać szybko i używając mało pamięci. Stwierdzenie, że szybko = dużo pamięci jest po prostu nie prawdziwe. To zbytnie uproszczenie rzeczywistości :)

[sasik520]

graf jest w #!$%@? wielki

@wytrzzeszcz: a jakieś bardziej konkretne wartości?

[wytrzzeszcz]

@sasik520: pare miljardow wieszcholkow
@tell_me_more: wyglada jak to co chce

[tell_me_more]

@wytrzzeszcz: jeszcze dodam, że jeśli zdecydujesz się zaznaczać na każdej krawędzi, czy jest mostem, to:

- 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ś)

[legolass]

@wytrzzeszcz:

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

[karer]

Zależy od problemu, czasem problem można rozwiązać szybko i używając mało pamięci. Stwierdzenie, że szybko = dużo pamięci jest po prostu nie prawdziwe. To zbytnie uproszczenie rzeczywistości :)

@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]

@karer: Żeby mieć wyniki w pamięci najpierw je musisz policzyć i je tam umieścić. Równie dobrze mogę udowodnić, że w czasie 10 milisekund mogę napisać ten komentarz. Wystarczy że go napisze a potem w ciągu 10 milisekund wcisnę "wyślij". Brak logiki w tym.

[karer]

Brak logiki w tym.

@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]

@karer: Wiem co to jest złożoność algorytmu, nie zawsze (a raczej rzadko) się ją liczy tak jak piszesz i twoje kolejne zdanie nie ma z tym nic wspólnego. Starasz się znaleźć nierealistyczny scenariusz na poparcie swojej tezy i nie wątpię że taki znajdziesz/znalazłeś. W praktyce nic nie działa tak jak to opisujesz.

[karer]

Starasz się znaleźć nierealistyczny scenariusz na poparcie swojej tezy i nie wątpię że taki znajdziesz/znalazłeś. W praktyce nic nie działa tak jak to opisujesz.

@extern-int: ale przeciez nie piszemy o praktyce. Tutaj chodzi o to ze pytajacy nie podal zadnych informacji ktore moglyby zawezic temat.