Chromatic number
http://dbpedia.org/resource/Chromatic_number
Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G).
rdf:langString
Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
rdf:langString
Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba taka, że możliwe jest legalne pokolorowanie wierzchołków grafu Oznacza się ją symbolem . Problem wyznaczenia liczby chromatycznej jest NP-trudny – nie są znane niezawodne wielomianowe algorytmy wyznaczające liczbę chromatyczną każdego grafu. Istnieje jednak szereg oszacowań liczby chromatycznej dla różnych klas grafów, np.:
rdf:langString
rdf:langString
Chromatic number
rdf:langString
Liczba chromatyczna
rdf:langString
Хроматическое число
rdf:langString
Хроматичне число
rdf:langString
色数
xsd:integer
670588
xsd:integer
894539410
rdf:langString
Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba taka, że możliwe jest legalne pokolorowanie wierzchołków grafu Oznacza się ją symbolem . Problem wyznaczenia liczby chromatycznej jest NP-trudny – nie są znane niezawodne wielomianowe algorytmy wyznaczające liczbę chromatyczną każdego grafu. Istnieje jednak szereg oszacowań liczby chromatycznej dla różnych klas grafów, np.:
* gdzie jest rozmiarem maksymalnej kliki grafu
* Twierdzenie Brooksa: dla grafów pełnych oraz cykli o nieparzystej długości gdzie jest maksymalnym stopniem wierzchołka w grafie G; dla pozostałych grafów spójnych zachodzi ,
* dla grafów planarnych
* dla drzew o co najmniej dwóch wierzchołkach
rdf:langString
Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G).
rdf:langString
Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
xsd:nonNegativeInteger
181