Граф як сукупність об’єктів з вказаними зв’язками між ними. Матриця суміжності як спосіб його представлення. Постановка задач про розфарбування графів, алгоритм вирішення її методом неявного перебору. Розробка програмної реалізації цього процесу.
Аннотация к работе
Граф (геометричний граф) - це фігура на площині, яка складається з непорожньої скінченної множини точок (вершин) і скінченної множини орієнтованих чи не орієнтованих ліній (ребер), що зєднують деякі пари вершин.Планарний граф - граф, який може бути зображений на площині без перетину ребер. Матриця інцидентності - одна з форм представлення графа, в якій вказуються звязок між інцидентними елементами графа (ребро (дуга) і вершина). Якщо для розфарбування вершин, суміжних з v, використано менше 5 кольорів, то розфарбування f можна доповнити до правильного розфарбування графа G не більш як 5 кольорами, розфарбувавши вершину v «не зайнятим» кольором. Отже, ми побудували правильне 5-розфарбування графа G - v, при якому ні одна з вершин, суміжних з v в графі G, не має кольору 1 (в результаті перефарбування вершина поміняла колір на 3, а вершини , , , зберегли колір). Під час першої будується початкова допустима розфарбування графа за наступним правилом: перша вершина фарбується в перший колір, а далі для кожної вершини вибирається мінімальний за номером колір, такий щоб ніяка із суміжних з даною раніше забарвлених вершин не мала цього кольору.В ході виконання даної курсової роботи було розглянуто та розяснено багато прикладів застосування деяких аспектів теорії графів, а саме - розфарбування графів.