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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат графу G (рис. 1.60, а).

Остовной связный подграф — это подграф графа G, который содержит все его вершины и каждая его вершина достижима из любой другой (рис. 1.60, б).

Дерево — это граф, в котором нет циклов, т. е. граф, в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Остовным связным деревом называется подграф, включающий все вершины исходного графа G, каждая вершина которого достижима из любой другой, и при этом не содержащий циклов (рис. 1.60, в).

Рис. 1.60. а — подграф графа G, б — основной связный подграф графа G, в — основное связное дерево

Следующая страница Преобразование графа в основное связное дерево минимального веса

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