Новый эвристический алгоритм раскраски графа

Abstract

В дискретной математике известны разные алгоритмы раскраски графов: точные, переборные, эвристические. Недостатком точных и переборных алгоритмов является то, что они характеризуются неполиномиальной сложностью от количества вершин в графе. Эвристические требуют меньших затрат времени, но не гарантируют получения оптимального решения. В предлагаемой статье описывается новый эвристический алгоритм раскраски графа, обладающий линейной сложностью. Качество окраски достигается выбираемым порядком обработки вершин.

The exact, searching and heuristic algorithms are known in discrete mathematics. Non polynomial computational complexity in relation to graph nodes quantity is the imperfection of exact and searching algorithms. The heuristic algorithms are need smallest time, but optimal solution isn’t guaranteed. This article presents new graph paint heuristic algorithm with linear computational complexity. The paint quality is achieved by selected nodes processing order.