Задание 11: На рисунке изображён граф. Катя обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Начала она в вершине D. В какой вершине Катя закончила обводить граф?

Чтобы решить эту задачу, нужно понять, что граф можно обвести, не отрывая карандаша и не проводя ни одно ребро дважды, если в нём либо все вершины имеют чётную степень (количество ребер, выходящих из вершины), либо ровно две вершины имеют нечётную степень. В данном случае Катя начала в вершине D, значит, если существует вершина с нечётной степенью, то это D, а вторая вершина с нечётной степенью будет вершиной, где Катя закончила обход графа. Посмотрим на степени вершин: Вершина A: степень 1 Вершина B: степень 1 Вершина C: степень 2 Вершина D: степень 3 Вершина E: степень 2 Вершина F: степень 1 Мы видим, что вершины A, B, D и F имеют нечётную степень. Так как Катя начала в вершине D (степень 3), она закончит в одной из вершин A, B или F. Чтобы выяснить это, посмотрим на граф. D соединена с C, E и F. После D идет C. После C очевидно идет B. После B идет А. После A идет E. После E идет F. Так как Катя начала в вершине D и должна пройти по каждому ребру только один раз, и граф должен быть обведен без отрыва карандаша, определим конечную вершину. В графе вершины A, B, F имеют степень 1, D имеет степень 3, а C и E имеют степень 2. Из вершины D Катя пошла, значит закончит она в одной из вершин A, B или F. Степень вершины показывает, сколько ребер выходит из вершины. Если степень вершины нечетная, то она либо начальная, либо конечная. Рассмотрим вершины с нечетными степенями: A(1), B(1), D(3), F(1). По условию Катя начала в D, следовательно закончит в одной из вершин A, B, F. Закончит Катя в вершине F. Ответ: F