МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Графы-1 (знакомство). 29 сентября 2012 года

Граф — совокупность точек, некоторые из которых соединены отрезками. Точки называются вершинами графа, отрезки ребрами.

1.

В деревне 9 домов. Известно, что у Гоши соседи Иван и Роман, Максим сосед Ивану и Михаилу, Виктор — Алексею и Андрею, а также по соседству живут Константин с Андреем, Иван с Михаилом, Константин с Алексеем, Михаил с Романом и больше соседей в означенной деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Гоша огородами пробраться к Андрею за яблоками?

2.

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?

3.

В некотором государстве 6 городов и 10 автодорог, каждая из которых связывает какие-то два города. Между городами устанавливается авиационное сообщение, исходя из принципа экономии: авиационная линия между двумя городами устанавливается тогда и только тогда, когда автомобильная дорога между этими городами отсутствует. Сколько авиалиний будет проведено?

Степень вершины — количество ребер, выходящих из данной вершины.

4.

В стране 1329 городов, из каждого выходит по 4 дороги. Сколько всего дорог в стране?

5.

Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.

6.

Вася считает, что в его классе у всех разное число друзей-одноклассников. Не ошибается ли он?

7.

Иван утверждает, что среди любых а) четырёх; б) пяти; в) шести человек обязательно найдётся либо трое знакомых друг с другом, либо трое незнакомых. Не завирается ли он?

8.

Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько друзей у Пети? (Укажите все решения.)

Дополнительные задачи

9.

Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, ..., n, n.

10.

Докажите, что не существует многогранника, у которого было бы ровно семь ребер.

11.

Верно ли, что два графа изоморфны, если

а)

у них по 10 вершин, степень каждой из которых равна 9?

б)

у них по 8 вершин, степень каждой из которых равна 3?

в)

они связны, без циклов и содержат по 6 ребер?

12.

В некотором городе на любом перекрестке сходятся ровно 3 улицы. Улицы раскрашены в три цвета так, что на каждом перекрестке сходятся улицы трех разных цветов. Из города выходят три дороги. Докажите, что они имеют разные цвета.