Условие задачи
Докажите, что можно так установить одностороннее движение по улицам любого города, что число улиц, по которым можно въехать на любой перекресток, не более, чем на одну отличается от числа улиц, по которым можно уехать с него.
Задача из контрольной работы по дискретной математике технического университета. Не представляю как к ней подступиться. Подскажите пожалуйста идею решения задачи
У нас связный (наверное, ведь это же один город) граф. Пусть число вершин нечетной степени =к. Тогда этот граф можно покрыть к/2 цепями, реберно непересекающимися. Каждую такую цепь ориентируем в одну сторону (в какую именно - смотрим по условиям).
Это, конечно, не доказательство - только направление, куда думать.
Где можно почитать о графах? Уровень технического университета.
Сейчас полно книжек под названием "Дискретная математика". Например, Судоплатов, Овчинникова.
В интернете - не искала, не знаю.
Русская версия Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)