РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ ГРАФОВ

1

В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

2

На столе лежит 5 коробочек. В некоторых коробочках лежит по пять коробочек, в некоторых из них тоже лежит по пять коробочек, и так далее, а пустых коробочек получилось всего 25. Сколько всего коробочек?

3

Между зажимами A и B включено несколько сопротивлений. Каждое сопротивление имеет входной и выходной зажимы. Какое наименьшее число сопротивлений необходимо иметь и какова может быть схема их соединения, чтобы при порче любых девяти сопротивлений цепь оставалась соединяющей зажимы A и B, но не было короткого замыкания? (Порча сопротивления: короткое замыкание или обрыв.) *

4

В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?

5

В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?

6

Клетчатая плоскость раскрашена десятью красками так, что соседние (то есть имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Каково минимально возможное число пар соседних красок? (Две краски называются соседними, если ими покрашены какие-то две соседние клетки.)

Нажимая кнопку "Отправить", вы соглашаетесь с пользовательским соглашением и политикой конфиденциальности.