Задать вопрос юристу

3.3.1. Определениеи свойства деревьев

Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

Пример 86.

Граф G1 является деревом (рис.38).

Граф G2 является лесом (рис. 38), он содержит три связные компоненты, каждая из которых является деревом.


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

Утверждение. Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина.

Утверждение. Пусть G – дерево. Тогда любая цепь в G будет простой.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.3.1. Определениеи свойства деревьев:

  1. 4.3. Определённый интеграл и его свойства.
  2. Свойства и применение определенных интегралов
  3. Свойства определенного интеграла.
  4. Свойства определённого интеграла
  5. § 46, Определённый интеграл и его свойства
  6. 8.1. Определение и простейшие свойства характеристических функций.
  7. 2.2. Определение прочностных свойств вмещающих пород
  8. Часть 1. Определение свойств нервной системы
  9. в) Определение, свойство и граница (Bestimmung, Beschaffenheit und Grenze)
  10. Свойства, определяемые при оценке качества ТГИ, характеризуются определёнными показателями...
  11. Лабораторная работа М 4 Определение свойств нервной системы с помощью опросника «Оценка индивидуально-типологических особенностей личности»
  12. ПРОГРАММА РЕНТГЕНОЛОГИЧЕСКОГО ОБСЛЕДОВАНИЯ ГЛАЗНЫХ РАНЕНЫХ C ЦЕЛЬЮ ВЫЯВЛЕНИЯ ИНОРОДНЫХ ТЕЛ, ИХ ЛОКАЛИЗАЦИИ И ОПРЕДЕЛЕНИЯ НЕКОТОРЫХ ФИЗИЧЕСКИХ СВОЙСТВ