Эйлеровы графы. Онлайн-кружок журнала “Квантик“, занятие 15 (2013-2014 уч. год)

Теория графов появилась, когда Леонард Эйлер задумался над “Кёнигсбергской головоломкой“: можно ли пройти по всем мостам Кёнигберга ровно один раз и вернуться в исходную точку? Именно тогда и было введено понятие графа. Эйлер сформулировал важный теорему, устанавливающую, когда граф можно обойти, пройдя по каждому ребру ровно один раз. Применения этой теоремы обширны: от простых до совсем неожиданных, когда нужный граф построить весьма непросто. О некоторых из применений мы и поговорим.