"Будем говорить, что ребро и вершина покрывают друг друга, если они инцедентны. Множество вершин, покрывающее все рёбра графа, называется вершинным покрытием графа, а множество рёбер, покрывающих все вершины, называется рёберным покрытием графа. Наименьшее число вершин в вершинных покрытиях графа называется его числом вершинного покрытия.(А0) Аналогично наименьшее число рёбер в рёберных покрытиях графа наывается числом рёберного покрытия.(А1) Вершинное(рёберное) покрытие называется наименьшим, если оно содержит А0(соответственно А1) элементов."
Из учебника Ф.Харари: "Теория графов"
[Ответ]
тебе надо вершинное или реберное покрытие найти?
чем\как задан граф..?
граф ориентированный?
граф с петлями?
если нет, простейший случай:
Сообщение от :
Матрица инцидентности 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());
/*
дополнительная строчка должна являца минимальным
вершинным покрытием
правда от графа остануца только нолики, но это решаемо
*/
};
все написаное выше полная отсебятина, ни где не тестировалась, и вполне может неработать
[Ответ]
