возьмем какую-либо вершину. просто выбрали любую. теперь "идем" по ребрам графа, не проходя по каждому ребру более 1 раза. поскольку циклов нет, рано или поздно мы "" в какую-нибудь вершину, у которой только 1 ребро, по которому мы в нее зашли. заметим, что тогда ее степень равна 1. возьмем и выкинем эту вершину и ее единственное ребро из графа. теперь кол-во вершин в графе - n-1, а ребер m-1 (m - кол-во ребер в изначальном графе). при этом связности мы не испортили, т.к. у нее было только одно ребро, которое мы выкинули с этой же вершиной!
проделаем ту же операцию. таким образом мы уменьшаем кол-во ребер и вершин каждым шагом на 1. рассмотрим граф, в котором осталось 2 вершины. одна из этих вершин имеет степень 1. значит и вторая тоже (при условии, что нет двойных ребер, но граф связен, поэтому их нет). уберем последнюю "единичную" вершину. у нас осталась одна вершина и ни одного ребра. а значит вершин изначально было на 1 больше, чем ребер. доказано.
Я предлагаю действовать перебором. Числитель не может быть меньше 10 (т.к. двузначный). Если он 10, то после вычитания станет 9, тогда знаменатель должен стать (после удвоения) 99 (чтобы дробь стала быть равной 1/11). Но никакое целое число после удвоения не равно 99, значит 10 в качестве числителя не подходит. Берём 11. После вычитания 1 станет 10. Значит знаменатель станет 110 (опять чтобы получилось 1/11)Чтобы он (знаменатель) стал 110, первоначально он должен быть 55. Т.е. дробь 11/55 нам подходит, т.к. после преобразований она становится 10/110 = 1/11. Рассуждая дальше, найдём ещё такие числа, например 13/66 - тоже подходит, и оно меньше, чем 11/55, дальше 15/77 и оно ещё меньше, 17/88 - следующее и 19/99 - последнее, т.к. дальше пойдут трёхзначные знаменатели. И эта последняя дробь наименьшая из всех. Значит она и есть ответ. И сумма числителя и знаменателя 118
ответ:
пошаговое объяснение:
возьмем какую-либо вершину. просто выбрали любую. теперь "идем" по ребрам графа, не проходя по каждому ребру более 1 раза. поскольку циклов нет, рано или поздно мы "" в какую-нибудь вершину, у которой только 1 ребро, по которому мы в нее зашли. заметим, что тогда ее степень равна 1. возьмем и выкинем эту вершину и ее единственное ребро из графа. теперь кол-во вершин в графе - n-1, а ребер m-1 (m - кол-во ребер в изначальном графе). при этом связности мы не испортили, т.к. у нее было только одно ребро, которое мы выкинули с этой же вершиной!
проделаем ту же операцию. таким образом мы уменьшаем кол-во ребер и вершин каждым шагом на 1. рассмотрим граф, в котором осталось 2 вершины. одна из этих вершин имеет степень 1. значит и вторая тоже (при условии, что нет двойных ребер, но граф связен, поэтому их нет). уберем последнюю "единичную" вершину. у нас осталась одна вершина и ни одного ребра. а значит вершин изначально было на 1 больше, чем ребер. доказано.
p.s.: где достал(а)? какой город? )
подробнее - на -