Определение минимального покрытия графа

[ac!d]

Кто-нибудь может написать или кинуть на почту алгоритм сего задания? Просмотрел кучу учебников по ДМ, ничерта не нашёл, определение самого покрытия есть, а алгоритма нету.

[xxx-men]

что есть "минимальное покрытие"? определение в студию=)
может что нибуть и найду.....

[ac!d]

"Будем говорить, что ребро и вершина покрывают друг друга, если они инцедентны. Множество вершин, покрывающее все рёбра графа, называется вершинным покрытием графа, а множество рёбер, покрывающих все вершины, называется рёберным покрытием графа. Наименьшее число вершин в вершинных покрытиях графа называется его числом вершинного покрытия.(А0) Аналогично наименьшее число рёбер в рёберных покрытиях графа наывается числом рёберного покрытия.(А1) Вершинное(рёберное) покрытие называется наименьшим, если оно содержит А0(соответственно А1) элементов."
Из учебника Ф.Харари: "Теория графов"

[xxx-men]

тебе надо вершинное или реберное покрытие найти?
чем\как задан граф..?


граф ориентированный?
граф с петлями?

если нет, простейший случай:

Матрица инцидентности G имеет n строк и m столбцов, а ее элемент G(i,j) равен 1, если вершина с номером i инцидентна ребру с номером j , в противном случае он равен нулю.

попробую минимальное вершинное покрытие:
const int n=количество_вершин;
const int m=количество_ребер;
bool G[n][m+1]; // +дополнительная строчка

//функция, найти число связей у вершины
int find(int x,)
{
int result=0;
for(int i =0; i<m; i++)
___if(G[x][i]) result++;
};

//функция, найти вершину с максимальным числом связей
int find_max()
{
int result =0;
for(int i =0; i<n; i++)
___if( find(i)>find(result ) ) result = i;//оптимизаторы нервно курят....
};

//функция добавить вершину в "список минимального покрытия"
void add(int x)
{
G[x][m+1]=true;
for(int i=0;i<m;i++)
{
if(G[x][i])
___for(j=0;j<n;j++)
______G[j][i]=false;
};
};

//main
int main()
{
/*тут заполняеца этот массив*/
/*дополнительная строчка забиваеца нулями*/

while( find( find_max()) )
___add(find_max());

/*
дополнительная строчка должна являца минимальным вершинным покрытием
правда от графа остануца только нолики, но это решаемо
*/
};

все написаное выше полная отсебятина, ни где не тестировалась, и вполне может неработать

[ac!d]

Всё, спасибки, прога уже найдена. Если что, могу скинуть на почту, если интересуешься