Міністерство освіти і науки
Державна освітня установа
вищої професійної освіти
В«Сибірський державний індустріальний університетВ»
Кафедра інформаційних технологій в металургії
Курсова робота: В«Алгоритм розмальовки графаВ»
Виконав: студент гр. ІСТ-М-12
О.А. Маломижева
Перевірив: ктн, доцент
С.Ю. Краснопьоров
Новокузнецьк 2013р.
Введення
Поняття В«графВ» пов'язане з поняттям В«графічнийВ», В«графікаВ». Дійсно, графові моделі мають просту і зрозумілу графічну інтерпретацію, що дозволяє з їх допомогою образно уявити самі різні об'єкти, в той же час залишаючись у рамках суворих математичних моделей. Першою роботою теорії графів як математичної дисципліни вважають статтю Ейлера (1736г.), в якій розглядалася задача про Кенігсберзький мостах. Ейлер показав, що не можна обійти сім міських мостів і повернутися у вихідну точку, пройшовши по кожному мосту рівно один раз. Наступний імпульс теорія графів одержала через майже 100 років з розвитком досліджень по електричних мережах, кристалографії, органічної хімії та інших наук. З графами, самі того не помічаючи, ми стикаємося постійно. Наприклад, графом є ​​схема ліній метрополітену. Точками на ній представлені станції, а лініями - шляхи руху поїздів. Досліджуючи свій родовід і зводячи її до далекого предка, ми стоїмо так зване генеалогічне древо. І це древо - граф. Методи теорії графів широко застосовуються в дискретної математики. Без них неможливо обійтися при аналізі та синтезі різних дискретних перетворювачів: функціональних блоків комп'ютерів, комплексів програм і т.д. В даний час теорія графів охоплює великий матеріал і активно розвивається. br/>
1. Теоретична частина
.1 Основні визначення
Графом називається набір точок (ці точки називаються вершинами), деякі з яких оголошуються суміжними (або сусідніми). Вважається, що суміжні вершини з'єднані між собою ребрами (або дугами). Таким чином, ребро визначається парою вершин. Два ребра, у яких є спільна вершина, також називаються суміжними (або сусідніми). Граф визначається як сукупність безлічі М з заданим на ньому бінарним отношеніемТМ2. br/>В
Між елементами М і Т визначено ставлення інцидентності, тобто зв'язку між двома елементами безлічі М через один елемент множини Т, представлено на малюнку 1.
В
Рисунок 1 - Приклад графа В«зіркаВ»
Граф називається орієнтованим (або орграфом), якщо деякі ребра мають напрямок. Це означає, що в орграфе деяка вершина може бути з'єднана з іншого вершиною, а зворотного з'єднання немає. Геометрично граф часто зображують точками площини, причому сус...
