том 10.
Результатом роботи над курсовою роботою створено програму середовищі Delphi. За допомогою цієї програми здійснюється введення даних транспортної мережі, і виконується розрахунок у результаті якого розраховується найкоротший шлях. p align="justify"> Теорія графів знаходить широке застосування в різних галузях науки і техніки:
Графи і інформація
Двійкові дерева грають вельми важливу роль в теорії інформації. Припустимо, що певне число повідомлень потрібне закодувати у вигляді кінцевих послідовностей різної довжини, що складаються з нулів та одиниць. p align="justify"> Якщо ймовірності кодових слів задані, то найкращим вважається код, в якому середня довжина слів мінімальна в порівнянні з іншими розподілами ймовірності. Задачу про побудову такого оптимального коду дозволяє вирішити алгоритм Хаффмана. p align="justify"> Двійкові кодові дерева допускають інтерпретацію в рамках теорії пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який можна або В«такВ», або В«ніВ». Стверджувальному і негативної відповіді відповідають два ребра, що виходять з вершини. "Опитування" завершується, коли вдається встановити те, що було потрібно. p align="justify"> Таким чином, якщо комусь знадобиться взяти інтерв'ю у різних людей, і відповідь на чергове запитання залежатиме від заздалегідь невідомого відповіді на попереднє запитання, то план такого інтерв'ю можна представити у вигляді двійкового дерева.
Графи і хімія
Ще А. Келі розглянув задачу про можливі структурах насичених (або граничних) вуглеводнів, молекули яких задаються формулою: CnH2n +2 ​​Молекула кожного граничного вуглеводню являє собою дерево.
Якщо видалити всі атоми водню, то решта атоми вуглеводню також будуть утворювати дерево, кожна вершина якого має ступінь не вище 4. Отже, число можливих структур граничних вуглеводнів, тобто число гомологів даного речовини, дорівнює числу дерев з вершинами ступені не більше чотирьох. Таким чином, підрахунок числа гомологів граничних вуглеводнів також призводить до задачі про перерахування дерев певного типу. Це завдання і її узагальнення розглянув Д. Пойа. p align="justify"> Графи і біологія
Дерева відіграють велику роль у біологічній теорії розгалужених процесів. Для простоти ми розглянемо тільки один різновид розгалужених процесів - розмноження бактерій. Припустимо, що через певний проміжок часу кожна бактерія або ділиться на дві нові, або гине. Тоді для потомства однієї бактерії ми отримаємо двійкове дерево. Нас цікавитиме лише одне питання: у скількох випадках n-е покоління однієї бактерії налічує рівно k нащадків? Рекурентне співвідношення, що позначає число необхідних випадків, відомо в біології під назвою процесу Гальтона-Ватсона. Його можна розглядати як окремий випадок багатьох загальних формул. p align="justify"> Графи і фізика
