Можно ли 21 компьютер соединить проводами так чтобы каждый был соединен с 11 другими
Напомним, что граф> — это набор точек, некоторые из которых соединены линиями. Точки называются вершинами графа, линии — рёбрами.
1. Получите из левой картинки правую, проводя линии между точками (по одной). Около каждой точки подписывайте, сколько из неё выходит линий. Как изменяются числа после каждого дорисовывания линии?
Решение. После каждого дорисовывания степени двух вершин увеличиваются на 1. Вершину графа будем называть чётной, если из неё выходит чётное число рёбер, нечётной — если выходит нечётное число рёбер.
Ответ. Сумма всех чисел равна удвоенному числу ребер, так как каждое ребро увеличивает степень ровно двух вершин на 1.
Решение. Рассмотрим граф, в котором телефоны — это вершины. Вершины будем соединять ребром, если телефоны соединены проводом. В любом графе число нечетных вершин четно. Значит, так соединить телефоны не получится.
4. В классе 30 человек. Может ли быть так, что у 9 из них по 3 друга в классе, у 11 — по 4 друга и у 10 — по 5 друзей?
Решение. Посчитаем число нечетных вершин в этом графе. Их 9 + 10 = 19 — нечетное число. Значит, такого не может быть.
Решение. Пусть в графе a городов. Тогда a ·3⁄2 = 100, но тогда 3 a = 200, чего не может быть, так как 200 не делится на 3.
Решение. Рассмотрим граф, вершины которого соответствуют отрезку. Вершины будем соединять ребром, если соответсвующие отрезки пересекаются. Тогда получим, граф в котором нечетное число нечетных вершин. Значит, так нарисовать отрезки не получится.
7. В некотором государстве 99 городов, некоторые пары городов соединены дорогами длиной в 1, 3 или 5 вёрст, причём от каждого города до каждого по этим дорогам можно добраться ровно одним способом. Из каждого города в каждый другой отправились гонцы с важным донесением. Докажите, что суммарное расстояние, пройденное гонцами, делится на 4.
Решение. Рассмотрим произвольную дорогу N . Эта дорога делит все города на две группы так, что из города одной группы нельзя проехать в город другой группы, не проезжая через N . Пусть в одной группе a городов, тогда в другой 99 − a . Но тогда по этой дороге проехали всего 2· a ·(99 − a ) раз. Т.к. a и 99 − a разной четности, то 2· a ·(99 − a ) делится на 4. Значит, и вся сумма делится на 4.
8. На Малом Мехмате дети договорились послать друг другу электронные письма. Те из них, у кого число знакомых чётно, отправят письма всем знакомым, а те, у кого число знакомых нечётно, отправят письма всем незнакомым. Придя домой и включив компьютер, Гоша увидел, что ему пришло 99 писем. Докажите, что он получит ещё хотя бы одно.
Решение. Будем называть ребёнка чётным, если у него четное число знакомых, и нечётным в противном случае. Заметим, что число нечётных детей чётно. Посмотрим, от кого Гоша мог получить письма. Либо от четных знакомых, либо от нечетных незнакомых. Разберем два случая.
1) Гоша — чётный. Тогда он получит чётное число писем от знакомых и еще чётное число от незнакомых.
2) Гоша — нечётный. Тогда он получит нечётное число писем от незнакомых и еще нечётное число писем от знакомых.
В обоих случаях получили, что Гоша получит чётное число писем. Т.е. еще хотя бы одно.
Можно ли 21 компьютер соединить проводами так чтобы каждый был соединен с 11 другими
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён ровно с пятью другими?
Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а рёбра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна 5. Подсчитаем количество рёбер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчёте каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число рёбер графа должно быть равно 15·5 : 2. Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? Ответ объяснить.
Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.
Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.
Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.
Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.
Можно ли 21 компьютер соединить проводами так чтобы каждый был соединен с 11 другими
Часовой пояс: UTC + 3 часа
Запрошенной темы не существует.
Часовой пояс: UTC + 3 часа
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB | Kolobok smiles © Aiwan
