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/

do góry

On 17.06.2018 22:00, s...@g...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

do góry

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

do góry

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

do góry

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

N

do góry

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

do góry

On 18.06.2018 19:14, s...@g...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

do góry