ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 157
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Теория графов, занятие 3
-
В парке «Лотос» невозможно найти такой маршрут для прогулок по его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку парка содержит не более одного раза. Докажите, что некоторые дорожки парка приводят в тупик. -
Администрация парка «Лотос» решила провести реконструкцию освещения парка. По новому проекту каждый перекресток и тупик будет освещаться четырьмя светильниками, а аллея, соединяющая два перекрестка или перекресток и тупик – шестью. Сколько светильников будет установлено, если в парке 18 перекрестков и тупиков? -
Государство Филиппины расположено на островах. Между некоторыми из островов ежедневно курсируют теплоходы (один рейс в одном направлении, другой – в противоположном). С любого острова можно добраться на любой другой, возможно, с пересадками. Полиция Филиппин пригласила Крутого Уокера для помощи в поимке опасного преступника. Преступник суеверен и не плывет на теплоходе 13 числа каждого месяца и каждый понедельник. Уокер не суеверен. Кроме того, он с помощью агентуры всегда знает, на каком острове находится преступник. Докажите, что если Уокер и преступник будут пользоваться только теплоходами, то они в конце концов окажутся на одном острове. -
В некотором поселке 1000 жителей. Ежедневно каждый из них делится узнанными вчера новостями со всеми своими знакомыми. Известно, что любая новость становится известной всем жителям. Доказать, что можно выбрать 90 жителей так, что если одновременно сообщить им какую-либо новость, через 10 дней она станет известной всем жителям поселка. -
Есть две страны: Обычная и Зазеркалье. У каждого города в Обычной стране есть двойник в Зазеркалье, и наоборот. Если в Обычной стране некоторые два города соединены авиалинией, то в Зазеркалье они не соединены, а если в Обычной стране некоторые два города не соединены авиалинией, то в Зазеркалье они соединены. В Обычной стране Алиса не может добраться из города А в город В, сделав менее двух пересадок. Докажите, что Алиса сможет в Зазеркалье перелететь из любого города в любой другой, сделав не более двух пересадок. -
Некоторые из 40 городов страны попарно соединены авиалиниями, принадлежащими одной из десяти авиакомпаний. Из каждого города можно перелететь в любой другой без пересадок, и каждая авиалиния действует в обоих направлениях. Докажите, что существует компания, которая может обеспечить путешествие с началом и концом в одном и том же городе, с числом перелетов не менее трех, причем каждый промежуточный город в пути будет посещаться ровно один раз. -
В городе с любой станции метро можно проехать на любую другую. Докажите, что одну из станций можно закрыть на ремонт без права проезда через нее так, чтобы с любой оставшейся станции можно было проехать на любую другую. -
В одном приморском курортном городе улицы настолько узкие, что в городе установлено одностороннее движение. Тем не менее, из каждой точки города можно проехать в любую другую. Докажите, что можно предложить такой маршрут патрулирования для полицейской машины, который начинается и оканчивается в одном и том же месте и проходит через каждый участок улиц между двумя перекрестками по крайней мере один раз. -
В приморском курортном городе после установления одностороннего движения оказалось, что число улиц, по которым можно въехать на каждый перекресток, равно числу улиц, по которым можно с него выехать. Докажите, что можно предложить такой маршрут патрулирования, который начинается и заканчивается в одном месте и проходит через каждый участок улиц ровно один раз. -
Докажите, что можно так установить одностороннее движение по улицам любого города, что число улиц, по которым можно въехать на любой перекресток, не более чем на одну отличается от числа улиц, по которым можно уехать с него. -
В городе двухстороннее движение. В течение двух лет в городе проходил ремонт всех дорог. Вследствие этого в первый год на некоторых дорогах было введено одностороннее движение. На следующий год на этих дорогах было восстановлено двустороннее движение, а на остальных дорогах введено одностороннее движение. Известно, что в любой момент ремонта можно было проехать из любой точки города в любую. Докажите, что в городе можно ввести одностороннее движение так, что из любой точки города можно будет проехать в любую. -
Насыщенным углеводородом называется соединение углерода С, имеющего валентность 4, и водорода Н, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода. Нарисуйте молекулы насыщенных углеводородов для n=3,4,5,6.