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

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

Занятие 18. Графы (17.03.2007)

Граф — это набор точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а отрезки – рёбрами.

Количество рёбер, выходящих из вершины графа, называется степенью этой вершины. Вершина называется чётной, если её степень чётна, и нечётной, если её степень нечётна.

0.

Докажите, что в любом графе количество нечётных вершин чётно.

1.

Ваня нарисовал 6 точек и некоторые из них соединил отрезками. Известно, что из пяти точек выходит соответственно 5, 5, 4, 3 и 2 отрезка. Сколько отрезков выходит из шестой точки?

2.

a)

Сеня поспорил с Димой. Он утверждает, что сможет нарисовать граф с 8 вершинами, степени которых равны 7, 7, 6, 5, 3, 3, 2, 2 соответственно. Кто выиграет спор?

б)

Кто выиграл бы спор, если бы Сеня утверждал, что сможет нарисовать граф со 100 вершинами, степени которых равны 1, 1, 2, 2, ..., 50, 50?

3.

Семеро школьников, уезжая в 2006 году из Летней школы «Калейдоскоп», договорились, что каждый из них напишет письмо трём другим. Может ли каждый из них получить письмо от того, кому он отправил своё письмо?

4.

Пять вершин куба покрашены в красный цвет. Верно ли, что обязательно найдутся три ребра, у которых оба конца красные?

5.

На собрании присутствовало n человек. Известно, что у любых двух знакомых из них нет общих знакомых, а у любых двух незнакомых – ровно два общих знакомых. Докажите, что у всех присутствующих на собрании одно и то же число знакомых.

6.

Можно ли 10 телефонов соединить проводами так, чтобы каждый провод соединял ровно два телефона, любые два телефона были соединены не более, чем одним проводом, и чтобы между любыми четырьмя телефонами проводов было бы проведено ровно три?

7.

На Малом Мехмате дети договорились послать друг другу электронные письма. Те из них, у кого число знакомых чётно, отправят письма всем знакомым, а те, у кого число знакомых нечётно, отправят письма всем незнакомым. Придя домой и включив компьютер, Гоша увидел, что ему пришло 99 писем. Докажите, что он получит ещё хотя бы одно.