2 вариант І. Рассмотрите рисунок: а) Сколько концевых вершин имеет граф? б) Какую максимальную длину имеют цепи в этом графе? в) Сколько цепей, соединяющих начальную точку с концевой, имеют длину равную 3? г) Пусть данное дерево изображает случайный опыт. Сколько элементарных событий в этом опыте? 2. Сколько вершин в дереве, в котором 37 ребер? 3. Постройте дерево в котором 7 вершин, причем 4 из них концевые.

2 вариант

І. Рассмотрите рисунок:

а) Концевыми вершинами графа называют вершины, которые имеют степень 1, то есть связаны только с одной другой вершиной. Подсчитаем количество концевых вершин на рисунке.

На рисунке 4 концевые вершины.

Ответ: 4

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

Максимальная длина цепи равна 3.

Ответ: 3

в) Цепи, соединяющие начальную точку с концевой и имеющие длину 3, это пути от верхней вершины до каждой из концевых вершин через две промежуточные вершины. Подсчитаем количество таких цепей.

Таких цепей 4.

Ответ: 4

г) Если данное дерево изображает случайный опыт, то элементарные события соответствуют концевым вершинам дерева. Количество элементарных событий равно количеству концевых вершин.

В данном случае элементарных событий 4.

Ответ: 4

2. В дереве количество вершин всегда на 1 больше количества ребер. Если в дереве 37 ребер, то количество вершин можно найти, прибавив 1 к количеству ребер.

Количество вершин = 37 + 1 = 38

Ответ: 38

3. Постройте дерево в котором 7 вершин, причем 4 из них концевые.

      A
     /|\
    B C D E
   / \
  F   G

В этом дереве:

• 7 вершин (A, B, C, D, E, F, G)
• 4 концевые вершины (C, D, E, F)

Ответ: Дерево построено.