Граф
Граф — структура дискретной математики, описывающая связи объектов. Неофициальное название — сеть, вернее, сеть это что-то конкретное, вроде транспортной или нейронной сети, например, — кое подлежит мощному моделированию, использующему математическую теорию о гра́фах, теорию графов.
Мощность графов обеспечена тем, что матрицей из бит целиком выражается направленный граф.
Матрица — рабочая лошадка математических вычислений. Бит… дык он и есть бит, не иначе.
Описание[править]
Изначально понятие о графах появилось в месте под названием Валахия, но мало кто это понял.
Полноценная теория графов возникла в XVIII веке. В 1736 году прославленный в Вечности Леонард Эйлер решил задачу о семи мостах Кёнигсберга, Князева Града-того, коий в Восточной Пруссии. Сей град стоял на реке Преголя с двумя островами, соединёнными семью мостами. Задача заключалась в нахождении маршрута, проходящего через каждый мост ровно один раз и возвращающегося в исходную точку. Сделать это было тяжко, и призадумался он.
Эйлер свёл задачу к графу, где участки суши суть вершины, а мосты есмь рёбра. Он доказал невозможность такого маршрута математически. Так стало понятно, что графы это не просто так, это весьма сильная концепция, которая имеет перспективы применения.
По мотивам исследований пожилого были найдены многие закономерности. Скажем, граф имеет эйлеров цикл (замкнутый путь, проходящий каждое ребро ровно один раз), если все вершины имеют чётную степень. Эйлеров путь существует, если ровно две вершины имеют нечётную степень.
Гамильтонов цикл проходит через каждую вершину ровно один раз и возвращается в начало. Проблема существования гамильтонова цикла NP-полна, то бишь совершенно невозможно восрать скоростной алгоритм, который решит этот вопрос твёрдо и чётко.
Предельно благороден и граф Монте-Кристо.
