Глава 2 Элементы теории графов

В 1736 г. Л.Эйлер опубликовал статью, посвященную решению задачи о Кенигсбергских мостах. С этого времени идет отсчет теории графов как математической дисциплины. Первые исследования в теории графов бы­ли связаны с попытками решения т.н. задачи о четырех красках (впервые сформулированной в Великобритании А.Де Морганом и А.Кэли во второй половине XIX века), а также с задачами о перевозках и о электрических схемах (Г.Кирхгоф). В настоящее время теория графов является самосто­ятельной математической дисциплиной, имеющей приложения как в самой математике, так и в экономике, физике, биологии. Это связано с универ­сальностью языка теории графов и эффективностью ее методов в решении различных задач.