Додання однієї хорди до остова графа вказує на незалежний цикл

Теорема 2.3.4. Граф G є зв’язним тоді і тільки тоді, коли він має остов.

Означення 2.3.8. Лісом з k дерев називають граф, що не має циклів і складається з k компонент.

Теорема 2.3.5. Кожне дерево з n вершинами має n -1 ребро.

Теорема 2.3.6. Ліс з дерев, який містить n вершин, має n - k ребер.

ЛІТЕРАТУРА

1. Алферова З.В. Математическое обеспечение экономических расчетов с помощью графов. – М.: Статистика, 1994. – С.18-23.

2. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С. 30-34,136-143.

3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. – С.43-59.

4. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.230-235, 273-275.

5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – С.39-40, 105-108.

Тема 2.4. РОЗФАРБУВАННЯ ГРАФА