Дерево как граф без цикла

Антон пошёл с отцом в тир. Они договорились, Андрей делает5выстрелов и за каждое попадание получает ещё по2выстрела. Андрей выстрелил19раз. Сколько раз он попал? Решите задачу, заполнив пропуски в решении задачи. Решение. Стрельбу Антона можно описать , которое называется корневым деревом. В этом дереве все вершины, кроме верхней соответствуют . Если Антон , то степень соответствующей вершины равна 3, если - 1. Степень верхней вершины равна , дерево имеет вершин и рёбер. Пусть n - число попаданий. Тогда Граф содержит n вершин степени 3, (19-n) вершин степени 1 и одну вершину степени 5. Т.к. сумма степеней вершин графа равна удвоенному числу рёбер получим, 3n+(19-n)+5=38; 2n = - 24; 2n = ; n = . Ответ: Антон попал раз.

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

Граф называется плоским, если его рёбра не пересекаются (в точках отличных от вершин). Плоский граф разбивает плоскость на части, которая называются гранями. Формула Эйлера. Если связанный плоский граф сvвершинами иeрёбрами разбивают плоскость наfграней, тоv-e+f=2.Установите соответствия между графами и количеством его граней.

Сформулируйте понятия, подставив в прямоугольники слова по смыслу. Деревья - это связные графы без . Любые вершины дерева соединены лишь маршрутом. В дереве невозможно в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру или более раз. В любом дереве есть ровно путь из каждой вершины в каждую . Число q ребер графа находится из соотношения , где n — число вершин дерева. У деревьев количество ребер, которое только может быть у графа. У деревьев число ребер, которое может быть у графа без циклов. дерево - дерево, у которого есть ровно вершина степени , все остальные вершины имеют степень 3 или 1. Вершина степени называется вершиной.

Сопоставьте дерево с его диаметром.

Выберите верные утверждения.

Решите задачи. 1) Какое максимальное число висячих вершин может иметь дерево, построенное на 9 вершинах? Ответ: 2) Какое минимальное число висячих вершин оно может иметь? Ответ:

Сформулируйте утверждения, подставив в прямоугольники слова по смыслу. Определение. Вершина , степень которой равна называется вершиной. Теорема. В с более чем вершиной есть висячая . Теорема. В дереве вершин на больше числа . Обратная теорема. Если в графе вершин на одну , чем рёбер, то он является .

Сформулируйте утверждения, подставив в прямоугольник слова по смыслу. 1) У дерева количество на единицу меньшее количество . 2) В любом дереве с 5 вершинами ребра. 3) В любом дереве с 17 рёбрами вершин.

Туристическая фирма планирует посещение туристами на Кавказе различных городов: Ессентуки, Кисловодск, Нальчик. Сколько существует вариантов такого маршрута?

Установите соответствие между способами обхода бинарного дерева и его вариантами по готовому чертежу.

В стране25 озёр, соединённых между собой36 каналами, Так что от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?