tag:
графы
§
Два графа называются изоморфными, если у них одинаковое число вершин (обозначим его n) и вершины каждого из них можно занумеровать так числами от 1 до n, что в первом графе две вершины соединены ребром тогда и только тогда, когда вершины с такими же номерами во втором графе соединены. (Проще говоря, если только двигать вершины и изгибать рёбра, то получится граф, изоморфный исходному.)615.
В шахматном турнире по круговой системе участвуют семь школьников. Известно, что Ваня сыграл шесть партий, Толя - пять, Лёша и Дима по три, Семён и Илья по две, Женя - одну. С кем сыграл Лёша?
623.
В городе Октопусе построили метро и в нём 8 станций. При этом из них выходит 4,3,3,3,2,2,2,1 линий метро соответственно (одна линия соединяет ровно две станции). Одну линию закрыли на ремонт. Могло ли оказаться, что теперь карта метро состоит из двух одинаковых независимых кусков?
635.
В стране Цифра есть 9 городов 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник заметил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий, делится на три. Можно ли добраться из города 1 в город 9?
667.
В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
741.
Между девятью планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?
758.
Гриша с папой пошёл в тир. Уговор был такой: Гриша делает 5 выстрелов и за каждое попадание в цель получает право сделать
еще 2 выстрела. Всего Гриша сделал 17 выстрелов. Сколько раз он попал в цель?
767.
В компании 4 гнома и 5 эльфов. У каждого эльфа ровно 5 друзей в этой компании.
Докажите, что найдётся гном, среди друзей которого имеется не менее двух эльфов.
770.
За рекой живёт 17 медведей, на дальних холмах – 14, а в зелёной долине – 20. В
один прекрасный день они все пришли ловить в реке лососей. Медведи очень дружелюбные и делились каждой пойманной рыбой с ещё одним медведем. В итоге оказалось, что у каждого медведя на 1 отличается количество тех, с кем он поделился, от тех, кто с ним поделился. Может ли это быть правдой?
775.
Можно ли расположить в пространстве 7 карандашей так, чтобы каждый касался ровно трех других?
776.
Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
871.
В полном графе часть рёбер покрасили в красный цвет, а остальные - в синий. Рассмотрим два графа: один состоящий из всех красных рёбер, а второй из синих. а) Докажите, что хотя бы один из этих графов связен. б) Докажите, что для каждой вершины можно выбрать такой цвет, что от неё до любой другой минимальное расстояние по этому цвету будет меньше 3.