Дерево, эквивалентные определения

Материал из Викиконспекты
Версия от 07:48, 1 ноября 2011; Vasin (обсуждение | вклад) (Определения)
Перейти к: навигация, поиск

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

Лес - граф, являющийся набором непересекающихся деревьем.

Определения

Дерево - неориентированный простой граф G, который удовлетворяет любому из эквивалентных утверждений:

  • любые две вершины графа G соединены единственным простым путем
  • G - связен и ацикличен
  • G - ацикличен, и простой цикл формируется при добавлении любого ребра
  • G - связен, и удаление любого ребра приводит к потере связности
  • G - связен, и полный 3-х вершинный граф не является его минором

Литература

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • Википедия — свободная энциклопедия