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

#олмат
#графы
#8класс

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

#олмат
#8класс
#графы

140. В посёлке городского типа Жирниково работает троллейбусная сеть. Каждый маршрут проходит ровно через 3 остановки, причем любые 2 маршрута имеют не более одной общей остановки. Какое наибольшее число маршрутов может быть, если всего в посёлке 9 остановок?

#олмат
#графы

(Сейчас ещё раз повторим задачу 20, поскольку она черезвычайно важна)
154. Докажите, что среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

#олмат
#графы
#бессмертнаяклассика

(А вот и продолжение прошлой задачи)
155. В компании из 9 девушек некоторые поссорились. Оказалось, что нет такой тройки девушек, в которой каждая девушка поссорилась с каждой. Докажите, что найдутся 4 девушки, среди которых ни одна пара еще не ссорилась.

#олмат
#графы
#9класс

243. Дан произвольный граф. Надо расставить в его вершинах целые числа так, чтобы выполнялись два условия:
1) если две вершины соединены ребром, то числа в них имеют общий делитель;
2) если две вершины не соединены ребром, то числа в них взаимно просты.
Всегда ли можно так сделать?

#олмат
#графы

​​247. Между городами страны организованы двусторонние беспосадочные авиарейсы таким образом, что от каждого города до каждого другого можно добраться (возможно, с пересадками). Более того, для каждого города А, существует город B такой, что любой из остальных городов напрямую соединён либо с А, либо с B. Докажите, что от любого города добраться до любого другого не более, чем с двумя пересадками.

#олмат
#графы
#8класс

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

#олмат
#графы

303. У куба отмечены вершины и центры граней, а также проведены диагонали всех граней. Можно ли по отрезкам этих диагоналей обойти все отмеченные точки, побывав в каждой из них ровно по одному разу?

#олмат
#графы

​​305. У каждого марсианина по три руки и несколько антенн. Каждый марсианин взял за руки трех других (так, что все руки оказались заняты). Оказалось, что у любых двух марсиан, взявшихся за руки, количество антенн отличается ровно в 6 раз. Может ли суммарное количество антенн быть 2018?

#олмат
#графы
#тч

328. (Формула Эйлера). Пусть связный плоский граф с V вершинами и E ребрами разрезает плоскость на F связных кусков (граней). Тогда V−E+F=2.

#олмат
#графы

335. В стране 10 городов. Возможно ли проложить между городами дороги так, чтобы из каждого города выходило по 3 дороги и из каждого города в каждый можно было бы добраться по дорогам, заходя не более, чем в один промежуточный город?

#олмат
#графы

​​340. Двадцать городов соединены 172 авиалиниями. Доказать, что, используя эти авиалинии, можно из любого города перелететь в любой другой (быть может, делая пересадки).

#олмат
#графы

366. В волшебной стране Лариколяндия 100 городов, некоторые из которых соединены авиалиниями. Известно, что из каждого города выходит более 90 авиалиний. Докажите, что найдутся 12 городов, попарно соединенных авиалиниями.

#олмат
#графы

​​397. Схема городов и дорог в некотором государстве изображена на рисунке. Можно ли обойти все города, побывав в каждом из них по одному разу?

#олмат
#графы

​402. Есть проволока длиной 120 сантиметров. На какое наименьшее число частей нужно ее разрезать, чтобы из них можно было сложить каркас куба с ребром 10 сантиметров? (проволоку можно сгибать)

#олмат
#графы
#оценкаплюспример

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

#олмат
#графы

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

#олмат
#графы

​​495. У каждого из жителей некоего города есть три знакомых жителя, причём с одним из них он активно общается каждое утро, с другим — каждый полдень, с третьим — каждый вечер. Петя с Васей поссорились и прекратили общаться. Петя заразился вирусом. Докажите, что Вася тоже вскоре заразится.

#олмат
#графы

​​501. В графе 100 вершин, какие-то соединены ребрами, но мы не знаем какие. Мы можем выбрать любую пару вершин и получить ответ на вопрос “есть ли ребро между ними?”. Какое наименьшее число вопросов надо задать, чтобы гарантированно выяснить является ли граф связным?

#олмат
#графы