![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Desargues_graph_3color_edge.svg/languk-640px-Desargues_graph_3color_edge.svg.png&w=640&q=50)
Розфарбовування ребер
З Вікіпедії, безкоштовно encyclopedia
Розфарбовування ребер — в теорії графів, це присвоєння кольорів ребрам графа, при якому не існує суміжних ребер однакового кольору. Таке розфарбування графа називають правильним розфарбуванням.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Desargues_graph_3color_edge.svg/320px-Desargues_graph_3color_edge.svg.png)
Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. (червень 2019) |
Проблема розфарбовування ребер полягає в з'ясуванні, чи можливо розфарбувати даний граф використовуючи не більше кольорів. Мінімально потрібна кількість кольорів для правильного розфарбування даного графа називається хроматичним індексом графа. Наприклад, граф праворуч може бути розфарбований трьома кольорами, але двох буде замало (існуватимуть суміжні ребра однакового кольору). Таким чином, його хроматичний індекс дорівнює три.