ГРАФ РАСКРАШЕННЫЙ

— неориентированный граф без петель, множество вершин (или ребер) которого разбдто на к непересекающихся групп так, что каждая вершина (ребро) принадлежит точно одной группе и смежные вершины (ребра) принадлежат разным группам. Минимальное число таких групп вершин (ребер) наз. хроматическим числом (классом) графа. Если каждой группе поставить в соответствие свой цвет, то в Г. р. смежные элементы будут окрашены различными цветами, т. е. их легко различить. Задачи, связанные с раскраской графов, кроме теоретического, имеют большое практическое значение. Они возникают при монтаже и проверке сложных электрических схем, составлении графиков турниров, в социологии и т. п.

Лит. см. к ст. Графов теория. В. А. Трубин.