On 18.06.2018 06:40, s...@g...com wrote:
>>> Czy znajdując rozwiązanie (pokolorowanie grafu) - czyli rozdzielenie sytuacji
konfliktowych - nie napotkamy nowych sytuacji konfliktowych?!? Które wymagałyby od
nas nowych krawędzi?!? Przecież tak może się dziać bez końca!!!
>>>
>>> Proszę o odpowiedź na moje wątpliwości.
>>
>> A czemu mamy napotkać? Przecież wszytskie potencjalne konflikty
>> już są w grafie.
>
> Chodzi mi o to, że np. mamy egzaminy między 8-12 i od 12-16 i konflikt 2 egzaminów
między 12-14, to jeśli znajdziemy rozwiązanie dla konfliktu 12-14 np. godzina 10, to
powstaje nowy konflikt...


Dlaczego?

Kolory to sloty (godziny).
Szukasz kolorowania, czyli przypiszani egzaminom godzin.

Jesli masz egzaminy

A 8-12
B 12-16
C 12-16 (ustaliłęś sloty na 4 godzinne, to się tego trzymajmy)
D 12-16

To nie możemy przesunać C ani D na 8-12, bo pomiędzy A i D oraz A i C
isntieje krawędź!

Krawędzie to NIE konflikty. Przeczytaj poprzedniego posta dokładniej.


> Chyba, że domyślnie szukamy rozwiązań poza zbiorem węzłów tego grafu... A wtedy
chyba dodajemy nowe węzły, tak by mieć graf bez krawędzi.

Nie. Wierzchołki to egzaminy. Kolory to godziny.
Krawędzie spełnaiją to co napsiałem:
>> Egzaminy A i B są połączone krawędzią, jeśli istnieje studfent S,
>> taki, że S ma egzamin A i S ma egzamin B.

pzdr
bartekltg