Графы

курсовая работа

3.2 Свойства

Дерево не имеет кратных рёбер и петель.

Любое дерево с n вершинами содержит n ? 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B ? P = 1, где B -- число вершин, P -- число рёбер графа.

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

Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.

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

Для любых трех вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

Делись добром ;)