3. 3. Список суміжності. 14
4. Обходи графів. 14
4. 1. Пошук в глибину. 15
4. 2. Пошук в ширину. 17
Список літератури. 20
Будь-яка система, що припускає наявність дискретних станів або наявність вузлів і переходів між ними може бути описана графом.
Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлера, з'явилася в 1736 р Ейлер вирішував дуже відому головоломку про мостах Кенігсберга. Термін «граф» вперше був введений через 200 років (в 1936 р) Д. Кеніга. Поштовх до розвитку теорія графів одержала на рубежі ХIX і ХХ століть, коли різко зросла кількість робіт в області топології і комбінаторики, з якими її пов'язують найтісніші узи спорідненості. Графи стали використовуватися при побудові схем електричних ланцюгів і молекулярних схем.
Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-і роки ХХ століття.
Останнім часом графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях чи не всю сучасну математику. Графи ефективно використовуються в теорії планування і управління, теорії розкладів, соціології, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходження найкоротшого відстані, максимального паросполучення і ін. Математичні розваги і головоломки теж є частиною теорії графів. Теорія графів швидко розвивається, знаходить все нові додатки.
1. Основні поняття
Декартових твором двох множин A і B називається множина пар елементів, таких, що перший елемент пари береться з безлічі A, другий з B: A x B =.
Наприклад, декартових твором множин A = і B = є безліч A x B = <(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)>.
Граф - це пара G = (V, E), де V - безліч вершин, E - безліч ребер (дуг).
Граф - сукупність кінцевого числа точок, які називаються вершинами графа, і попарно з'єднують деякі з цих вершин ліній, званих ребрами або дугами графа.
Вершини графа позначають латинськими буквами A, B, C, D або цифрами. Іноді граф в цілому можна позначати однією великою літерою.
Невпорядкована пара вершин називається ребром, упорядкована - дугою. Тобто відрізок між вершинами, що має напрямок, називають дугою. Напрямок позначається стрілочкою на кінці.
Відрізок між вершинами, що не має напрямку, називають ребром.
Дуги - це як дороги з одностороннім рухом: можна проїхати тільки в одну сторону. Ребра - це як дороги з двостороннім рухом: можна проїхати в обидві сторони.
Завдяки використанню графів можна спростити вирішення завдань, сформульованих в різних областях знань: в автоматиці, електроніці, фізиці, хімії та ін. За допомогою графів зображуються схеми доріг, газопроводів, тепло - і електромережі. Допомагають графи в рішенні математичних і економічних завдань.
Аркадій, Борис. Володимир, Григорій і Дмитро при зустрічі обмінялися рукостисканнями (кожен потиснув руку кожному по одному разу). Скільки всього рукостискань було зроблено?
Точки А, Б, В, Г, Д називаються вершинами графа, а відрізки ліній, що з'єднують ці точки - ребрами графа.
У задачі необхідно підрахувати число ребер графа, зображеного на малюнку. Це число і буде дорівнює кількості скоєних рукостискань між п'ятьма молодими людьми. Їх 10.
Граф, що містить тільки дуги, називається орієнтованим.
Орієнтованим називається граф, в якому - безліч впорядкованих пар вершин виду (x, y), де x - називається початком, y - кінцем дуги. Дугу (x, y) часто записують як і зображують у вигляді:
Вважається, що дуга веде від вершини x до вершини y, а вершина y суміжна з вершиною x. Орієнтований граф також називають Орграф.