Liczba chromatyczna

0Mniac · Post autor: **0Mniac** » 25 cze 2015, o 16:07

Witam. Jest jakiś ogólny sposób- może wzór na wyznaczanie liczby i indeksu chromatycznego? Jakie są wasze sposoby na wyznaczenie tego? I btw, cykl \(\displaystyle{ C_{5}}\) będzie wyglądał tak? : Plus dodatkowe pytanie do tego cyklu- ile drzew rozpinających ma cykl i jak ilość takich drzew się wyznacza? Co do liczby i indeksu chromatycznego to znalazłem informację, że w grafie \(\displaystyle{ K_{n}}\) liczba chromatyczna to \(\displaystyle{ n}\) , a indeks to \(\displaystyle{ n-1}\), prawda to?:D

: AU; 61996964038110159455.jpg (5.52 KiB) Przejrzano 69 razy

gardner · Post autor: **gardner** » 27 cze 2015, o 21:07

W grafie pełnym liczba chromatyczna wynosi n co jest oczywiste bo każdy jeden wierzchołek jest połączony z wszystkimi innymi. Co do indeksu chromatycznego to ile wynosi,zależy od liczby wierzchołków : czy jest parzysta czy nie. Sprawdź sobie dla przećwiczenia i napisz odpowiedź. Chyba nie ma jednego klarownego sposobu na sprawdzanie takich rzeczy. Za to w pewien sposób możesz sobie w pewien ograniczyć indeks chromatyczny stosując twierdzenie Vizinga,co do liczby chromatycznej twiedzenie o folklorze. Poczytaj w necie co dokładnie mówią.