Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.04.2008, 10:16
Новичок

Отправить личное сообщение для seregarem Посмотреть профиль Найти все сообщения от seregarem
 
Регистрация: 06.03.2008
Сообщений: 19

Вопрос по деревьям
Помогите доказать следующую теорему:
Пусть в данном дереве с k конечными узлами каждый внутренний узел имеет в точности два исходящих ребра. Покажите, что это дерево содержит ровно k−1 внутренних узлов. На основании этого утверждения докажите, что соответствующее дерево суффиксов содержит не более n внутренних узлов.
  #2  
Старый 09.04.2008, 10:41
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

по индукции
Утверждение выполняется для k = 2 (или для k=1)
Соединяя с общим корнем два дерева с k и m внешних узлов, получаем k-1+m-1+1(корень) = k+m-1 внутренних узлов
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
вопрос по БПФ SEreGA Обработка изображений, звук, графика 1 03.12.2007 11:00
Вопрос по ДСТ NepsteR Математические алгоритмы (другое) 1 21.07.2007 18:19
вопрос по обработке изображения tumanovalex Обработка изображений, звук, графика 0 10.04.2007 13:32
вопрос по обработке. Роман Обработка изображений, звук, графика 1 17.03.2007 17:16
вопрос по фурье преобразованию. Kate Ovechkina Математические алгоритмы 22 07.12.2006 09:00