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

Среда, 23.05.2012, 07:48
Приветствую Вас Гость

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

Форма входа

Категории раздела

Дополнительно

Реклама

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

- Ага, вот эти студенты

- Не-не-не-не-не-не-не, Вейерштрасс, не-не-не!

- Сегодня я покажу вам особенный, УЛИЧНЫЙ матан. Хотите увидеть немного матана? Вот ты, что ты делаешь?

- Нахожу предел! понятно?! предел нахожу!!

- Ты уверен что ты находишь предел? Уверен что не что-то другое?

- Да, уверен.. Е-МА НАРОД!!!! ЭТО ЖЕ СУПРЕМУМ!!! ДЕМОН КУДА ТЫ ДЕЛ ПРЕДЕЛ??!!! ФАК МОЙ МОСК!!!

- O_O

Поиск

Наш опрос

Статистика

Онлайн всего: 13

Ныкаются: 13

Пользователей: 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
Просмотров: 1202 \| Загрузок: 0 \| Рейтинг: 0.0/0 \|

Всего комментариев: 0