Гамильтонов цикл

Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.

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);

}