1. Введение. В последнее время теория графов приобретает все большую актуальность и популярность. Это является следствием того, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология, лингвистика. Эта теория также тесно связана со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероятности, топология, комбинаторный анализ. Теория графов может служить математической моделью для всякой системы, содержащей бинарное отношение. Одним из свойств графов, придающее им привлекательность в глазах исследователей, является возможность графического представления в виде диаграмм, и как следствие, высокая наглядность. [1] Важное место в теории графов занимают задачи раскраски вершин или ребер графа. С построением раскрасок связан целый ряд практических задач (распределение ресурсов вычислительных машин в сети, планирование производства, составление различных расписаний). Одной из важных задач, связанных с раскраской, является задача построения приближенных алгоритмов раскрашивания, которые не всегда находят точное решение задачи (иногда они находят только приближение к нему, и мы не можем знать этого заранее), но зато достаточно эффективны. Эта задача особенно значима при проектировании и создании различных вычислительных систем, при контроле продукции на производстве различных вычислительных устройств или их компонент. [2] Целью работы является изучение возможностей окрашивания некоторых графов для улучшения существующих приближенных алгоритмов последовательного раскрашивания и построения нового алгоритма, который бы был для них более эффективен. В работе ставятся и решаются следующие задачи: − анализ существующих алгоритмов приближенного окрашивания; − анализ возможностей окрашивания некоторых видов графов; − разработка нового алгоритма приближенного раскрашивания, который более эффективен в частных случаях; − экспериментальная проверка работоспособности нового алгоритма и сравнение результатов с результатами существующих алгоритмов. Методы исследования. В работе использованы методы теории автоматов, теории графов и алгебры для получения сложностных характеристик.
| 
Поиск