algorithm
полиномиально ограниченный алгоритм для минимальной вершины
Поиск…
Вступление
Это полиномиальный алгоритм для получения минимального вершинного покрытия связанного неориентированного графа. Сложность времени этого алгоритма O (n2)
параметры
| переменная | Имея в виду |
|---|---|
| г | Ввод подключенного ненаправленного графика |
| Икс | Набор вершин |
| С | Конечный набор вершин |
замечания
Первое, что вам нужно сделать в этом алгоритме, чтобы получить все вершины графа, отсортированные по убыванию в зависимости от степени.
После этого вы выполняете итерацию по ним и добавляете каждый из них в конечные вершины, которые не имеют соседних вершин в этом наборе.
В завершающей стадии итерации на конечном наборе вершин и удалим все вершины, которые имеют одну из своих смежных вершин в этом множестве.
Алгоритм Псевдокод
Алгоритм PMinVertexCover (граф G)
Ввод связанного графа G
Минимальный набор вершинной вершины C
Set C <- new Set<Vertex>()
Set X <- new Set<Vertex>()
X <- G.getAllVerticiesArrangedDescendinglyByDegree()
for v in X do
List<Vertex> adjacentVertices1 <- G.getAdjacent(v)
if !C contains any of adjacentVertices1 then
C.add(v)
for vertex in C do
List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)
if C contains any of adjacentVertices2 then
C.remove(vertex)
return C
C - минимальное вершинное накрытие графа G
мы можем использовать сортировку ведра для сортировки вершин в соответствии с его степенью, поскольку максимальное значение степеней (n-1), где n - количество вершин, тогда сложность времени сортировки будет равна O (n)
