​​Графы — интуитивно понятная штука в олимпиадной математике, ведь по сути это просто точки, соединенные линиями. Если кто-то с кем то играет, дружит, пожимает руки, отправляет письма, обходит картинку одним росчерком или ездит по дорогам в разные города — это все задачи на графы. Обход графа — идея, которая понятна даже второклассникам. И лучшей иллюстрацией этой идее служит задача про мосты о семи кёнигсбергских мостах. В этой задаче ученый Леонард Эйлер пытался обойти все семь мостов нынешнего Калининграда за один раз, не проходя ни по какому мосту дважды. Эйлер сам пытался обойти эти мосты и каждый раз у него ничего не выходило. И он сформулировал идеи, которые позже легли в основу теории графов. Оказывается, что если некая точка находится не в начале и не в конце маршрута нашей прогулки, то в этой точке сходится четное количество мостов. Ведь если мы пришли в эту точку по одному мосту, то можем из нее выйти через другой мост. Если начало прогулки и ее конец совпадают, то в этой точке тоже четное число мостов, потому что мосты разбиваются на пары. В каком случае будет нечетное количество мостов? Не в середине пути и в случае, когда начало и конец маршрута не совпадают. Получается, что мы можем пройти по всем мостам по одному разу только в случае, когда все вершины четные либо есть две нечетные вершины, то есть когда одна является началом, а вторая концом. Так мы с детьми 2-3 класса учим графы и выясняем, с какой точки начинать обход картинки, не отрывая руки от бумаги, и в какую точку заканчивать. Еще графы мы используем при решении задач, в которых просят определить, есть ли дорога из пункта А в пункт В, если есть определенный список дорог. В таких задачах мы часто находим, что все дороги распадаются на 2 несвязных между собой конструкции. Простая идея графов работает для решения задачек уровня 2-3 класса в олимпиадной математике. А более сложные графы вам обязательно встретятся в школьной информатике и взрослом программировании.