Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Деревья и их простейшие свойства

Читайте также:
  1. B-деревья
  2. Агрохимические свойства
  3. Алгоритмы. Основные свойства
  4. Аллювиальные отложения. Условия образования. Их разновидности. Инженерно- геологические свойства.
  5. АТМОСФЕРА ЗЕМЛИ. ФИЗИЧЕСКИЕ СВОЙСТВА ВОЗДУХА
  6. Базовые свойства.
  7. Билет 5 Основные черты, функции и Юридические свойства Конституции
  8. Биомеханические свойства и особенности строения ОДА человека
  9. Биомеханические свойства мышц
  10. Биомеханические свойства мышц
  11. Биохимические свойства
  12. Биоэнергетика и целебные свойства деревьев



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

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

Докажем сейчас следующую достаточно важную теорему.

Теорема. Если граф G является деревом, то число его ребер (т) и число его вершин (п) связаны соотношением т = п – 1.

Доказательство этой теоремы проведем по индукции по числу вершин. Если данный граф содержит всего 2 вершины, то в нем только 1 ребро, и нужное соотношение выполнено. Пусть наше утверждение выполнено для любого дерева, число вершин которого строго меньше п, Докажем его для дерева G,содержащего п вершин. Возьмем висячую вершину дерева G и удалим ее из графа (вместе с единственным ребром, выходящим из этой вершины). Тогда новый граф также является деревом: новый граф не содержит контуров (циклов), он остается связным. (Если бы новый граф оказался несвязным, то какие-то две вершины графа G были бы связаны между собой через удаленную (висячую) вершину. В этом случае степень этой висячей вершины была бы больше или равна 2, что невозможно). Таким образом, новый граф является деревом, и по индукционному предположению для него число ребер меньше числа вершин на единицу. Так как число вершин и число ребер нового графа отличается от числа вершин и ребер “старого” графа G на единицу, то для графа G также выполнено то же самое соотношение. Таким образом, индукция проведена, и теорема доказана.

На самом деле верно и обратное утверждение, которое является частью более общей теоремы, отражающей простейшие свойства дерева.

Теорема.Следующие 4 условия равносильны:

  • граф G является деревом;
  • число ребер (т) и число вершин в графе (п) связаны соотношением т = п – 1;
  • любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;
  • граф G связен и не содержит контуров.

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

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





Дата добавления: 2015-05-09; Просмотров: 58; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.80.60.91
Генерация страницы за: 0.005 сек.