знаходить мінімальну розмальовку цього графа за лінійний від n число кроків.
Гері, Джонсон і Стокмейер [2] довели, що при навіть перевірка на 3-раскрашіваемоеть плоского графа є NP-повною завданням.
Розглянемо тепер випадок, коли алгоритм розмальовки вершин графа з перефарбою двобарвних компонент може бути віднесений до класу точних поліноміальних алгоритмів. В [12] описаний клас графів, для якого досліджуваний алгоритм завжди знаходить мінімальну розмальовку. Ці графи отримали назву графів Мейніеля: у всіх таких графів кожен непарний цикл містить, принаймні, дві хорди. Доведено, що всякий граф Мейніеля є досконалим графом. p align="justify"> Що стосується трудомісткості алгоритму розмальовки вершин графа Мейніеля з перефарбою двобарвних компонент, то вона може бути оцінена як кроків.
Програма. Опис розробленої програми
На підставі вивченого матеріалу була розроблена і реалізована програма, розфарбовували вершини заданого графа. Програма розроблена в середовищі VisualStudio2010 С + + з використанням бібліотеки з графами BoostGraphLibrary. p align="justify"> Дана програма працює з файлами. Вхідні файли повинні містити граф, описаний на мові DOT [13, 14] (див. рис.6) - спеціальний мова для опису графів. Це досить простий спосіб опису графів, як люди, так і комп'ютерні програми можуть легко його іспользовать.Прінято файли робити з розширенням В«. DotВ». br/>В
Малюнок 6. Вхідний файл
Вихідний файл має такий же формат (див. рис.7).
В
Малюнок 7. Вихідний файл
В результаті роботи програми виводить, якими квітами пофарбовані вершини, скільки квітів було потрібно на розмальовку графа і яке витратилася час роботи програми. Так само буде видно, в якому порядку офарблювалися вершини і скільки разів використовувався той чи інший колір. p align="justify"> Опишемо, як необхідно працювати з програмою.
Щоб запустити програму, необхідно відкрити командний рядок, де лежить папка з програмою (див. рис. 8):
В
Малюнок 8. Зовнішній вигляд програми
Далі необхідно прописати адресу, де лежить suboptimal_coloring.exe і потім, за допомогою позначень:
-input-filename-це звідки береться вибраний файл;
-output-filename - це відповідно навпаки, куди він кладеться;
написати повністю рядок виклику файлу. Вона повинна виглядати таким чином: D: XXX graph_coloring-r181 trunk> out Debug-Win32 suboptimal_coloring.exe - input-filename data/exp1.1.dot - output-filename data/exp1.1.colored . dot - report-filename data/report.csv (див. рис. 9)
В
Малюнок 9. Рядок виклику програми
