Вариант 2 Самостоятельная работа 1 ГДЗ Самостоятельные и контрольные работы Босова 9 класс (Информатика)

1. Сколько вершин и рёбер у графа, представленного на рисунке?
В ответе укажите число вершин затем число рёбер без запятой (например, 23).
Количество вершин: 5
Количество ребер: 9
Ответ: 59
2. Установите соответствие.
3. В стране Цифромании есть 6 городов с названиями 1, 2, 3, 4, 5, 6. Руководство страны сообщило, что организует железнодорожное сообщение между городами в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 2.
Постройте граф, соответствующий проекту железнодорожного сообщения между городами Цифромании.
Если двоичное число заканчивается на четную цифру, то оно делится на 2. Граф ориентированный, т.к., например 12 делится на 2, а 21 не делится. Между четными цифрами возможны неориентированные (в две стороны) дороги.
4. На рисунке представлено генеалогическое дерево Ивана, где отмечены одни мужчины.
Руслан сын Леонида, а Леонид сын Ефима. У Леонида есть брат, Никита. Никита для Руслана дядя.
Ответ: Никита дядя Руслана (Руслан племянник Никиты)
5. На рисунке изображена схема дорог, связывающих торговые точки А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки К?
Количество путей из А в К равно сумме путей из А в Д, из А в Е и из А в Б.
Количество путей из А в Д равно сумме путей из А в Б и из А в Е.
Количество путей из А в Е равно сумме путей из А в В и из А в Г.
В скобках указано количество путей из А до данной вершины:
В(1), Г (1), Е(2), Б(3), Д(2+3=5), К(2+5+3=10)
Ответ: 10
6. Дополнительное задание. В некоторой стране 12 городов. Из каждого города выходят четыре дороги, соединяющие его с другими четырьмя городами. Сколько всего дорог в этой стране?
Так как каждая дорога соединяет два города, то количество дорог будет в два раза меньше, суммы количества дорог, выходящих из каждого:
(4*12)/2=24
Ответ: 24

Выполнение

1. На рисунке 5 вершин и 9 рёбер, значит записываем число вершин и число рёбер подряд:

$$59$$

2. Соответствие по рисункам:

• взвешенный граф — граф, у которого на рёбрах указаны веса;
• ориентированный граф — граф, в котором на рёбрах есть стрелки;
• дерево — связный граф без циклов.

3. Ребро между городами есть тогда и только тогда, когда двузначное число, составленное из их номеров, делится на 2. Это возможно, если последняя цифра чётная. Значит, из каждого города ведут дуги ко всем чётным городам, а между чётными городами связи есть в обе стороны.

Граф ориентированный.

4. Руслан — сын Леонида, Леонид — сын Ефима. У Леонида есть брат Никита, значит Никита — дядя Руслана.

Ответ: Никита — дядя Руслана.

5. Обозначим число путей от точки А до каждой вершины:

• в точку В — $$1$$;
• в точку Г — $$1$$;
• в точку Е — $$1+1=2$$;
• в точку Б — $$3$$;
• в точку Д — $$2+3=5$$;
• в точку К — $$2+5+3=10$$.

Ответ: $$10$$

6. Каждая из 12 вершин имеет степень 4, значит сумма степеней равна $$12 \cdot 4 = 48$$. Каждая дорога учитывается дважды, поэтому число дорог:

$$\frac{12 \cdot 4}{2}=24$$

Ответ: $$24$$