Составить очень краткий конспект по ниже приведённому тексту 46) Деревья Напомним, что такое цепь и цикл в графе. Цепь - это простой путь, то есть путь, и котором нейроны не понторинтси. повторяются вершины, то и ребри тоже не повторяются (рис. 1, 6). Цикл в графе - это замкнутый путь, в котором не повторяются рёбра и не повторяются промежуточные вершины. Очень интересны и полезны графы, в которых нет циклов. Если в связном графе нет циклов, то такой граф называют деревом. Дерево - связный граф без циклов. Цепь тоже яиляется деревом, поскольку в цепи нет циклов. И даже граф, состоящий из одной-единственной вершины без ребер, также можно рассматривать как простейшее дерево (рис. 1, в). a) Дерево, в котором 7 вершин б) Цепь - это дерево в) Простейшее дерево одна вершина Рисунок 1 пРимеР 1. На рисунке 2 показана схема подоснабжения в небольшом посёлке. Трубы идут от водонапорной башни и ветвятся, пролегая вдоль улиц. Из больших труб отходят малые к домам. Граф водопровода - дерево. Здесь можно выделить начальную вершину - водонапорную башню. 000 Водонапорная башия ПРИМЕР 2. Возьмём симметричную монету и подбросим её 3 раза. Чтобы изобразить этот случайный опыт, построим дерево, От начальной вершины S нарисуем ветви нниз к вершинам, которые обозначим О (орёл) и Р (решка) это пеаультаты первого броска. От каждой из них идут ещё два ребра вниз к вершинам О и Р, изображающим результаты иторого броска. Точно так же покажем результаты третьего броска (рис. 3). Получилось дерево случайного эксперимента. В этом дереве восемь цепей, ведущих из начальной вершины S конценые вершины: Водопровод Рисунок 2 SOOO, SOOP, SOPO, SOPP, SPOO, SPOP, SPPO и SPPP. Каждая цепь изображает одно из восьми возможных элементарных событий в этом случайном опыте. В примерах 1 и 2 понятно, какую вершину следует выбрать в качестве начальнои, или корневой, вершинн, из которой «растёт» дерево. Вода по трубам течёт из водонапорной башни. Это и есть начальная вершина на схеме водоснабжения (см. рис. 2). Во втором примере начальная вершина изображает начальный момент, когда монету ещё не бросили ни разу, Мы её обозначили букьой S от слова start, имея в виду начало случайного опыта. Рисунок 3 Название «дерево» происходит оттого, что цепи «ветвятся», не образуя циклов. Единственная разница - в природе деревья обычно растут снизу вверх, а математические деревья мы рисуем так, как нам удобно. Бывают бесконечные деревья, то есть деревья, в которых бесконечно много вершин и рёбер. Многоточие на рисунке 4 показывает, что дерево простирается вправо до бесконечности. ПРИМЕР 3. Предположим, что кто-то пытается послать СМС из леса, где связь очень плохая. Каждая отдельная попытка может оказаться неудачной, и в таком случае телефон предпримет следующую. Будем считать, что попыток может быть сколько угодно. Такой случайный опыт можно изобразить с помощью бесконечного графа. Начинается граф в вершине S, каждая попытка может оказаться неудачной (вершина Н) или удачной (вершина У) (см. рис. 4). Рисунок 4. Бесконечное дерево случайного эксперимента Вопросы 1 Что такое дерево? 2 Может ли в дереве быть 4 ребра; бесконечно много рёбер? 3 Бывают ли в дереве петли; цепи; циклы? Задачи 1 Какие из графов на рисунке 5 являются деревьями? б) B) r) д) Рисунок 5