Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Методи розфарбування графів

Реферат Методи розфарбування графів





Вступ

граф програмний розфарбування

У даній курсовій работе розглядаються задачі з Ледь НЕ повсякдення життя, Які зводяться в Теорії графів до знаходження хроматична числа планарних графів та їх оптимального розфарбування.

Вирішення данної проблеми має як теоретичне так и практичне значення, Наприклад: для розфарбування Політичної Карта світу НЕ обійтісь и без розфарбування планарних графів (КОЖЕН материк відповідає ОКРЕМЕ планарному графу, а столиця країни - вершина) что ми розглянемо в пункті 2.4 .. Ця тема є й достатньо актуальними и вікорістовуеться як на виробництві, плануванні міста, так и в школах - для складання Розклад занять.

Метою данної роботи є РОЗГЛЯД проблем та завдань что зводяться до знаходження оптимального розфарбування, а отже и хроматична число; розробка алгоритму, что знаходиься оптімальне розфарбування графу ТА ЙОГО практичне! застосування.


1. Теоретична частина


1.1 Основні поняття


Граф - сукупність про єктів з Вказаною зв язками между ними.

Про єкти - вершини графу , а зв язки - дуги та ребра графу . Для різніх областей использование види графів могут відрізнятіся орієнтовністю, ограниченной на Кількість зв'язків и Додатковий Даними про вершини або ребра.

Велика Кількість структур, Які мают практичність Цінність в математиці та інформатіці, могут буті представлені графами. Например, будову Вікіпедії можна змоделюваті помощью орієнтованого графу, в якому вершини - це статті, а дуги (орієнтовані ребра) - посилання на агентство Інші статті.

Граф, что містіть только ребра - назівається неорієнтованім , а тієї что містіть только дуги - ОРІЄНТОВНИЙ , всі ж Інші - мішані .

Граф (геометричність граф) - це фігура на площіні, яка складається з непорожньої скінченної множини точок (вершин) i скінченної множини орієнтованих чи не орієнтованих ліній (ребер), что з 'єднують деякі парі вершин.

Планарний граф - граф, Який может буті збережений на площіні без Перетин ребер.

хроматична число графа G - Мінімальна Кількість кольорів, в Які можна розфарбуваті вершини графа G таким чином, щоб кінці будь-которого ребра малі Різні кольори. Позначається год ( G ).

Петля - дуга чі ребро что сполучає вершину саму Із собою.

Если пара вершин сполучена кількома ребрами чі дугами одного напрямку то Такі ребра чі дуги назівають кратним (||)


Таблиця

Тип графуРебраКратні ребраПростій графНеорієнтовніНіМультиграфНеорієнтовніТакОріентовний графОрієнтовніНіОрієнтовній мультігафОріентовніТак

Матриця суміжності - один Із способів представлення графа у виде матриці. Матриця суміжності графа G зі скінченною кількістю вершин (пронумеровані від 1 до n) - квадратна матриця А розмірності n, в Якій значення елемента рівне числу ребер что сполучає i-ву та j-ву вершини.




Мал.1


Матриця суміжності простого графа (что НЕ містіть петель и кратних ребер) є бінарною матрицею и містіть нулі на головній діагоналі

Ма ? тріця інціде ? нтності - одна з форм представлення графа, в Якій вказуються зв язок между інцідентнімі елементами графа (ребро (дуга) i вершина). Стовпці матриці відповідають ребрам, рядки - вершин. Ненульове значення у клітінці матриці вказує на зв язок между вершиною и ребром (їх інцедентність).

Кожна комірка матриці может набуваті трьох значень:

1: если ребро виходим з и входити у;

: если ребро входити у і виходе з;

: если между и немає ребра.



Список суміжності - це послідовність (масив, список) розміром N, КОЖЕН елемент якої є списком вершин суміжніх з даною.

Цей способ Збереження Найкраще Підходить для перерахування усіх вершин суміжніх з x.


1.2 Постановка завдань про розфарбування графів


Завдання про розфарбування карти

Знайте оптімальне розфарбування (а отже и хроматична число) даного планарного графа что відповідає Політичній карте світу. Відповідній задачі граф можна побудуваті прямо на карте: в середіні кожної країни відмітіті вершину, яка Цю Країну представляет («Столиця»), а реб...


сторінка 1 з 5 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Граф М.Т. Лоріс-Меліков і його спроба урядових реформ
  • Реферат на тему: Реалізація алгоритму знаходження множин елементарних циклів графа засобами ...
  • Реферат на тему: Розробка та реалізація мовою високого рівня алгоритму виділення сільносвязн ...
  • Реферат на тему: Практичне застосування теореми Пойа і перерахування графів
  • Реферат на тему: Розробка програми формування матриці суміжності