Experiment Title: simple diagramming, judgment of connected graph, Euler graph and Hamiltonian graph
Purpose of the experiment:
- Master the definition and judgment method that can be simplified;
- Master the judgment methods of connected graph and Euler graph;
- Master the search method of Euler loop;
- Understand the practical application of Euler chart.
Test requirements:
- Given a sequence of nonnegative integers (for example: (4,2,2,2,2)).
- Judge whether the sequence of nonnegative integers is diagrammable and simple.
- If it can be simplified, the corresponding simple graph is obtained according to the Havel theorem process, and the graph is output.
- Judge whether the simple graph is connected.
- If it is a connected graph, judge whether the graph is an Euler graph. If it is an Euler diagram, please output an Euler circuit (output form: V2 - > V1 - > V5 - > V3 - > V4 - > V5 - > V2).
Review of relevant knowledge
Simple diagrammable judgment
Mode 1:
Mode 2:
The above two theorems are both necessary and sufficient conditions.
Euler circuit
That is, a simple loop through all edges in the graph
thinking
- Whether we can simplify the graph, we use the two conditions that the sum of vertex degrees is even and the vertex degrees are between 0 and n - 1. The first condition is the decision condition of diagonalization. I use the second sufficient and necessary condition above to judge whether it can be simplified, and use Havel's theorem to obtain the adjacency matrix from the degree sequence. At first, I encountered a Bug when calculating the adjacency matrix. For the test case 4 4 2 2, I can't deduce the adjacency matrix from the bottom up. I think the reason is that the sequence number of vertices was disturbed by me in the process of Havel theorem. If you start from scratch every time to find vertices that can be connected, the middle will be stuck in 4 4 2 2 and cannot add edges, that is, an isolated vertex and two edges will be left out and cannot be added. So I changed from ab initio traversal to loop traversal, and the first adaptation algorithm in similar operating systems was changed to loop first adaptation algorithm.
- If an undirected graph is an Euler graph, the degree of each vertex is even;
- Whether it is connected, starting from one vertex, if it can traverse all vertices, it is connected;
- To find the Euler loop, start from a vertex and add a path that has not been passed each time. There can be no loop. If there is no way to go, all edges have passed and returned to the original starting point, it shows that this is a correct Euler loop.
Implementation code
/*
1,Given a sequence of nonnegative integers (for example: (4,2,2,2,2)).
2,Judge whether the sequence of nonnegative integers is diagrammable and simple.
The simple graph is represented by undirected adjacent matrix
3,If it can be simplified, the corresponding simple graph is obtained according to the Havel theorem process, and the graph is output.
4,Judge whether the simple graph is connected.
5,If it is a connected graph, judge whether the graph is an Euler graph. If it is the form of V3 - > V3 - > output, please refer to V1 - > V5 - > output.
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[11] = {0}; // Storage degree sequence
int n = 0; // Number of vertices
int graph[11][11]; // Adjacency matrix for storing simple graphs
int visited[11];
int used[11][11]; // Has it passed when seeking Euler circuit
stack<int> path; // Storage Euler loop
int m = 0; // Number of edges
int curEdge = 0;
bool cmp(int t1, int t2)
{
return t1 >= t2;
}
// Judge whether it is diagrammable and simple. If it is diagrammable, it returns 1, if it is simple, it returns 2, and if it is not diagrammable, it returns 0
int isGraphic()
{
int sum = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] < 0) // Negative non graphicization
{
return 0;
}
sum += a[i];
}
if (sum % 2 == 0) // Graphicization
{
if (n - 1 >= a[1] && 0 <= a[n]) // The second judgment that can be simply diagrammed
{
int left = 0;
int right = 0;
int flag = true;
for (int r = 1; r <= n - 1; ++r)
{
left += a[r];
right = r * (r - 1);
for (int j = r + 1; j <= n; ++j)
{
right += min(r, a[j]);
}
if (left > right)
{
flag = false;
break;
}
}
if (flag == true)
{
return 2;
}
else
{
return 1;
}
}
else // Can not be simplified, return 1
{
return 1;
}
}
else // Not diagrammable, return 0
{
return 0;
}
}
// Judging adjacency matrix with Havel theorem, top-down
void isGraphicHavel(int c[11], int len) // Pass in the degree sequence c[11], and the number of vertices len,
{
int b[11] = {0};
int j = 1;
for (int i = 2; i <= c[1] + 1; ++i)
{
b[j++] = c[i] - 1;
}
for (int i = c[1] + 2; i <= len; ++i)
{
b[j++] = c[i];
}
sort(b + 1, b + 1 + len - 1, cmp); // Descending sort
// cout << "c[i]: " << endl;
// for (int i = 1; i <= len; ++i)
// {
// cout << c[i] << " ";
// }
// cout << endl;
// cout << "b[i]: " << endl;
// for (int i = 1; i <= len - 1; ++i)
// {
// cout << b[i] << " ";
// }
// cout << endl;
int flag = true; // Judge whether to reach the lowest level, that is, all are isolated points
for (int i = 1; i <= len - 1; ++i)
{
if (b[i] != 0)
{
flag = false;
break;
}
}
if (!flag) // Continue to seek the next layer
{
isGraphicHavel(b, len - 1);
}
int temp[11];
copy(c, c + 11, temp); // Temporary array of c to prevent affecting the upper layer
// Add new vertices and edges of this layer c[11] to the adjacent matrix of the underlying degree sequence b[11]
// This code doesn't work properly when testing the sample of 4 4 4 2 2 2 2, because it can't go up to 4 4 4 2 2 2 in 4 4 2 2
// Finally, an isolated point will be left out, and no edges can be added, because there can be no parallel edges
// It may be better to change the first adaptation algorithm to cyclic first
int start = 1;
for (int i = 1; i <= len; ++i)
{
while(temp[i] > b[i]) // New edges need to be added and two values need to be changed
{
int num = 0;
for (int j = start; num < len && temp[i] > b[i]; j = (j == len) ? 1 : j + 1)
{
num++;
if (i != j && graph[i][j] != 1){ // And rings cannot have parallel edges
if (temp[j] > b[j]) // The vertex also needs a new edge
{
graph[i][j] = 1;
graph[j][i] = 1;
temp[i]--;
temp[j]--;
start = (j == len) ? 1 : j + 1; // The pointer points to the next point instead of the first point
}
}
}
}
}
// Cout < < adjacency matrix: "< endl;
// for (int i = 1; i <= n; ++i)
// {
// for (int j = 1; j <= n; ++j)
// {
// cout << graph[i][j] << " ";
// }
// cout << endl;
// }
}
// Judge whether it is an Euler chart, return 1, not 0
int isEuler()
{
// If it is an Euler graph, all vertex degrees are even
for (int i = 1; i <= n; ++i)
{
if (a[i] % 2 != 0)
{
return 0;
}
}
return 1;
}
// dfs traverses all the points in the binary array
void dfs(int t)
{
for (int i = 1; i <= n; ++i)
{
if (visited[i] == 0 && graph[t][i] == 1) // i has not been visited, and there is an edge between vertices t and i
{
visited[i] = 1;
dfs(i);
}
}
}
// Judge whether it is a connected graph according to the adjacency matrix
bool isConnected()
{
// Exclude those with outliers first
if (n == 1)
{
return false;
}
for (int i = 1; i <= n; ++i)
{
if (a[i] == 0)
{
return false;
}
}
// Search from v1
visited[1] = 1;
dfs(1);
for (int i = 1; i <= n; ++i)
{
if (visited[i] == 0) // There are vertices that have not been accessed
{
return false;
}
}
return true;
}
bool EulerCircuit(int v) // The return value represents whether it can go through
{
// First calculate the number of edges and use the stack to store the vertices that have passed. If you don't finish walking, there is no way to go, or you can't get back to the starting point, the vertices at the top of the stack will pop up
// For each vertex, use the adjacency matrix to try each adjacent vertex at one time
int flag = false; // Sign of whether it can go through
for (int i = 1; i <= n && !flag; ++i)
{
if (graph[v][i] == 1 && used[v][i] == 0) // An unparalleled Road
{
used[v][i] = 1; // The mark has passed
used[i][v] = 1;
path.push(i);
curEdge++;
flag = true;
if (!EulerCircuit(i)) // Can't go on
{
flag = false;
used[v][i] = 0; // The mark has passed
used[i][v] = 0;
path.pop();
curEdge--;
}
}
}
if (!flag) // There is no way to go
{
if (v == 1 && curEdge == m) // Back to the starting point and walked all over the side
{
return true;
}
else // I left wrong last time
{
return false;
}
}
else
{
return true;
}
}
int main()
{
while (true)
{
memset(graph, 0, sizeof(graph));
memset(a, 0, sizeof(a));
memset(visited, 0, sizeof(visited));
memset(used, 0, sizeof(used));
m = 0;
curEdge = 0;
cout << "Please enter the number of vertices:" << endl;
cin >> n; // Enter the number of vertices
cout << "Please enter the degree sequence in descending order, with spaces as intervals:" << endl;
for (int i = 1; i <= n; ++i) // Enter the degree sequence in descending order. There is no data in the first position
{
cin >> a[i];
}
int t1 = isGraphic();
if (t1 == 0)
{
cout << "Non graphicization" << endl;
}
else if (t1 == 1)
{
cout << "Graphicization" << endl;
}
else
{
cout << "Simple diagrammable" << endl;
isGraphicHavel(a, n); // Finding the adjacency matrix of a simple graph according to Havel's theorem
cout << "Adjacency matrix:" << endl;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
cout << graph[i][j] << " ";
}
cout << endl;
}
// Judge whether it is connected
if (isConnected())
{
cout << "Connected graph" << endl;
if(isEuler())
{
cout << "Eulatu" << endl;
// Using the handshake theorem to find the number of edges
for (int i = 1; i <= n; ++i)
{
m += a[i];
}
m = m / 2;
path.push(1); // Start with v1
EulerCircuit(1);
cout << path.top();
path.pop();
while(!path.empty())
{
cout << "->" << path.top();
path.pop();
}
cout << endl;
}
else
{
cout << "nonEuler graph " << endl;
}
}
else
{
cout << "Unconnected graph" << endl;
}
}
}
return 0;
}