23 lut 11:46
Bleee:
Ideks chromatyczny grafu G jest równy Δ(G) lub Δ(G) + 1.
Tak więc wystarczy zobaczyć czy wystarczy Δ(G) kolorów (zapewne tak) i wnioskować z tego.
23 lut 12:16
Karolina: Co to jest Δ(G)?
23 lut 13:05
Bleee:
Maksymalny stopień wierzcholka
23 lut 13:14
Karolina: Największa liczba wychodzących krawędzi z jednego wierzchołka ? Jeśli tak, to już rozumiem,
wtedy zakładamy że będą dwie opcje i uzasadnieniem jest już tylko rysunek z odpowiednim
pokolorowaniem.
23 lut 13:16
Karolina: Dziękuję bardzo
23 lut 13:16
Bleee:
Taka jeszcze wskazowka: większość grafów ma indeks chromatyczny równy Δ(G)
23 lut 13:18
Bleee:
A uzasadnieniem będzie pokolorawnie ilością Δ(G) lub wykazanie ze nie można taka ilością
pokolorować (pokolorowanie ilością Δ(G) +1 nie będzie uzasadnieniem
)
23 lut 13:20
Bleee:
Dodatkowo warto napisać na podstawie jakiego twierdzenia wiemy że indeks chromatyczny będzie ≤
Δ(G) + 1
23 lut 13:24
23 lut 13:29
Bleee:
Te litery w wierzchołkach to mam nadzieję że nie są kolory wierzchołków, jeżeli tak to zauważ
że w paru masz sąsiadujące wierzchołki o tym samym kolorze ((znalazłem dwa grafy z
siasadujacym kolorem B)
23 lut 13:33
wredulus_pospolitus:
A jeżeli potrafisz uzasadnić liczbę chromatyczną grafu, to:
− zauważ, że indeks chromatycznych grafu G będzie równy liczbie chromatycznej grafu brzegowego
tegoż grafu G.
23 lut 13:43
23 lut 13:45
Karolina: O uzasadnienie indeksu chromatycznego*
23 lut 13:45
wredulus_pospolitus:
tfu ... nie graf brzegowy tylko graf krawędziowy
23 lut 13:47
wredulus_pospolitus:
w (b) nadal masz dwa wierzchołki (B) połączone
zauważ, że (b) to graf pełny
23 lut 13:50
23 lut 14:02
Karolina: Teraz tylko jeszcze zostały uzasadnienia do tych indeksów chromatycznych z Δ(G)+1 (wszystkie te
przykłady są z Δ(G)+1)
23 lut 14:04
Karolina: Nie za bardzo rozumiem pojęcie grafu krawędziowego. A mogłabym poprosić o chociaż jeden
przykład uzasadniony odpowiednio żebym wiedziała na czym to polega?
23 lut 14:07
wredulus_pospolitus:
szczerze mówiąc ... nie pomogę Ci w tym
Ja bym próbował kolorować krawędzie grafów G, a nie przechodził do krawędziowych.
23 lut 14:32
Karolina: Trudno i tak bardzo dziękuję
23 lut 14:34
wredulus_pospolitus:
Niestety −−− potrzebowałbym teorii która zapewne była na wykładzie.
23 lut 14:43
