ГРАФЫ

Во многих ситуациях удобно изображать объекты точками, а связи между ними--линиями или стрелками. Такой способ представления называется графом. Например, схема метро --это граф. Точки называют вершинами графа, а линии--ребрами.

Вершину называют чётной, если из неё выходит чётное число рёбер и нечётной в противном случае. Граф называют связным, если между любыми вершинами существует путь, состоящий из рёбер графа, ориентированнымесли на каждом ребре указано направление, плоским --если он нарисован на плоскости и его ребра не пересекаются (во внутренних точках).

Пример:

В стране Радонежии некоторые города связаны между собой авиалиниями. Из столицы выходит 1985 авиалиний, из города Дальнего --одна, а из остальных городов --по 20 линий. Докажите, что из столицы можно добраться до Дальнего (быть может, с пересадками).

Рассмотрим множество городов, до которых можно добраться из столицы. Это граф: его вершины--города, ребра--авиалинии, их соединяющие. Из каждой вершины графа выходит столько рёбер, сколько всего авиалиний выходит из соответствующего города. Граф содержит нечётную вершину --столицу. Поскольку число нечётных вершин в графе чётно, в нем есть ещё одна нечётная вершина. Этой вершиной может быть только город Дальний.

Задачи:

1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля -- Меркурий, Плутон -- Венера, Земля -- Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун - Сатурн,

Сатурн -- Юпитер, Юпитер -- Марс и Марс -- Уран. Можно ли добраться (возможны пересадки) с Земли до Марса?

Ответ6

нет

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

Ответ:

10-ю способами

3. Доска имеет форму креста, который получается, если из квадратной доски 4x4 выкинуть угловые клетки. Можно ли ходом шахматного коня обойти эту доску и вернуться на исходное поле, побывав на всех полях ровно по одному разу?

Ответ:

да

4. В деревне есть 15 телефонов, а АТС отсутствует. Можно ли телефоны соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Ответ:

невозможно

5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей.

Примечание. Если Петя друг Васи, то Вася - друг Пети.

Ответ:

нет

6. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Можно ли из любого города можно добраться до любого другого (возможно,

проезжая через другие города).

Ответ:

нельзя

7. Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаша от бумаги?

Ответ:

можно, можно, нельзя

8. Можно ли так расставить фишки в клетках доски 8х8, чтоб в любых двух столбцах количество фишек было одинаковым, а в любых двух--различным?

Ответ:

можно

9. В футбольном первенстве Мячландии изъявили желание участвовать сразу 2008 команд. Причем турнир решено провести так, что каждая команда встречается со всеми другими по одному разу. Может ли случится так, что в какой-то момент времени каждая из участвующих команд сыграет ровное количество матчей?

Ответ:

ситуация, описанная в задаче не существует ни в Мячландии ни в какой либо другой стране

10. В Тридевятом царстве лишь один вид транспорта -- ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний -- одна, а из всех остальных городов по 20. Можно ли из столицы долететь в Дальний (возможно с пересадками)?

Ответ:

можно