Сведения о графах

Сведения о графах. В теории графов существуют специфические методы решения экстре¬мальных задач. Один из них основан на теореме о мак¬симальном потоке и минимальном разрезе, утверждаю¬щей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минималь¬ной пропускной способности разрезов, разделяющих вершины U и V. Были построены различные эффективные алгоритмы нахождения макси¬мального потока. Большое значение в теории графов имеют алгоритмические вопросы.

Для конечных графов, т. е. для графов с конеч¬ным множеством вершин и ребер, как правило, пробле¬ма существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение мно¬гих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допусти¬мых вариантов.

Однако таким способом удается ре¬шить задачу только для графов с небольшим числом вершин и ребер.

Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, на¬ходящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока. Результаты и методы теории графов применяются при реше¬нии транспортных задач о перевозках, для нахож¬дения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управ¬лении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в пост¬роении различных дискретных устройств, в програм¬мировании и т. д. Граф G (рис.1) задается множеством точек (вершин) х1, х2 хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2 аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек.

Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом, (рис.2).