визначення
Хроматичної число графа - мінімально кількість непересічних класів вершин графа
(Де V - безліч вершин графа), таких, що вершини в кожному класі незалежні, тобто що будь-ребро графа не з'єднує вершини одного і того ж класу.
пов'язані визначення
- Граф називається K-розфарбовуваним. якщо його хроматичної число не перевищує K. а K не перевищує кількості вершин графа. Тобто
- граф називається K-розфарбовуваним. якщо його вершини можна розфарбувати K різними кольорами так, що у будь-якого ребра кінці будуть різного кольору.
- K-хроматичний граф - граф, хроматичної число якого дорівнює K. Тобто
- граф називається K-хроматичним. якщо його вершини можна пофарбувати мінімум K квітами так, що у будь-якого ребра кінці будуть різного кольору. K при цьому називається хроматичним числом цього графа.
хроматичний індекс
хроматичний індекс кубічного графа
Хроматичний клас графа G - мінімальне число кольорів, в які можна розфарбувати ребра графа G так, щоб суміжні ребра мали різні кольори. Позначається χ '(G). Проблема реберної розмальовки довільного плоского кубічного графа без мостів трьома кольорами еквівалентна знаменитої Проблемі чотирьох фарб. Хроматичний індекс визначає 1-факторизацию графа.
хроматичний многочлен
Якщо розглянути кількість різних розмальовок поміченого графа як функцію від доступного числа квітів t. то виявляється, що ця функція завжди буде поліномом від t. Цей факт був виявлений Біркгофом і Льюїсом [1] при спробі довести Гіпотезу чотирьох фарб.
Хроматичні многочлени деяких графів
Значення для теорії графів
Безліч глибоких завдань теорії графів легко формулюються в термінах розмальовки. Найзнаменитіша з таких завдань, Проблема чотирьох фарб. в даний час вирішена, проте з'являються нові, наприклад, узагальнення Проблеми чотирьох фарб, гіпотеза Хадвігера.
література
«Теорія графів» - О. Оре. переклад з англійської І. Н. Врублевської, під редакцією Н. Н. Воробйова, видавництво «Наука», Москва 1986
- ↑ Birkhoff, G. D. and Lewis, D. C. "Chromatic Polynomials." Trans. Amer. Math. Soc. 60, 355-451, 1946.
Дивитися що таке "Хроматичний граф" в інших словниках:
Граф Петерсена - Цю статтю слід вікіфіціровать. Будь ласка, оформіть її згідно з правилами оформлення статей ... Вікіпедія
Повний граф - Вершини n Ребра Діаметр 1 Автоморфізм ... Вікіпедія
Хроматичної число - 3 розфарбування графа Петерсена хроматичної число графа G мінімальне число кольорів, в які можна розфарбувати вершини ... Вікіпедія
Гіпотеза Хадвігера - Не слід плутати з проблемою Нельсона Ердеша Хадвігера. Гіпотеза Хадвігера одна з невирішених гіпотез теорії графів. Вона формулюється так: всякий k хроматичний граф стягуємо до повного графу на вершинах. ... ... Вікіпедія
Невирішені проблеми математики - невирішені проблеми (або Відкриті проблеми) проблеми, які розглядалися математиками, але до сих пір не вирішені. Часто беруть форму гіпотез, які, ймовірно, вірні, але потребують доведення. У науковому світі популярна практика ... ... Вікіпедія
Відкриті математичні проблеми - відкриті (невирішені) математичні проблеми проблеми, які розглядалися математиками, але до сих пір не вирішені. Часто мають форму гіпотез, які, ймовірно, вірні, але потребують доведення. У науковому світі популярна ... ... Вікіпедія
Невирішені проблеми математики - Невирішені проблеми (або Відкриті проблеми) проблеми, які розглядалися математиками, але до сих пір не вирішені. Часто беруть форму гіпотез, які, ймовірно, вірні, але потребують доведення. У науковому світі популярна практика ... ... Вікіпедія
Невирішені проблеми теорії чисел - Невирішені проблеми (або Відкриті проблеми) проблеми, які розглядалися математиками, але до сих пір не вирішені. Часто беруть форму гіпотез, які, ймовірно, вірні, але потребують доведення. У науковому світі популярна практика ... ... Вікіпедія