Найти в графе максимальное паросочетание.

⇐ ПредыдущаяСтр 3 из 3

Пусть дан связный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо найти такое подмножество ребер , что для любой пары ребер из этого подмножества не существует общей вершины, т.е. найти такое, что
. Задача состоит в поиске подмножества максимальной мощности.

Найти в графе минимальное реберное покрытие.

Пусть дан связный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо найти такое подмножество ребер , чтобы для любой вершины графа нашлось ребро из этого подмножества, которому вершина бы принадлежала, т.е. такое , что . Задача состоит в поиске подмножества с минимальной мощностью.

Найти в графе простой путь максимальной длины.

Пусть дан связный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо такое подмножество ребер, чтобы они составляли простой путь (путь без циклов). Задача состоит в поиске подмножества максимальной мощности.

Найти в полном взвешенном графе гамильтонов цикл минимальной длины.

Пусть дан полный взвешенный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо найти Гамильтонов цикл (цикл, проходящий каждую вершину графа один и только один раз), имеющий минимальный суммарный вес.

Найти в графе двудольный подграф с максимальным числом вершин.

Пусть дан связный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо найти двудольный подграф этого графа, содержащий наибольшее число вершин исходного графа.

Найти в графе двудольный подграф с максимальным числом ребер.

Пусть дан связный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо найти двудольный подграф этого графа, содержащий наибольшее число ребер исходного графа.

Найти во взвешенном графе остов минимального веса.

Пусть дан связный взвешенный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо найти такой остов (остовное дерево), чтобы суммарный вес входящих в него ребер был минимальным.

Найти во взвешенном графе остов максимального веса.

12. Найти равномерное разбиение графа на 2 подграфа с минимальным сечением.

Пусть дан связный граф G=(V, E), где V – множество вершин, Е – множество ребер. Необходимо разбить множество вершин на два подмножества с равным числом вершин так, чтобы суммарный вес ребер, соединяющий эти два подмножества был минимальным.

ПРИЛОЖЕНИЕ 6. Данные частных задач

Данные частных задач заданы при помощи матрицы смежности или матрицы весовых коэффициентов (в случае задачи коммивояжера и поиска островного дерева).

Если ребро из вершины с номером i в вершину с номером j существует, то на пресечении строки с номером i со столбцом с номером j стоит 1, иначе 0.

Найти в графе вершинное покрытие минимальной мощности.

Найти в графе независимое множество максимальной мощности.

Найти в графе доминирующее множество минимальной мощности.

Найти в графе максимальное паросочетание.