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

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

Графы 2

1.

В графе каждая вершина покрашена в зеленый или синий цвет. Известно, что каждая синяя вершина соединена с пятью синими и десятью зелеными, а каждая зеленая – с девятью синими и шестью зелеными. Каких вершин больше: синих или зеленых?

2.

В графе вершины пронумерованы числами от 1 до 30, причем вершины соединены ребром, если одно из чисел, записанных в этих вершинах, делится на другое. Сколько компонент связности в этом графе?

3.

Сколько ребер в полном графе с 10 вершинами? Сколько вершин в полном графе с 78 ребрами?

4.

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

5.

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

6.

Докажите, что

1. связный граф, степени всех вершин которого четны, можно нарисовать, не отрывая руки от бумаги и не проводя по одному ребру два раза.
2. связный граф, степени всех вершин которого, кроме двух, четны, можно нарисовать, не отрывая руки от бумаги и не проводя по одному ребру два раза.
3. никакие другие графы, кроме указанных в пунктах a) и b), нарисовать нельзя.

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

7.

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

8.

На какое минимальное количество частей требуется разрезать кусок проволоки, чтобы их этих частей можно было сложить каркас куба?