Среда, 08.02.2012, 10:06
Приветствую Вас Гость

Сайт факультета ЭВТ ВолгГТУ

Меню сайта
Форма входа
Логин:
Пароль:

Войдите, чтобы не видеть рекламу
Категории раздела
Дополнительно
Реклама


Это интересно...

Сисадмин мнил себя богом сети, однако электрик грубо развеял этот миф ...

Поиск
Наш опрос
Вы умеете программировать на
Всего ответов: 387
Статистика

Онлайн всего: 16
Ныкаются: 16
Пользователей: 0
Главная » Файлы » Методички » Экстремальные задачи [ Добавить материал ]

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

[ ] 20.06.2010, 16:54

Дерево — это связный граф без циклов.

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

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

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

См. также:  Алгоритмы решения экстремальных задач, Романовский, страница 106.

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

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

Пусть G-связный граф, v – висячая вершина в G, G' – граф полученный из G в результате удаления вершины v и инцидентного ей ребра. Тогда G' - связный граф.

Пусть G – дерево с n вершинами и m ребрами. Тогда m = n – 1.

Пусть G' - граф являющийся деревом, G - граф полученный в результате добавления к G' новой вершины v и ребра {v, W} где W -- некоторая вершина графа G'. Тогда G - дерево.

Пусть G = (v, X) – связный граф с n ребрами и m вершинами и пусть так же выполняется равенство m = n – 1. Тогда G – дерево.


Двоичное дерево (оно же бинарное дерево): Неориентированное дерево, в котором степени вершин не превосходят 3, либо ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
Категория: Экстремальные задачи | Добавил: COBA
Просмотров: 1030 | Загрузок: 0 | Рейтинг: 0.0/0 |
Всего комментариев: 0

Имя *:
Email:
Код *:




Рейтинг@Mail.ru Создать сайт бесплатно