Решение.

Задача.

П. 2. Деревья.

Определение 22. Всякий связный граф, не имеющий циклов, называется деревом. Несвязный граф, каждая компонента которого является деревом, т.е. представляющий собой объединение деревьев, называется лесом.

Определение 23. Вершина называется изолированной, если степень ее равна нулю. Если степень вершины дерева равна единице, то она называется висячей вершиной.

В примере висячими являются вершины a, b, c, d, e, f, g.

Дерево с р вершинами содержит р –1 ребер.

Многие графы, употребляемые в приложениях, являются деревьями. Например, графы всевозможных сортировок и классификаций. Корреспонденцию, пришедшую в страну, сортируют сначала по городам. Затем, в каждом городе – по отделениям связи, там – по участкам и т.д. Подобно этому живые организмы классифицируют сначала по типам, внутри типа – по классам, затем – по порядкам и т.д.

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

В физиологии рассматривают трахеобронхиальное дерево, вершинами которого являются участки раздвоения дыхательных путей, а ребрами – сами эти пути.

Наконец, деревьями являются всевозможные схемы происхождения: дерево языков, дерево происхождения видов, фамильное дерево и т.д.

Лист бумаги Плюшкин разрезает на три части. Некоторые из полученных листов он так же разрезает на три части. Несколько новых листиков он вновь разрезает на три более мелкие части и т.д. Сколько Плюшкин получает листиков бумаги, если разрезает k листов?

Листы бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, будут белыми крупными, остальные нарисуем маленькими черными.

Рисунок 7 помогает увидеть, что при разрезании одного листка на три части, число листков увеличивается на два. Если же разрезано k листов, то образовалось (1+2 k) листов (рис. 8). На этом рисунке показано 5 разрезаний.

П. 3. Изображение одного и того же графа.

Один и тот же граф может выглядеть на рисунке по-разному.

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