​​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 вершин, какие-то соединены ребрами, но мы не знаем какие. Мы можем выбрать любую пару вершин и получить ответ на вопрос “есть ли ребро между ними?”. Какое наименьшее число вопросов надо задать, чтобы гарантированно выяснить является ли граф связным?

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