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

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

Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков.

Докажите, что найдутся такие команды <i>А, В</i> и <i>С</i>, что <i>А</i> выиграла у <i>В</i>, <i>В</i> выиграла у <i>С</i>, а <i>С</i> выиграла у <i>А</i>.

Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда<i>А</i>сильнее команды<i>B</i>, если либо<i>А</i>выиграла у<i>B</i>, либо существует такая команда<i>C</i>, что<i>А</i>выиграла у<i>C</i>, а<i>C</i>– у<i>B</i>.   а) Докажите, что есть команда, которая сильнее всех.   б) Докажите, что команда, выигравшая турнир, сильнее всех.

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

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

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

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

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

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

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

Докажите, что связный граф с 2<i>n</i> нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно  <i>n</i> –1  раз и не проводя никакое ребро дважды.

На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.

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

Докажите, что для плоского графа справедливо неравенство  2<i>E</i> ≥ 3<i>F</i>.

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

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

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

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

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

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

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

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

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

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

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