ВУЗ:
Составители:
Рубрика:
Глава 1. Основные понятия теории графов 47
20. Нарисовать все возможные вырожденные бинарные деревья
для n = 4.
21. Определить вершинную и реберную связность, диаметр и
центр графов на рис. 1.47.
22. Доказать, что полный граф K
n
имеет в точности n
n–2
остовных
деревьев.
23. Самая длинная простая цепь является диаметром графа. Дока-
зать, что любые два диаметра имеют общую вершину.
24. Доказать, что простой граф на n вершинах не является дву-
дольным, если он имеет более n
2
/4 ребер.
25. Доказать, что в дереве существуют хотя бы две висячие вер-
шины.
26. Доказать, что при добавлении ребра между двумя любыми
вершинами дерева в полученном графе образуется ровно один цикл.
27. При каких условиях a задаче Торричелли – Ферма точка Р на-
ходится внутри треугольника.
28. Записать матрицы смежности для графов C
3
, K
3
, K
3,3
.
29. Доказать, что диаметр графа не превосходит его удвоенного
радиуса.
30. Сколько помеченных графов порождает простой цикл С
5
?
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
