Indeks chromatyczny

[Karolinaa0]

Mam takie pytanie, ile wynosi indeks chromatyczny poniższych dwóch grafów z załącznika? Myślę że a)5 a b)6. Wiem na czym to polega, ale nie wiem jakie powinno być uzasadnienie. Z góry bardzo dziękuję.

[FasolkaBernoulliego]

Mnie się wydaje, że w (a) będzie 4.

Nazwijmy wierzchołki \(\displaystyle{ E}\) (najbardziej po lewej), \(\displaystyle{ F}\) (najbardziej na górze) i pozostałe cztery zaczynając od lewego dolnego rogu i idąc przeciwnie do ruchu wskazówek zegara: \(\displaystyle{ A, B, C, D.}\)
\(\displaystyle{ ED = 1,}\)
\(\displaystyle{ EC = 2,}\)
\(\displaystyle{ EB = 3,}\)
\(\displaystyle{ EA = 4,}\)
\(\displaystyle{ AB = 1,}\)
\(\displaystyle{ BC = 4,}\)
\(\displaystyle{ CD = 3,}\)
\(\displaystyle{ DA = 2,}\)
\(\displaystyle{ DF = 4,}\)
\(\displaystyle{ BF = 2.}\)

Jeżeli się nie pomyliłem, to dostajesz w ten sposób, że indeks jest co najwyżej \(\displaystyle{ 4}\). Ponieważ np. \(\displaystyle{ E}\) ma rząd \(\displaystyle{ 4}\), to indeks nie może być mniejszy, niż \(\displaystyle{ 4}\). Zatem musi być równy \(\displaystyle{ 4}\).

Pewnie jest jakieś eleganckie rozwiązanie, jak się lepiej zna teorię, ja jestem w tym zielony jak szczypiorek na wiosnę. W drugim przykładzie na razie nie widzę jak będzie - jak coś do wieczora wymyślę, to dam znać.

Ech, zgubiłem jedną krawędź w pierwszym. Myślę od nowa.

[kerajs]

Jaki numer (kolor) ma AC?

[FasolkaBernoulliego]

Dobra, mój komputer twierdzi, że dobrze masz policzone te indeksy. Teraz myślę nad uzasadnieniem.

Kod: Zaznacz cały

from sage.graphs.graph_coloring import edge_coloring
g = Graph({1: [3, 4, 5, 6], 2: [4,6], 3: [4,5,6], 4: [5], 5: [6]})
#show(plot(g))
print(edge_coloring(g, value_only=True))

g2 = Graph({1: [3, 4, 5, 6, 7], 2: [3, 4, 5, 6, 7], 3: [5, 6, 7], 4: [5, 6, 7], 5: [6]})
#show(plot(g2))
print(edge_coloring(g2, value_only=True))

Dodano po 52 minutach 26 sekundach:
Hm, mam taki pomysł.

Zauważmy, że:
(a) każde

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Skojarzenie_%28teoria_graf%C3%B3w%29

może mieć co najwyżej dwie krawędzie spośród
\(\displaystyle{ ED}\)
\(\displaystyle{ EC}\)
\(\displaystyle{ EB}\)
\(\displaystyle{ EA}\)
\(\displaystyle{ AB}\)
\(\displaystyle{ BC}\)
\(\displaystyle{ CD}\)
\(\displaystyle{ DA}\)

(b) każde skojarzenie może mieć co najwyżej jedną krawędź spośród:
\(\displaystyle{ BF}\)
\(\displaystyle{ DF}\)

(c) jeżeli skojarzenie ma krawędź \(\displaystyle{ AC}\), to może mieć tylko jedną krawędź spośród tych wymienionych w (a)

Stąd maksymalne skojarzenie ma 3 elementy (w sumie to jest to oczywiste), ale nie może być więcej, niż dwóch takich rozłącznych skojarzeń. Zakładając nawet, że pozostałe krawędzie można podzielić na 2-elementowe skojarzenia, to wciąż będziemy ich mieli 5, czyli indeks chromatyczny jest 5.

Sprawdź(cie), czy moje rozumowanie jest poprawne.

Dodano po 17 minutach 47 sekundach:
W przypadku (b) chyba da się zrobić łatwiej: ponieważ mamy 7 wierzchołków, to maksymalne skojarzenie może mieć 3 krawędzie. Ale mamy 16 krawędzi, więc 5 rozłącznych skojarzeń nie wystarczy, żeby je wszystkie pokryć. Zatem indeks musi być 6.