Визначення та способи представлення графів. Основні алгоритми на графах. Побудова мінімального остового дерева. Алгоритми Прима та Дейкстри. Модель Флойда-Уоршалла. Огляд можливостей мови програмування. Опис функцій програмної моделі, інтерфейс програми.
ЗМІСТ ВСТУП 1. Загальний огляд проблеми та обґрунтування вибору програмних засобів 1.1 Значення алгоритмів на графах 1.2 Визначення та способи представлення графів 1.3 Огляд програмних засобів 2. Програмна реалізація алгоритмів 3.1 Огляд можливостей мови програмування 3.2 Опис функцій програмної моделі 3.3 Інтерфейс програми ВИСНОВКИ ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ ВСТУП Спробуйте намалювати „заклеєний конверт” одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків. Яскраві приклади цього - теорії, створені М. Келдишем для авіаконструкторів. Отже, неформально, граф можна визначити як набір вершин (міста, перехрестя, компютери, букви, цифри кости доміно, мікросхеми, люди) і звязків між ними: дороги між містами; вулиці між перехрестями; дротяні лінії звязку між компютерами; слова, що починаються на одну букву і закачуються на іншу або цю ж букву; провідники, що сполучають мікросхеми; споріднені стосунки, наприклад, Олексій - син Петра. Наприклад, у вигляді графа можуть бути зображені електричні, транспортні, інформаційні і комп’ютерні та інші мережі, карти автомобільних, залізничних, повітряних шляхів, лабіринти, моделі кристалів, структури молекул хімічних речовин і т.д. Ребра неорієнтованого графа, частіше усього званого просто графом, можна проходити в обох напрямах. У орієнтованому графові, або орграфі, ребра є впорядкованими парами вершин : перша вершина - це початок ребра, а друга - його кінець. Приклади існування графів в оточуючому нас середовищі наведено у таблиці 1.1 Таблиця 1.1 - Приклади неорієнтованих графів Граф Вершини Ребра Сімя Люди Родинні звязки Місто Перехрестя Вулиці Мережа Компютери Кабелі Будинок Квартири Сусідство Метро Станції Пересадки Листок в клітинку Клітинки Наявність загальної межі Для візуального представлення графа його малюють, а не задають їх множинами. Рисунок 1.2 - Три способу зображення одного графа Рисунок 1.3 - Приклад двох різних графів З приведеного вище визначення витікає, що в класичних графах не буває петель - ребер, що сполучають деяку вершину саму з собою (рис. 1.4).
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
