Задача о минимальном остовном дереве: алгоритм Крускала
Вначале текущее множество рёбер устанавливается пустым.
Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству.
Когда таких рёбер больше нет, алгоритм завершён.
Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
Задача о кратчайшем пути в графе: алгоритм Флойда
На
каждом шаге алгоритм генерирует
двумерную матрицу W, 
.
Матрица W содержит
длины кратчайших путей между всеми
вершинами графа. Перед работой алгоритма
матрицаW заполняется
длинами рёбер графа.
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
Задача о кратчайшем пути в графе: алгоритм Дейкстры
Если все вершины посещены, алгоритм завершается.
В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку.
Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины.
Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом.
Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины.
Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Задача о максимальном потоке в сети: варианты постановки задачи
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока максимальна.
Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.
Произвольное число источников и/или стоков
Неориентированные рёбра
Ограничение пропускной способности вершин
Задача о максимальном потоке в сети: алгоритм решения
Алгоритм Форда:
Найти любой увеличивающий путь.
Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей.
Повторять, пока увеличивающий путь есть.
Задача о наибольшемпаросочетании
Наибольшее паросочетание — это такое паросочетание, которое содержит максимальное количество ребер.
Эйлеровы и гамельтоновы циклы и цепи.
Эйлерова цепь — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров цикл — это эйлерова цепь, являющийся циклом.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз.
Задача о раскраске графа: эвристические алгоритмыи алгоритм неявного перебора
Эвристический алгоритм (эвристика) — алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве практически значимых случаев.
Для начала выдели связные компоненты графы и раскрашивай каждый из них по отдельности. Число цветов, наверное разумнее будет находить двоичным поиском - в худшем случае он лишь ненамного замедлит программу, но зато свободы в придумывании эвристик будет гораздо больше. На каждом шаге двоичного поиска перед тобой будет стоять задача - можно ли раскрасить данный связный граф K цветами. Решай перебором - выбери нераскрашенную вершину, перебери цвет для нее, отличный от цветов смежных с ней уже-раскрашенных вершин, рекурсивно попытайся раскрасить оставшиеся вершины, если не получилось - откат, пробуй другой цвет. Выбирать вершину можно по разному, например можно взять ту, с которой связано наибольшее число нераскрашенных вершин. Или ту, для которой число цветов в которую ее можно раскрасить на данном шаге наименьшее. Если это число = 0 (т.е. ее соседи уже покрашены во все K цветов), можно прекратить перебор на этом шаге. Придумывай эвристики для своих конкретных графов чтобы сократить перебор, т.к. в общем случае задача NP-сложная и требует экспоненциального времени.