Проверочная работа «Дерево. Свойства дерева» Вариант 1 1. Определите, какие из следующих утверждений верны: а. В дереве может быть только одна вершина. б. Степень вершины в ориентированном графе это количество входящих и исходящих дуг. в. Цепь - это путь, где каждое ребро встречается более одного раза. г. Граф без циклов называется сетью. 2. Определите количество концевых вершин в дереве : S / Н Н / \ НННН / \ НННН 3. Выполните задание: Постройте дерево случайного опыта для подбрасывания монеты 2 раза. Определите количество концевых вершин. 4. Выполните задание: Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице. Постройте дерево и определите длину кратчайшего пути между пунктами А и Е. A B C D E A 3 2 B 3 4 4 C 4 4 3 D 2 4 4 E 3 5. Постройте дерево и определите количество дорог, ведущих из пункта А в пункт F. A B C D E H F 6. Придумайте пример из жизни, который можно представить в виде дерева, и изобразите его.

Ответ:

Привет! Разбираемся с твоим вариантом контрольной работы по теории графов. Тут есть где развернуться!

1. Определите верные утверждения:

• а. В дереве может быть только одна вершина. Это неверно, в дереве может быть много вершин.
• б. Степень вершины в ориентированном графе — это количество входящих и исходящих дуг. Это верно по определению.
• в. Цепь — это путь, где каждое ребро встречается более одного раза. Это неверно, в цепи каждое ребро встречается ровно один раз.
• г. Граф без циклов называется сетью. Это неверно, граф без циклов называется деревом. Сеть — это более общее понятие.

Верное утверждение: б

2. Количество концевых вершин в дереве:

Считаем концевые вершины (те, у которых только один «ребенок»):

       S
      / \
     H   H
    / \ / \
   H H H H
  / \ / \
 H H H H

Концевые вершины — это все H в самом низу. Их 4.

Количество концевых вершин: 4

3. Дерево случайного опыта для подбрасывания монеты 2 раза:

Дерево будет выглядеть так:

       Начало
      /      \
   Орел (O)   Решка (Р)
  /  \      /  \
Орел Решка Орел Решка
(OO)   (OP)  (PO)   (PP)

Концевые вершины: OO, OP, PO, PP. Их 4.

Количество концевых вершин: 4

4. Кратчайший путь между пунктами A и E:

Сначала построим граф на основе таблицы:

Теперь найдем кратчайший путь:

• A → D = 2
• A → B = 3

Из D:

• D → C = 4 (A → D → C = 2 + 4 = 6)
• D → B = 4 (A → D → B = 2 + 4 = 6)

Из B:

• B → E = 4 (A → B → E = 3 + 4 = 7)
• B → C = 4 (A → B → C = 3 + 4 = 7)

Из C:

• C → E = 3 (A → C → E = 6 + 3 = 9)

Кратчайший путь: A → D. Далее ищем путь от D к E:

• D → B → E = 4 + 4 = 8 (A → D → B → E = 2 + 8 = 10)
• D → C → E = 4 + 3 = 7 (A → D → C → E = 2 + 7 = 9)

Сравним пути:

• A → B → E = 7
• A → D → C → E = 9

Кратчайший путь: A → D (2) → C (4) → E (3) = 9

Длина кратчайшего пути: 9

5. Дерево и количество дорог из A в F:

Считаем количество путей из A в F:

• A → B → E → F
• A → B → E → H → F
• A → D → E → F
• A → D → E → H → F
• A → D → H → F
• A → C → H → F

Количество дорог: 6

6. Пример из жизни, который можно представить в виде дерева:

Пример: Генеалогическое древо семьи. У каждого человека есть родители, у родителей — свои родители и так далее. Это можно представить в виде дерева, где корень — это самый старый известный предок, а листья — это потомки.

Надеюсь, теперь тебе всё понятно! Если что, обращайся!

Ответ: Решения выше.

Проверка за 10 секунд: Убедись, что все ответы соответствуют логике вопросов и пересмотри вычисления.

Круто! Ты разобрался с этой контрольной! Продолжай в том же духе!