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

Занятие 12. Графы-I

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

1.	Нарисуйте какой-нибудь а) связный; б) несвязный граф.
2.	Приведите пример связного графа, который при удалении любого ребра а) становится несвязным; б) остаётся связным (вершины не удаляют).
3.	Граф состоит из 29 вершин, из каждой из которых исходит не меньше 14 рёбер. Докажите, что этот граф связный.
4.	Каждые два города некоторой страны соединены либо автобусным, либо железнодорожным маршрутом. Докажите, что турист может объехать все города этой страны, пользуясь лишь одним видом транспорта (при этом не требуется, чтобы каждый город был посещён лишь один раз).

Вершину графа называют чётной, если из неё исходит чётное количество рёбер, и нечётной, если нечётное.

5.	Граф имеет 100 вершин, и из каждой вершины исходит по 4 ребра. Сколько рёбер в этом графе?
6.	Докажите, что в любом графе число нечётных вершин чётно.
7.	В Тридевятом царстве лишь один вид транспорта — ковёр-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных — по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
8.	В некотором связном графе все вершины чётны. Одно из рёбер удалили (вершины не удаляли). Докажите, что граф остался связным.