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

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

Руководитель Блинков Александр Давидович
2007/2008 учебный год

Версия для печати

Графы 2

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

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

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

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

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

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

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

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

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

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS