1. Организационный момент и введение в тему

Мы привыкли представлять информацию в виде таблиц или диаграмм. Но есть задачи, где данные связаны между собой сложными отношениями: «кто кому начальник», «как связаны города дорогами», «из какого слова можно составить другое».

Для описания таких связей математики придумали специальный язык — теорию графов.

Граф — это совокупность точек (которые называют вершинами) и линий (которые называют рёбрами), соединяющих некоторые из этих точек.

Графы нас окружают повсюду:

  • Схема метро — это граф (станции — вершины, тоннели — рёбра).

  • Карта социальной сети «ВКонтакте» — граф (люди — вершины, дружба — рёбра).

  • Карта сайта в интернете — граф (страницы — вершины, ссылки — рёбра).

Сегодня мы познакомимся с самым важным и полезным видом графов — деревом.