Уроки 31 - 34
§1.10. Графы и их исследование с использованием языков объектно-ориентированного программирования Visual Basic и Turbo Delphi

Содержание урока

1.10.1. Введение в теорию графов

Основные понятия теории графов

Маршрут графа

Ориентированные графы

Взвешенные графы

Описание графа с помощью матрицы смежности

Подграфы и деревья

Преобразование графа в основное связное дерево минимального веса

Контрольные вопросы

1.10.2. Изучение графов на языке Visual Basic

1.10.3. Изучение графов на языке Turbo Delphi

1.10.1. Введение в теорию графов

Ориентированные графы

Сообразительный читатель может задать вопрос: имеет ли значение направление, ориентация ребра? Ведь в системе улиц можно найти дороги как с односторонним, так и с двусторонним движением. Именно поэтому в теории графов вводится понятие орграфа — ориентированного графа. В орграфе каждое ребро имеет одно направление. Такие ребра называются дугами. Другими словами, ребро — это неупорядоченная пара вершин, а дуга — упорядоченная. Очевидным является тот факт, что дуги R₁₂ и R₂₁ не совпадают в орграфе. Для орграфа вводятся такие понятия, как входящая и исходящая степени вершины. Это соответственно число входящих в вершину дуг и число исходящих из нее дуг.

Следующая страница Взвешенные графы

Cкачать материалы урока