Проверочная работа по теме «Графы. Деревья» Вариант 1 1. Выбрать граф, который является деревом. Объяснить свой выбор. a) б) N 2. Построить граф, в котором 6 вершин, и он является деревом. a) Проверочная работа по теме «Графы. Деревья» Вариант 2 Выбрать граф, который является деревом. Объяснить свой выбо б) 2. Построить граф, в котором 5 вершин, и он является деревом. 3. Построить дерево, в котором есть 4 вершины степени 3. 4. Построить дерево вариантов посадки яблони, груши и вишни (порядок посадки важен). 1. 3. Построить дерево, в котором есть 3 вершины степени 4. 4. Построить дерево вариантов распределения Ивана, Матвея и Петра по трём местам в турнирной таблице (порядок важен). G

Привет! Давай выполним это задание по графам и деревьям. Вариант 1 1. Чтобы граф являлся деревом, он должен быть связным и не содержать циклов. * Граф а) является деревом, так как он связный и не имеет циклов. Все вершины соединены, и нет замкнутых путей. * Граф б) не является деревом, так как содержит цикл (треугольник). 2. Дерево с 6 вершинами можно построить следующим образом: расположим вершины в линию и соединим их последовательно. 3. Дерево, в котором есть 4 вершины степени 3, построить невозможно, так как сумма степеней всех вершин должна быть равна удвоенному числу ребер. В данном случае сумма степеней была бы 3+3+3+3 = 12, а число ребер в дереве с 4 вершинами равно 3. Это противоречит условию. 4. Дерево вариантов посадки яблони, груши и вишни (порядок важен): 1. Яблоня - Груша - Вишня 2. Яблоня - Вишня - Груша 3. Груша - Яблоня - Вишня 4. Груша - Вишня - Яблоня 5. Вишня - Яблоня - Груша 6. Вишня - Груша - Яблоня Вариант 2 1. Чтобы граф являлся деревом, он должен быть связным и не содержать циклов. * Граф а) не является деревом, так как содержит цикл (треугольник). * Граф б) является деревом, так как он связный и не имеет циклов. Все вершины соединены, и нет замкнутых путей. 2. Дерево с 5 вершинами можно построить следующим образом: расположим вершины в линию и соединим их последовательно. 3. Дерево, в котором есть 3 вершины степени 4, построить невозможно, так как максимальная степень вершины в дереве с 3 вершинами равна 2. Каждая вершина может быть соединена только с двумя другими. 4. Дерево вариантов распределения Ивана, Матвея и Петра по трём местам в турнирной таблице (порядок важен): 1. Иван - Матвей - Петр 2. Иван - Петр - Матвей 3. Матвей - Иван - Петр 4. Матвей - Петр - Иван 5. Петр - Иван - Матвей 6. Петр - Матвей - Иван

Ответ: Решения представлены выше.

Ты молодец! У тебя всё получится!