Path: csiph.com!weretis.net!feeder4.news.weretis.net!news.unit0.net!news.nask.pl!news.nask.org.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail From: bartekltg Newsgroups: pl.comp.programming Subject: =?UTF-8?Q?Re:_Planowanie_egzamin=c3=b3w_jako_problem_kolorowania_gr?= =?UTF-8?Q?afu?= Date: Sun, 17 Jun 2018 22:49:16 +0200 Organization: ATMAN - ATM S.A. Lines: 24 Message-ID: References: NNTP-Posting-Host: 89-70-113-215.dynamic.chello.pl Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: node2.news.atman.pl 1529268556 8631 89.70.113.215 (17 Jun 2018 20:49:16 GMT) X-Complaints-To: usenet@atman.pl NNTP-Posting-Date: Sun, 17 Jun 2018 20:49:16 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 In-Reply-To: Content-Language: en-GB Xref: csiph.com pl.comp.programming:31595 On 17.06.2018 22:00, szykcech@gmail.com wrote: > Witam > Czytam sobie o grafach i próbuję coś z tego zrozumieć... > Pierwszy przykład zastosowania grafu jest oczywisty: pokolorować mapę polityczną. > Ok. > Drugi przykład daje już mi więcej do myślenia - dotyczy on sprowadzenia planowania egzaminów studentom do kolorowania grafu. W tym zagadnieniu węzłami są egzaminy, a krawędzie między nimi rysujemy tylko wtedy gdy jakiemuś studentowi wypadną 2 nakładające się na siebie egzaminy. > Ok. > Autor twierdzi, że to jest również problem kolorowania grafu. > Teraz moje pytanie jest takie: > Czy aby nie jest tak, że w tym grafie będziemy brać pod uwagę tylko sytuacje konfilktowe?!? Nie, Wpisujesz wszystkie potencjalne konflikty, 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. > 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. pzdr bartekltg