АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Деревья и циклы

Прочитайте:
  1. Жизненные циклы паразитов
  2. МАРШРУТЫ, ЦЕПИ И ЦИКЛЫ.
  3. Маршруты, цепи, циклы
  4. Половые циклы мелких животных
  5. Пути, маршруты, цепи и циклы.
  6. Семантические деревья
  7. Тіршілік циклы.
  8. Циклы по гастроэнтерологии и диетологии

Граф G называется деревом если он является связным и не имеет циклов.

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

Свойства деревьев:

Следующие утверждения эквивалентны:

1) Граф G есть дерево.

2) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

3) " две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

4) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

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

Утверждение 5. Пусть G связный граф, а − висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n (G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.

Число называется цикломатическим числом графа G.



Дата добавления: 2015-09-27 | Просмотры: 531 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)