Начало теории графов было положено Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах в 1736 году. Бывший Кенигсберг (Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Жители предлагали приезжим пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

И решена она была, как вы уже догадались, немецким и русским математиком Леонардом Эйлером.
Эйлер нашёл правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был…. 
Для наглядности заменим рисунок расположения речных рукавов упрощенной схемой (см. рис.). В предложенной задаче размер острова и длина мостов никакого значения не имеет (такова, мы знаем, характерная особенность всех топологических задач: они не зависят от относительных размеров частей фигуры)

Поэтому мы можем местности заменить на схеме точками, в которых встречаются пути обхода. Задача сводится теперь, как видим, к тому, чтобы начертить последнюю фигуру  одним, росчерком, не отрывая пера от бумаги и не проводя ни одной линии дважды.
Покажем, что фигуру нашу начертить одним росчерком нельзя. В самом деле, в каждую из узловых точек  надо прийти по одному из путей и затем эту точку покинуть по другому пути, исключение составляет только начальная и конечная точки: в первую не надо ниоткуда приходить, вторую нет надобности покидать. Значит, для возможности непрерывного обхода нашей фигуры необходимо, чтобы во всех узловых точках, кроме двух, сходилось либо по 2, либо по 4 пути, — вообще четное число путей. В нашей же фигуре в каждой из точек сходится как раз нечетное число линий. Поэтому начертить ее одним росчерком нельзя; невозможно, следовательно, и обойти Кенигсбергские мосты требуемым образом.
Задача была с помощью графов.
Граф – это совокупность точек ( вершины), и линий (рёбра), соединяющих некоторые из вершин. Эти линии указывают на выявленные связи между элементами системы, которые изображены вершинами. 
Типичная информационная модель, выполненная в виде графа,- схема метрополитена.

Одна из целей, поставленных при строительстве метро- возможность соединить все станции между собой.
ДЗ 1 
Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.

Можно ли долететь на рейсовых ракетах с Земли до Марса?
ДЗ 2

Однажды встретились пятеро друзей. Каждый здороваясь, пожал каждому руку. Сколько рукопожатий было сделано.