![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.
int c[n]; // номер хода, на котором посещается вершина
int path[n]; // номера посещаемых вершин
int v0=2; // начальная вершина
//Матрица смежности
int a[n][n]=
{
//тут должна быть инициализация матрицы смежности
};
void prnt(void)
{
int p;
for (p = 0; p<n; p++)
printf("%d ", path[p]);
printf("%d ", path[0]);
printf("\n");
}
//подпрограмма нахождения гамильтонова цикла
int gamilton (int k)
{
int v,q1=0;
for(v=0; v<n &&!q1; v++)
{
if(a[v][path[k-1]]||a[path[k-1]][v])
{
if (k==n && v==v0) q1=1;
else if (c[v]==-1)
{
c[v] = k; path[k]=v;
q1=gamilton (k+1);
if (!q1) c[v]=-1;
} else continue;
}
} return q1;
}
main()
{
int j;
clrscr();
printf("Гамильтонов цикл:\n");
for(j=0;j<n;j++) c[j]=-1;
path[0]=v0;
c[v0]=v0;
if(gamilton (1)) prnt(); else printf("Нет решений\n");
}
Задача о домино
Приведём здесь классическую задачу на эйлеров цикл - задачу о домино.
Имеется N доминошек, как известно, на двух концах доминошки записано по одному числу (обычно от 1 до 6, но в нашем случае не важно). Требуется выложить все доминошки в ряд так, чтобы у любых двух соседних доминошек числа, записанные на их общей стороне, совпадали. Доминошки разрешается переворачивать.
Переформулируем задачу. Пусть числа, записанные на донимошках, - вершины графа, а доминошки - рёбра этого графа (каждая доминошка с числами (a,b) - это ребра (a,b) и (b,a)). Тогда наша задача сводится к задаче нахожденияэйлерова пути в этом графе.
int main() {
int n;
vector < vector<int> > g (n, vector<int> (n));
... чтение графа в матрицу смежности...
vector<int> deg (n);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
deg[i] += g[i][j];
int first = 0;
while (!deg[first]) ++first;
int v1 = -1, v2 = -1;
bool bad = false;
for (int i=0; i<n; ++i)
if (deg[i] & 1)
if (v1 == -1)
v1 = i;
else if (v2 == -1)
v2 = i;
else
bad = true;
if (v1!= -1)
++g[v1][v2], ++g[v2][v1];
stack<int> st;
st.push (first);
vector<int> res;
while (!st.empty())
{
int v = st.top();
int i;
for (i=0; i<n; ++i)
if (g[v][i])
break;
if (i == n)
{
res.push_back (v);
st.pop();
}
else
{
--g[v][i];
--g[i][v];
st.push (i);
}
}
if (v1!= -1)
for (size_t i=0; i+1<res.size(); ++i)
if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1)
{
vector<int> res2;
for (size_t j=i+1; j<res.size(); ++j)
res2.push_back (res[j]);
for (size_t j=1; j<=i; ++j)
res2.push_back (res[j]);
res = res2;
break;
}
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (g[i][j])
bad = true;
if (bad)
puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)
printf ("%d ", res[i]+1);
}
Дата публикования: 2015-09-18; Прочитано: 789 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!