Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #31594 > unrolled thread

Planowanie egzaminów jako problem kolorowania grafu

Back to article view | Back to pl.comp.programming

Contents

  Planowanie egzaminów jako problem kolorowania grafu szykcech@gmail.com - 2018-06-17 13:00 -0700
    Re: Planowanie egzaminów jako problem kolorowania grafu bartekltg <bartekltg@gmail.com> - 2018-06-17 22:49 +0200
      Re: Planowanie egzaminów jako problem kolorowania grafu szykcech@gmail.com - 2018-06-17 21:40 -0700
        Re: Planowanie egzaminów jako problem kolorowania grafu bartekltg <bartekltg@gmail.com> - 2018-06-18 16:39 +0200
          Re: Planowanie egzaminów jako problem kolorowania grafu szykcech@gmail.com - 2018-06-18 09:58 -0700
          Re: Planowanie egzaminów jako problem kolorowania grafu szykcech@gmail.com - 2018-06-18 10:14 -0700
            Re: Planowanie egzaminów jako problem kolorowania grafu bartekltg <bartekltg@gmail.com> - 2018-06-19 16:33 +0200

#31594 — Planowanie egzaminów jako problem kolorowania grafu

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?!?
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.

z góry dzięki i pozdro
Szyk Cech
--
http://szyk.jcom.pl/
http://szyk.free.of.pl/
http://szykcech.cba.pl/
http://szyk.000webhostapp.com/
http://www.geocities.ws/szyk/
http://szyk.wex.pl/

[toc] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#31596

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

[toc] | [prev] | [next] | [standalone]

#31597

On 18.06.2018 06:40, szykcech@gmail.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

[toc] | [prev] | [next] | [standalone]

#31598

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

N

[toc] | [prev] | [next] | [standalone]

#31599

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

Cytat:
"Aby wyrazić powyższy problem za pomocą grafu, przypiszemy jednemu wierzchołkowi jeden egzamin oraz wstawimy krawędź między dwa wierzchołki, dla których ma miejsce konflikt, tzn. gdy istnieje osoba zdająca egzaminy odpowiadające obu końcom krawędzi."

Już wiem co ten pacan miał na myśli: węzły to egzaminy, a krawędzie to studenci podchodzący do danych dwóch egzaminów (nie tylko wtedy gdy ma miejsce konflikt). Można się zdenerwować czytając takie książki! Całe szczęście są jeszcze grupy dyskusyjne, więc jest się kogo spytać.

Dzięki Bartek za wyjaśnienia.

[toc] | [prev] | [next] | [standalone]

#31600

On 18.06.2018 19:14, szykcech@gmail.com wrote:
>> Krawędzie to NIE konflikty. Przeczytaj poprzedniego posta dokładniej.
> 
> Cytat:
> "Aby wyrazić powyższy problem za pomocą grafu, przypiszemy jednemu wierzchołkowi jeden egzamin oraz wstawimy krawędź między dwa wierzchołki, dla których ma miejsce konflikt, tzn. gdy istnieje osoba zdająca egzaminy odpowiadające obu końcom krawędzi."
> 
> Już wiem co ten pacan miał na myśli: węzły to egzaminy, a krawędzie to studenci podchodzący do danych dwóch egzaminów 
>(nie tylko wtedy gdy ma miejsce konflikt). Można się zdenerwować czytając takie książki! Całe szczęście są jeszcze grupy dyskusyjne, więc jest się kogo spytać.

Eee, napisał wyraźnie.

"dla których ma miejsce konflikt" tzn."

I teraz mastępuje definicja "konfliktu"

"gdy istnieje osoba zdająca egzaminy odpowiadające obu końcom krawędzi."

To, że nie doczytałeś zdania do końca, tylko uznałęś że "konflikt", 
znaczy "nakąłdające się egzaminy" nie oznacza, że on pacan;>

Programowanie to jak matematyka i prawo. Każdy wyraz ważny;-)

pzdr
bartekltg

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web