Вступ
граф програмний розфарбування
У даній курсовій работе розглядаються задачі з Ледь НЕ повсякдення життя, Які зводяться в Теорії графів до знаходження хроматична числа планарних графів та їх оптимального розфарбування.
Вирішення данної проблеми має як теоретичне так и практичне значення, Наприклад: для розфарбування Політичної Карта світу НЕ обійтісь и без розфарбування планарних графів (КОЖЕН материк відповідає ОКРЕМЕ планарному графу, а столиця країни - вершина) что ми розглянемо в пункті 2.4 .. Ця тема є й достатньо актуальними и вікорістовуеться як на виробництві, плануванні міста, так и в школах - для складання Розклад занять.
Метою данної роботи є РОЗГЛЯД проблем та завдань что зводяться до знаходження оптимального розфарбування, а отже и хроматична число; розробка алгоритму, что знаходиься оптімальне розфарбування графу ТА ЙОГО практичне! застосування.
1. Теоретична частина
1.1 Основні поняття
Граф - сукупність про єктів з Вказаною зв язками между ними.
Про єкти - вершини графу , а зв язки - дуги та ребра графу . Для різніх областей использование види графів могут відрізнятіся орієнтовністю, ограниченной на Кількість зв'язків и Додатковий Даними про вершини або ребра.
Велика Кількість структур, Які мают практичність Цінність в математиці та інформатіці, могут буті представлені графами. Например, будову Вікіпедії можна змоделюваті помощью орієнтованого графу, в якому вершини - це статті, а дуги (орієнтовані ребра) - посилання на агентство Інші статті.
Граф, что містіть только ребра - назівається неорієнтованім , а тієї что містіть только дуги - ОРІЄНТОВНИЙ , всі ж Інші - мішані .
Граф (геометричність граф) - це фігура на площіні, яка складається з непорожньої скінченної множини точок (вершин) i скінченної множини орієнтованих чи не орієнтованих ліній (ребер), что з 'єднують деякі парі вершин.
Планарний граф - граф, Який может буті збережений на площіні без Перетин ребер.
хроматична число графа G - Мінімальна Кількість кольорів, в Які можна розфарбуваті вершини графа G таким чином, щоб кінці будь-которого ребра малі Різні кольори. Позначається год ( G ).
Петля - дуга чі ребро что сполучає вершину саму Із собою.
Если пара вершин сполучена кількома ребрами чі дугами одного напрямку то Такі ребра чі дуги назівають кратним (||)
Таблиця
Тип графуРебраКратні ребраПростій графНеорієнтовніНіМультиграфНеорієнтовніТакОріентовний графОрієнтовніНіОрієнтовній мультігафОріентовніТак
Матриця суміжності - один Із способів представлення графа у виде матриці. Матриця суміжності графа G зі скінченною кількістю вершин (пронумеровані від 1 до n) - квадратна матриця А розмірності n, в Якій значення елемента рівне числу ребер что сполучає i-ву та j-ву вершини.
Мал.1
Матриця суміжності простого графа (что НЕ містіть петель и кратних ребер) є бінарною матрицею и містіть нулі на головній діагоналі
Ма ? тріця інціде ? нтності - одна з форм представлення графа, в Якій вказуються зв язок между інцідентнімі елементами графа (ребро (дуга) i вершина). Стовпці матриці відповідають ребрам, рядки - вершин. Ненульове значення у клітінці матриці вказує на зв язок между вершиною и ребром (їх інцедентність).
Кожна комірка матриці может набуваті трьох значень:
1: если ребро виходим з и входити у;
: если ребро входити у і виходе з;
: если между и немає ребра.
Список суміжності - це послідовність (масив, список) розміром N, КОЖЕН елемент якої є списком вершин суміжніх з даною.
Цей способ Збереження Найкраще Підходить для перерахування усіх вершин суміжніх з x.
1.2 Постановка завдань про розфарбування графів
Завдання про розфарбування карти
Знайте оптімальне розфарбування (а отже и хроматична число) даного планарного графа что відповідає Політичній карте світу. Відповідній задачі граф можна побудуваті прямо на карте: в середіні кожної країни відмітіті вершину, яка Цю Країну представляет («Столиця»), а реб...
