Cтруктура связанных между собой произвольным образом нескольких
объектов называется графом.
В программировании иногда вместо термина
"граф" используют термин
"сеть". Объекты, составляющие граф, называют
вершинами, а линии, связывающие объекты,
ребрами. Между двумя произвольными
вершинами графа соединение может отсутствовать. Чаще всего вершины графа
нумеруют или обозначают буквами.
Поводом для создания
теории графов стало решение одной занимательной задачи известным математиком
Леонардом Эйлером
во время посещения им в 1736 году Кёнигсберга (современного Калининграда).
Протекающая по городу Кёнигсбергу река делила
его на четыре части, и эти части были соединены
между собой семью мостами. На упрощенном плане
города мосты указаны цифрами, а части города − буквами.
Известная задача того времени была такой: как пройти по всем мостам, не
проходя ни по одному из них дважды?
Эйлер обозначил части города соответствующими точками A, B, C и D, а мосты
− с помощью линий, соединяющих эти точки (схема справа). Таким образом,
задача стала эквивалентной такому заданию: можно ли, не отрывая ручку от
бумаги, нарисовать данную фигуру, пройдя по каждой линии только один раз?
Эйлер доказал, что эта задача не имеет решения.
Обычно графы представляют двумя способами: списком смежности и матрицей смежности. В списке смежности перечислены вершины, соединенные
с каждой из данных вершин.