Деревья Дерево это частный случай графа, наиболее широко применяемый в программировании. Основные определения



жүктеу 123.73 Kb.
бет2/3
Дата11.11.2022
өлшемі123.73 Kb.
#23733
1   2   3
Деревья граф
лекция 8 икт в инклюз, практика 6 граф, 1. Информатика білім беру саласы ретінде, примеры на граф, 3 дәріс, informatikany-bzd-ortamyzda-alatyn-orny
Дерево

Вершины

Ребра (дуги)

Армия

Солдаты и офицеры

Иерархия (командир - подчиненный)

Династия (родословная по мужской линии)

Монархи

Отношение "отец - сын"



Рис. 11.12. Корневое дерево высоты 3
Мы будем изучать и использовать только один частный случай ориентированных деревьев - корневые деревья (см. рис. 11.12).
Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: кореньлистья (другое их название: терминальные вершины ) и остальные вершины ( нетерминальные ); причем должны выполняться два обязательных условия:

  1. из листьев не выходит ни одна дуга ; из других вершин может выходить сколько угодно дуг ;

  2. в корень не заходит ни одна дуга ; во все остальные вершины заходит ровно по одной дуге.

Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программированиидеревья "растут" вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья - самыми нижними.
Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.
Граф-дерево
Дерево – это граф без циклов, у которого между парами вершин имеется только одно ребро.

Граф-дерево с 9 узлами и 8 ребрами.
Из каждого узла выходит не более 2 ребер.
Такое дерево называют бинарным.
С помощью дерева удобно составлять упорядоченные комбинации элементов.
Например:
На столе стоит три стакана сока – апельсиновый, виноградный и яблочный. Можно взять только два стакана. Сколько есть возможных вариантов и каких?
По правилу произведения число возможных вариантов: 3⋅2=6. Поскольку, порядок выбора неважен, остаётся 62=3 варианта. Построим граф:

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.
Примеры
Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?
Построим полный граф.

Каждая тройка ребят соответствует треугольнику в этом графе.
Например, Вася образует три треугольника с оставшимися тремя ребятами:
3⋅22=3 - ВПК, ВТК и ВТП
Без Васи есть только один треугольник – ПКТ
Общее количество треугольников 3+1=4
Ответ: 4 варианта
Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?
Построим полный граф.

Каждые три овоща на полном графе образуют треугольник.
Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников 5⋅42=10, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).
Количество треугольников, в которые не входит капуста: 4⋅32=6
Количество треугольников, в которые не входят капуста и морковь: 3⋅22=3
Количество треугольников, в которые не входят капуста, морковь и перец: 2⋅12=1
Итого 10+6+3+1 = 20 различных треугольников.
Ответ: 20 салатов
Примечание: по расчетной формуле C63=6⋅5⋅41⋅2⋅3=20 - ответ правильный.
Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.
Если построить полный граф с 11-ю вершинами, каждая тройка команд в нём образует треугольник.

По аналогии с примерами 1 и 2, общее количество треугольников:
N=(10⋅92+9⋅82)+(8⋅72+7⋅62)+(6⋅52+5⋅42)+(4⋅32+3⋅22)+2⋅12=
=9(10+8)2+7(8+6)2+5(6+4)2+3(4+2)2+1=
=92+72+52+32+1=165
Так, как порядок мест важен, в каждом треугольнике –3⋅2=6 вариантов распределения медалей.
По правилу произведения: 6⋅165=990 - общее количество способов.
Ответ: 990 вариантов
Примечание: по расчетной формуле A311=11⋅10⋅9=990 - ответ правильный.
Пример 4. В столовой есть на выбор

  • два первых блюда: щи (Щ) и борщ (Б)

  • три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т)

  • два напитка: компот (К) и сок (С)

Сколько вариантов обедов можно составить из этих блюд и каких?
По правилу произведения общее количество вариантов обедов: 2⋅3⋅2=12
Построим дерево для перечисления вариантов:

Ответ: 12 вариантов



жүктеу 123.73 Kb.

Поделитесь с Вашими друзьями:
1   2   3




©emirb.org 2022
әкімшілігінің қараңыз

    Басты бет