Олимпиадные задачи из источника «глава 13. Графы-2» для 7 класса

20 команд сыграли круговой турнир по волейболу.

Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, ..., 19-я – у 20-й.

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

В некотором государстве каждый город соединён с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

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

Каждое из рёбер полного графа с 9 вершинами покрашено в синий или красный цвет.

Докажите, что либо есть четыре вершины, все рёбра между которыми – синие, либо есть три вершины, все рёбра между которыми – красные.

Каждое из рёбер полного графа с 17 вершинами покрашено в один из трёх цветов. Докажите, что есть три вершины, все рёбра между которыми – одного цвета.

Каждое из рёбер полного графа с 6 вершинами покрашено в один из двух цветов.

Докажите, что есть три вершины, все рёбра между которыми – одного цвета.

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

На конференции присутствуют 50 учёных, каждый из которых знаком по крайней мере с 25 участниками конференции.

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

В стране Озёрная семь озер, соединённых между собой десятью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?

В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом каждые два города соединяет ровно один путь.

Сколько в этой стране дорог?

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

В графе все вершины имеют степень 3. Докажите, что в нём есть цикл.

Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется <i>висячей</i>).

Докажите, что в дереве каждые две вершины соединены ровно одним простым путем.

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

В связном графе степени четырёх вершин равны 3, а степени остальных вершин равны 4.

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

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

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

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

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

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

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