Тема
Алгоритми на графах. Знаходження найкоротшого шляху
ВСТУП
Роком виникнення теорії графів одностайно вважається рік 1736, коли Леонард Ейлер опублікував рішення так званої задачі про Кенигсбергских мостах, а також знайшов загальний критерій існування ейлеровимі циклу в графі.
Отримання подальших істотних результатів у цій галузі датуються серединою ХIХ століття.
Однак початок проведення активних систематичних досліджень і становлення теорії графів як окремого авторитетного розділу сучасної математики відбулося ще майже 100 років тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найбільш поширених і популярних математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині і ліній, проведених між деякими з них, стала зручною і наочній формі зображення найрізноманітніших об'єктів, процесів і явищ.
Багато в чому це пов'язано з виникненням, бурхливим розвитком і поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від обслуговування переважно фізики переходить до проникнення своїх методів в інші сфери людської діяльності.
Одним із потужних інструментів такого проникнення є граф. З чисто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів як розділ сучасної алгебри. Дійсно, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного, інтенсивного і екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію.
Одну із завдань, яку можна вирішити за допомогою графа є задача знаходження найкоротших відстаней між об'єктами.
Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від знаходження оптимального маршруту між двома об'єктами на місцевості (напр. найкоротший шлях від будинку до академії), також використовується в системах автопілота, використовується для знаходження оптимального маршруту при перевезеннях комутації інформаційного пакету Internet і мн. ін.
Найбільш поширені методи пошуку найкоротших відстаней - це використання алгоритму Дейкстри (для знаходження найкоротшого шляху між двома вершинами), алгоритму Флойда (для знаходження найкоротших шляхів між усіма парами вершин) і алгоритму Єна (для знаходження k - найкоротших шляхів в графі).
Метою курсової роботи було вивчити і реалізувати на практиці алгоритм Дейкстри і Флойда для знаходження найкоротших шляхів в графі. Завдання роботи:
. Досліджувати властивості ейлерових і гамільтонових ланцюгів і циклів в теорії графів.
. Вивчення алгоритму Дейкстри і Флойда для знаходження найкоротших шляхів в графі.
. Приведення прикладів вирішення завдань цими методами.
Для графів з кінцевим безліччю вершин і ребер, як правило, проблема існування алгоритму вирішення завдань, у тому числі екстремальних, вирішується позитивно. Вирішення багатьох завдань, пов'язаних з кінцевими графами, може бути виконано за допомогою повного перебору всіх допустимих варіантів. Проте у такий спосіб вдається вирішити завдання тільки для графів з невеликим числом вершин і ребер. Тому істотне значення для графів має побудова ефективних алгоритмів, що знаходять точне або наближене рішення.
Розділ I. ВСТУП В теорії графів
1.1 Основні поняття та визначення
Основні елементи геометричних фігур, що застосовуються в теорії графів наведені на рис.1. і складаються з вершин графа, ребер графа і дуг графа.
Поєднання цих елементів визначає поняття: неорієнтовані граф, орієнтований граф і смешанийний граф [6].
Рис.1.1 Основні елементи графа (вершина, ребро, дуга)
неорієнтовані графів (Неограф) - це граф (рис.1.2), для кожного ребра якого неістотний порядок двох його кінцевих вершин.
Рис.1.2 неорієнтовані графів (вершини і ребра)
Орієнтування граф (орграф) - це граф, для кожного ребра якого существенен порядок двох його кінцевих вершин. Орграф представлений на рис.1.3, ребра орграфа іноді називають дугами.
Рис. 1.3 Орієнтований граф
Рис. 1.4 Смешанийий граф
См...
