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

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

Главная | Каталог файлов | Регистрация | Вход | RSS
Меню сайта
Форма входа
Логин:
Пароль:

Войдите, чтобы не видеть рекламу
Категории раздела
Алгебра и геометрия [1]
Английский язык [6]
Ассемблер [2]
Графика [6]
Защита информации [4]
Культурология [2]
Методы оптимизации [1]
Метрология [2]
Моделирование [7]
Основы трансляции [6]
Политология [3]
Пролог [9]
Системный анализ [5]
Сети ЭВМ [11]
Теория автоматов [6]
Тервер [3]
Технологии программирования [9]
Физика [1]
Философия [27]
ЭВМ и системы [13]
Экономика [2]
Экстремальные задачи [4]
Электротехника [1]
Разное [14]
Не из ВолгГТУ [4]
Экология [7]
БЖД [9]
Дополнительно
Реклама


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

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

Поиск
Наш опрос
Вы умеете программировать на
[ Результаты · Архив опросов ]
Всего ответов: 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 Создать сайт бесплатно