Курсова робота на тему: «ТЕОРІЯ ГРАФІВ У КОМП’ЮТЕРНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЯХ»

ЗМІСТ

вступ    3

Історичні зауваженння. Типові задачі теорії графів    5

Основні означення теорії графів    8

Способи задання графів    12

Принципи побудови сучасних комп’ютерних Інформаційних мереж    15

Топологія локальних мереж    17

Топологія глобальних мереж    20

Висновок    24

Список використаної літератури    26

 

 

вступ

Актуальність теми: Роком виникнення теорії графів одностайно вважається рік 1736, коли Леонард Ейлер опублікував розв’язок так званої задачі про кенігсберзькі мости, а також знайшов загальний критерій існування ейлерового циклу в графі.

Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших об’єктів, процесів та явищ.

Великою мірою це пов’язано з виникненням, бурхливим розвитком та поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від “обслуговування” переважно фізики переходить до проникнення своїх методів у інші сфери людської діяльності. Одним з потужних інструментів такого проникнення є граф.

За останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики.

 

Завдання: Розвиток інформаційних технологій формалізації руху даних на основі моделювання системних функцій комп’ютерних мереж являє собою складну багатокритеріальну задачу, яка вирішується на базі теорії графів. Розглянемо задачу використання теорії графів при побудові комп’ютених інформаційних технологій.

Об’єкт дослідження: застосування теорії графів саме в інформаційних комп’ютерних технологіях. Будемо розглядати комп’ютерні мережі (КМ) як графи і підграфи (підмережі великих КМ).

Предметом дослідження є особливості застосування та практичного використання теорії графів у комп’ютерних інформаційних технологіях.

:

Історичні зауваженння. Типові задачі теорії графів

Прийнято пов’язувати зародження теорії графів як математичної дисципліні з роботою Леонарда Ейлера 1736 р., у якій знайдено умову існування у зв’язному графі циклу, що містить всі ребра графа (без повторень). Такий цикл тепер називається ейлеровим. Як показує простий приклад (рис. 1), є графи, що не є ейлеровими циклами.

Першоджерелом задачі про ейлерів цикл сам Ейлер називає відому головоломку про кенігсберські мости. В місті Кенігсберг (у 1736 р.) два річкових острова А, В з’єднувалися між собою і з берегами С, Д річки Прегель сьома мостами (рис. 2).                                                                    С

    

Д

Рис. 1. Не ейлерів граф                        Рис. 2. Кенігсберські мости

Чи можна здійснити прогулянку по місту, пройшовши по кожному мосту точно один раз, і повернутися до вихідної точки? Зобразивши ділянки суші вершинами, мости — ребрами, одержимо граф, який не є ейлеровим циклом. Тому і задача про кенігсберські мости не має позитивного розв’язку.

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

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

Частковий випадок цієї задачі, що не враховує довжину переходів між пунктами, але зберігає всі її принципові труднощі, сформулював у 1859 р. В. Гамільтон на прикладі графа додекаедру: обійти замкненим маршрутом по ребрах багатогранника всі його вершини, пройшовши через кожну вершину рівно один раз (крім початку і кінця шляху). Саме цю задачу Гамільтон продав за 25 гіней одному майстрові іграшок у вигляді гри «Навкруги світу». Для довільного графа задача Гамільтона не обов’язково має розв’язок і формулюється так: Знайти простий цикл, що містить всі вершини графа (такий цикл називається гамільтоновим). Для графа додекаедра гамільтонів цикл існує. За певних умов сучасна задача комівояжера, що припускає неодноразове відвідання вершин, зводиться до відшукання у графі із заданими «довжинами» ребер гамільтонового циклу найменшої довжини. Згадані умови такі: кожне ребро (а, b) графа має довжину, що дорівнює довжині найкоротшого ланцюга між вершинами а і b.

Одна з найвідоміших задач математики — проблема чотирьох фарб — також належить до графів. Ще у минулому столітті було відзначено, що кожну конкретну географічну карту можна розфарбувати чотирма фарбами так, щоб будь-які дві сусідні країни були пофарбовані у різні кольори. Однак доведення для довільної карти (тобто для двозв’язного плоского графа) вдалося дати з використанням ЕОМ тільки в останні роки. Слід підкреслити результат Хівуда, що довів у 1890 р. достатність п’яти фарб для розфарбування карти.

Для неплоских графів задача про розфарбування ставиться інакше — для вершин; тут є багато результатів і нерозв’язаних задач, цікавих для теорії і практики .

Граф називається плоским, якщо його можна укласти на площині без схрещення ребер (шляхом їх неперервної деформації). Топологічний критерій планарності графа виявив Л. С. Понтрягін (1927 р.) без опублікування цього результату і незалежно — К. Куратовський (1930 р.). Через вагомість планарної реалізації електронних схем (друковані плати і ін.) останнім часом одержано інші критерії планарності та алгоритми укладення графів (Вагнер, Уїтні, Мак-Лейн, Фарі, Штейн тощо).

Сторінка: 1 2 3 4 5
завантаження...
WordPress: 23.15MB | MySQL:26 | 0,718sec