Experimental topic: solution of spanning tree, loop space and fault set space
Purpose of the experiment:
1. Master the solution method of undirected connected graph spanning tree;
2. Master the solution method of basic loop system and loop space;
3. Master the solution method of basic cut set system and fault set space;
4. Understand the practical application of spanning tree, loop space and fault set space.
Test requirements:
1. The adjacent matrix of an undirected simple connected graph is given (for example:).
2. Output the incidence matrix M of this figure.
3. Find the number of spanning trees in this graph.
4. Output the adjacent matrix (default row i corresponds to vertex vi) and incidence matrix (default row i corresponds to vertex vi and column j corresponds to edge ej) of any spanning tree.
5. Find the basic loop system corresponding to this spanning tree (output form, such as: {e1e4e3,e2e5e3}).
6. Find the basic cut set system corresponding to this spanning tree (output form: e.g. {e1,e4},{e2,e5},{e3,e4,e5}).
*Bonus question:
7. Find the loop space corresponding to this spanning tree (output form, such as: {, e1e4e3,e2e5e3,e1e4e5e2}).
8. Find the broken set space corresponding to this spanning tree (output form, such as: {, {e1,e4},{e2,e5},{e3,e4,e5},{e1,e2,e4,e5},{e1,e3,e5},{e2,e3,e4},{e1,e2,e3}).
Relevant ideas
- Find the number of spanning trees: here, the determinant of order n - 1 is obtained with the help of incidence matrix M, and then according to whether the determinant is full rank, if it is full rank, the corresponding edges form the spanning tree;
- Basic loop system: for a specific spanning tree, each chord corresponds to a basic loop, take a chord and add it to the branch set, and then find the corresponding loop set in this set;
- Basic cut set system: for a specific spanning tree, each branch corresponds to a basic cut set. Take a branch and add it to the string set. The graph after removing all edges in the set must be disconnected. However, the cut set needs to meet the minimum, so it is also necessary to remove redundant strings according to whether the graph is connected after adding strings. If the graph is still disconnected after adding strings, It shows that this string is redundant;
- Loop space: the loops in the loop system are obtained by looping each other, including empty sets. It is easier to deal with the situation of pairwise looping and three loops. If the number of loops is more than 3, first select the loop sequence to be looped, and then add the looping result to the space;
- Broken set space: the cut sets in the cut set system are obtained by looping each other, including empty sets. The processing method is the same as above;
Analog code
// 1. The adjacent matrix of an undirected simple connected graph is given (for example:).
// 2. Output the incidence matrix M of this figure.
// 3. Find the number of spanning trees in this graph.
// 4. Output the adjacent matrix (default row i corresponds to vertex vi) and incidence matrix (default row i corresponds to vertex vi and column j corresponds to edge ej) of any spanning tree.
// 5. Find the basic loop system corresponding to this spanning tree (output form, such as: {e1e4e3,e2e5e3}).
// The basic loop must contain the added string
// Therefore, starting from one vertex of the string, passing through the edge of the spanning tree, if you can return to another vertex
// This path is the basic loop
// Because the output requires an edge to represent the loop, one edge is stored here at a time. If you can finally return to the starting edge, add this loop to the basic loop system
// If not, go back. Here, each string can only correspond to one circuit, so once found, go back.
// Assumption of DfS function:
// Parameters:
// Side path stack, recording each side
// Compressed incidence matrix (because the serial number of the output edge is the serial number in the initial incidence matrix, the compressed incidence matrix here is also the serial number of the initial matrix)
// Initial start point (i.e. end point)
// Current starting point
// An array of whether an edge passes through
// Store the array of basic loop system, and store the path after finding the loop
// Branch collection
// Return value: bool type. If found, it returns TRUE
// Each time you traverse the branch set, look for the edge that has not passed. If it is not found, it indicates that you went wrong last time and go back
// If found, judge whether the loop has been formed. If not, continue recursion. If found, return
// 6. Find the basic cut set system corresponding to this spanning tree (output form: e.g. {e1,e4},{e2,e5},{e3,e4,e5}).
// *Bonus question:
// 7. Find the loop space corresponding to this spanning tree (output form, such as: {, e1e4e3,e2e5e3,e1e4e5e2}).
// 8. Find the broken set space corresponding to this spanning tree (output form, such as: {, {e1,e4},{e2,e5},{e3,e4,e5},{e1,e2,e4,e5},{e1,e3,e5},{e2,e3,e4},{e1,e2,e3}).
// For loop space and broken set space, the key is to realize the ring operation. Here, the order of edges in the loop is no longer considered, and each loop can be regarded as a set
#include <bits/stdc++.h>
using namespace std;
int n = 0; // Number of vertices
int m = 0; // Number of sides
// The passed in parameters are the order of the determinant and the determinant array, and the return value is the rank of the matrix
int rankOfDeterminant(int n, vector<vector<int> > matrix)
{
// Find the rank of binary matrix, that is, elimination. Finally, look at how many 1's are on the diagonal
int row = 0;
for(int col=0; col < n && row < n; col++, row++) // Starting from each column, eliminate each column to only 1 1 or all 0
{
int i = 0;
for(i = row; i < n; ++i) // Find the first non-zero row in this column
{
if(matrix[i][col] != 0)
break;
}
if(n == i)
--row;
else
{
swap(matrix[row], matrix[i]);
for(int k = i+1; k < n; k++)
{
if(0 != matrix[k][col])
{
for(int j = col; j < n; j++)
{
matrix[k][j] ^= matrix[row][j];// Use the 1 in row r to eliminate the 1 in all other rows on this column
}
}
}
}
}
return row;
}
// The parameters passed in are the starting value j of the sequence to be selected, the number of sequences to be selected, all sequence arrays, the current sequence array, and the number of selectable m
// All sequence problems similar to m choosing n
void selectSequence(int j, int num, vector<vector<int> >& sequences, vector<int> sequence, int tm)
{
if (num == 0) // Choose a sequence
{
sequences.push_back(sequence);
return;
}
else if (j + num > tm) // You can no longer select an n - 1 sequence
{
return;
}
else
{
// Select j
sequence.push_back(j); // Here j is the serial number of the edge
selectSequence(j + 1, num - 1, sequences, sequence, tm);
// Uncheck j
sequence.pop_back();
selectSequence(j + 1, num, sequences, sequence, tm);
}
}
// The incidence matrix is obtained according to the adjacent matrix
void getIncidenceMatrix(vector<vector<int> > &A, vector<vector<int> > &M)
{
// First calculate the number of edges, and then number the edges. Because it is a simple graph, there is only one edge between each two vertices. Just traverse the lower triangle
// The of determinant is generated by selecting n - 1 column from m column
int t = 0;
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (A[i][j] == 1)
{
M[i][t] = 1;
M[j][t] = 1;
t++;
}
}
}
}
void printMatrix(vector<vector<int> > &M)
{
for (int i = 0; i < int(M.size()); ++i)
{
printf("%d", M[i][0]);
for (int j = 1; j < int(M[0].size()); ++j)
{
printf(" %d", M[i][j]);
}
printf("\n");
}
}
int numOfSpanningTree(vector<vector<int> > & M, vector<vector<int> > &sequences, unordered_set<int>& store)
{
// Remove the first row of the incidence matrix and check all n - 1 order sub matrices in turn. The spanning tree is the one whose determinant is non - zero
int ret = 0;
for (int t = 0; t < int(sequences.size()); ++t)
{
vector<vector<int> > a(n - 1, vector<int>(n - 1, 0));
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < n - 1; ++j)
{
a[i - 1][j] = M[i][sequences[t][j]];
}
}
if (rankOfDeterminant(n - 1, a) == n - 1)
{
ret++;
store.insert(t); // Record the index number of the n - 1 order determinant of the corresponding spanning tree
}
}
return ret;
}
void branchSet(vector<int>& sequence, unordered_set<int>& branches)
{
// Find the set of branches
for (int i = 0; i < int(sequence.size()); ++i)
{
branches.insert(sequence[i]);
}
}
void stringSet(unordered_set<int> &strings, unordered_set<int>& branches)
{
// Find the set of strings
for (int i = 0; i < m; ++i)
{
if (branches.count(i) == 0)
{
strings.insert(i);
}
}
}
void basicCutSet(vector<unordered_set<int> >& cutSystem, unordered_set<int>& branches, unordered_set<int>& strings)
{
// Basic cut set system
for (auto it = branches.begin(); it != branches.end(); ++it)
{
unordered_set<int> temp(strings);
temp.insert(*it);
cutSystem.push_back(temp);
}
}
void endpointsOfEdge(unordered_map<int, vector<int> > &endpoints, vector<vector<int> >& M)
{
// Edge and vertex binding
for (int j = 0; j < m; ++j)
{
for (int i = 0; i < n; ++i)
{
if (M[i][j] == 1)
{
endpoints[j].push_back(i);
}
}
}
}
bool dfs(int initS, int newS, vector<int> &usedEdge, stack<int> &edgePath,unordered_map<int, vector<int> > &endpoints, vector<unordered_set<int> >& loopSystem, unordered_set<int>& branches)
{
if (newS == initS) // When the current starting point is the initial starting point, it indicates that a circuit has been walked out
{
unordered_set<int> temp;
while (!edgePath.empty())
{
int t = edgePath.top();
edgePath.pop();
temp.insert(t);
}
loopSystem.push_back(temp);
return true;
}
bool flag = false; // Can it go through
for (auto it = branches.begin(); it != branches.end(); ++it)
{
if (usedEdge[*it] == 0) // Unused edges
{
int tnewS = newS;
if (endpoints[*it][0] == newS) // Can go through
{
tnewS = endpoints[*it][1]; // Update current starting point
}
else if (endpoints[*it][1] == newS)
{
tnewS = endpoints[*it][0];
}
else
{
continue;
}
usedEdge[*it] = 1;
edgePath.push(*it);
flag = true;
if (dfs(initS, tnewS, usedEdge, edgePath, endpoints, loopSystem,branches)) // Return found
{
return true;
}
else
{
flag = false;
usedEdge[*it] = 0;
edgePath.pop();
}
}
}
return flag;
}
void basicCircuitSet(vector<unordered_set<int> >& loopSystem, unordered_set<int>& branches, unordered_set<int>& strings, unordered_map<int, vector<int> > &endpoints)
{
for (auto it = strings.begin(); it != strings.end(); ++it)
{
int initS = endpoints[*it][0];
int newS = endpoints[*it][1];
vector<int> usedEdge(m, 0);
usedEdge[*it] = 1;
stack<int> edgePath;
edgePath.push(*it);
if (dfs(initS, newS, usedEdge, edgePath, endpoints, loopSystem, branches))
{
}
else
{
cout << "dfs It's impossible not to find it. What's wrong?" << endl;
}
}
}
// The parameters passed in are the edge set array, the output setting options, and the basic broken set system with choice of 0
// The output of 1 is the basic loop system, the output of 2 is the loop space, and the output of 3 is the fault set space
void printEdgeSet(vector<unordered_set<int> > &edgeSet, int choice)
{
if (edgeSet.size() == 0)
{
if (choice == 0 || choice == 1)
{
printf("null set\n");
}
else
{
printf("{null set}\n");
}
}
else if (choice == 0 || choice == 3) // Basic fault set system or fault set space
{
printf("{");
if (choice == 3) // The broken set space also outputs an empty set
{
printf("null set,");
}
for (int i = 0; i < int(edgeSet.size()); ++i)
{
printf("{");
auto it = edgeSet[i].begin();
printf("e%d",*it + 1);
++it;
while(it != edgeSet[i].end())
{
printf(",e%d", *it + 1);
++it;
}
printf("}");
if (i != int(edgeSet.size()) - 1)
{
printf(",");
}
}
printf("}\n");
}
else // Basic loop system or loop space
{
printf("{");
if (choice == 2) // Loop space also outputs an empty set
{
printf("null set,");
}
for (int i = 0; i < int(edgeSet.size()); ++i)
{
auto it = edgeSet[i].begin();
printf("e%d",*it + 1);
++it;
while(it != edgeSet[i].end())
{
printf("e%d", *it + 1);
++it;
}
if (i != int(edgeSet.size()) - 1)
{
printf(",");
}
}
printf("}\n");
}
}
void cyclization(unordered_set<int>& a, unordered_set<int> &b, unordered_set<int>& temp)
{
for (auto it = a.begin(); it != a.end(); ++it)
{
if (b.count(*it) == 0)
{
temp.insert(*it);
}
}
for (auto it = b.begin(); it != b.end(); ++it)
{
if (a.count(*it) == 0)
{
temp.insert(*it);
}
}
}
// dfs traverses all the points in the binary array
void dfs(int t, vector<vector<int>> &tP, vector<int>& visited)
{
for (int i = 0; i < n; ++i)
{
if (visited[i] == 0 && tP[t][i] == 1) // i has not been visited, and there is an edge between vertices t and i
{
visited[i] = 1;
dfs(i, tP, visited);
}
}
}
// Judge whether it is a connected graph according to the adjacency matrix
bool isConnected(vector<vector<int>> &tP, vector<int>& visited)
{
// Exclude those with outliers first
if (n == 1)
{
return false;
}
// Search from v1
visited[0] = 1;
dfs(0, tP, visited);
for (int i = 0; i < n; ++i)
{
if (visited[i] == 0) // There are vertices that have not been accessed
{
return false;
}
}
return true;
}
int main()
{
// Input adjacency matrix
cout << "Enter the number of vertices:" << endl;
cin >> n;
vector<vector<int> > A(n, vector<int>(n, 0)); // Adjacent matrix
cout << "Enter adjacent matrix:" << endl;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin >> A[i][j];
if (A[i][j] != 0)
{
m++;
}
}
}
m /= 2; // Here we use the handshake theorem to find the number of sides
vector<vector<int> > M(n, vector<int>(m, 0)); // incidence matrix
getIncidenceMatrix(A, M);
cout << "Output incidence matrix:" << endl;
printMatrix(M);
vector<vector<int> > sequences; // Record the sequence set of n - 1 order determinant
vector<int> sequence; // Record n - 1 order determinant
selectSequence(0, n - 1, sequences, sequence, m);
// Cout < < sequences size < < sequences size() << endl;
cout << "Number of spanning trees:" << endl;
unordered_set<int> store; // Stores the position of the n - 1 determinant of all spanning trees
printf("%d\n", numOfSpanningTree(M, sequences, store));
int t = *store.begin(); // Here, select the n - 1 determinant corresponding to one of the spanning trees
vector<vector<int> > tA(n, vector<int>(n, 0)); // Adjacent matrix of the tree
vector<vector<int> > tM(n, vector<int>(n - 1, 0)); // The incidence matrix of one of the spanning trees
for (int i = 0; i < n; ++i) // i is the vertex sequence number
{
for (int j = 0; j < n - 1; ++j)
{
sequence.push_back(sequences[t][j]); // sequences[t][j] is the side sequence number
tM[i][j] = M[i][sequences[t][j]]; // Here, the n - 1 edges in the spanning tree are renumbered
}
}
printf("Incidence matrix of any spanning tree:\n");
printMatrix(tM);
for (int j = 0; j < n - 1; ++j) // Ergodic edge
{
int x = -1;
int y = -1;
for (int i = 0; i < n; ++i) // Traversal vertex
{
if (tM[i][j] == 1)
{
if (x == -1)
{
x = i;
}
else
{
y = i;
}
}
}
tA[x][y] = 1;
tA[y][x] = 1;
}
printf("Any adjacent generated matrix:\n");
printMatrix(tA);
unordered_set<int> strings; // Store chord sequence number
unordered_set<int> branches; // Store branch serial number
vector<unordered_set<int> > cutSystem; // The basic broken set system that stores the spanning tree
vector<unordered_set<int> > loopSystem; // The basic loop system that stores the spanning tree
unordered_map<int, vector<int> > endpoints; // Compressed version of the incidence matrix, the value is the endpoint sequence number
endpointsOfEdge(endpoints, M);
branchSet(sequence, branches);
stringSet(strings, branches);
printf("branches:%d\n", branches.size());
printf("strings:%d\n", strings.size());
// Basic cut set system: first put a branch and all strings into a false cut set,
// Then operate on the adjacency matrix, remove all strings and a branch, and then try to add strings. If they are still disconnected after adding, add this string
// Then, the added strings are removed from the false cut set, and finally the true cut set is obtained
unordered_set<int> temp;
vector<vector<int> > P(A); // Copy adjacency matrix
for (auto it = strings.begin(); it != strings.end(); ++it)
{
temp.insert(*it);
// Operate on the adjacency matrix and remove all strings
int v1 = endpoints[*it][0];
int v2 = endpoints[*it][1];
P[v1][v2] = 0;
P[v2][v1] = 0;
}
for (auto it = branches.begin(); it != branches.end(); ++it)
{
unordered_set<int> fSet(temp);
vector<vector<int>> tP(P);
vector<int> visited(n, 0);
// For the operation of adjacency matrix, remove a branch. At this time, the adjacency matrix should be disconnected, otherwise an error will be reported
fSet.insert(*it); // Add the serial number of a branch
int v1 = endpoints[*it][0];
int v2 = endpoints[*it][1];
tP[v1][v2] = 0;
tP[v2][v1] = 0;
if (isConnected(tP, visited))
{
cout << "Wrong, it can't be connected after removing all strings and a branch!" << endl;
exit(1);
}
for (auto p = strings.begin(); p != strings.end(); ++p)
{
// Judge whether the adjacency matrix with this string is connected. If it is still not connected, delete it in the false cut set. If it is connected, delete it in the adjacency matrix
int v1 = endpoints[*p][0];
int v2 = endpoints[*p][1];
tP[v1][v2] = 1;
tP[v2][v1] = 1;
for (int i = 0; i < n; ++i)
visited[i] = 0;
if (!isConnected(tP, visited)) // Still disconnected, remove this string from the false cut set
{
fSet.erase(*p);
}
else // Connected indicates that this string is part of the true cut set
{
tP[v1][v2] = 0;
tP[v2][v1] = 0;
}
}
cutSystem.push_back(fSet);
}
printf("Basic cut set system:\n");
printEdgeSet(cutSystem, 0);
// Basic loop system
basicCircuitSet(loopSystem, branches, strings, endpoints);
printf("Basic loop system:\n");
printEdgeSet(loopSystem, 1);
vector<unordered_set<int> > loopSpace;
vector<unordered_set<int> > cutSpace;
// To find the loop space, the loop operation is not a two loop operation. 0 is an empty set and 1 is itself,
// Therefore, there is still a process of selecting m from n, that is, which basic circuits are cyclized to obtain the final edge set
for (auto i = loopSystem.begin(); i != loopSystem.end(); ++i)
{
loopSpace.push_back(*i); // A ring
for (auto j = i + 1; j != loopSystem.end(); ++j) // Ring in pairs
{
unordered_set<int> temp;
cyclization(*i, *j, temp);
loopSpace.push_back(temp);
}
}
if (loopSystem.size() == 3) // Three rings
{
auto t1 = loopSystem.begin();
auto t2 = t1 + 1;
unordered_set<int> temp1;
cyclization(*t1, *t2, temp1);
unordered_set<int> temp2;
t2++;
cyclization(temp1, *t2, temp2);
loopSpace.push_back(temp2);
}
else if (loopSpace.size() > 3)
{
int num = loopSystem.size();
for (int i = 3; i <= int(loopSpace.size()); ++i) // i represents the number of loops participating in the ring closure
{
// Firstly, i loops are selected from num loops, and then the i loops are looped
vector<vector<int>> sets;
vector<int> temp;
selectSequence(0, i, sets, temp, num);
for (int ti = 0; ti < int(sets.size()); ++ti) // sets[ti][tj] is the serial number of the loop in the loopSystem
{
auto t1 = loopSystem[sets[ti][0]];
unordered_set<int> t;
for (int tj = 1; tj < i; ++tj)
{
auto t2 = loopSystem[sets[ti][tj]];
cyclization(t1, t2, t);
t1 = t; // The current partial cyclization is assigned to t1
t.clear();
}
loopSpace.push_back(t1); // One of the i cyclization results has a total of sets Size ()
}
}
}
printf("The loop space corresponding to the spanning tree:\n");
printEdgeSet(loopSpace, 2);
// //Finding fault set space
for (auto i = cutSystem.begin(); i != cutSystem.end(); ++i)
{
cutSpace.push_back(*i); // A broken set
for (auto j = i + 1; j != cutSystem.end(); ++j) // Ring in pairs
{
unordered_set<int> temp;
cyclization(*i, *j, temp);
cutSpace.push_back(temp);
}
}
if (cutSystem.size() == 3) // Three rings
{
auto t1 = cutSystem.begin();
auto t2 = t1 + 1;
unordered_set<int> temp1;
cyclization(*t1, *t2, temp1);
unordered_set<int> temp2;
t2++;
cyclization(temp1, *t2, temp2);
cutSpace.push_back(temp2);
}
else if (cutSpace.size() > 3)
{
int num = cutSystem.size();
for (int i = 3; i <= int(cutSpace.size()); ++i) // i represents the number of fault sets participating in the cyclization
{
// Firstly, i fault sets are selected from num fault sets, and then the i fault sets are cyclized
vector<vector<int>> sets;
vector<int> temp;
selectSequence(0, i, sets, temp, num);
for (int ti = 0; ti < int(sets.size()); ++ti) // sets[ti][tj] is the serial number of the loop in the cutSystem
{
auto t1 = cutSystem[sets[ti][0]];
unordered_set<int> t;
for (int tj = 1; tj < i; ++tj)
{
auto t2 = cutSystem[sets[ti][tj]];
cyclization(t1, t2, t);
t1 = t; // The current partial cyclization is assigned to t1
t.clear();
}
cutSpace.push_back(t1); // One of the i cyclization results has a total of sets Size ()
}
}
}
printf("Broken set space corresponding to the spanning tree:\n");
printEdgeSet(cutSpace, 3);
return 0;
}
test result
Test case 1:
Enter the number of vertices:
4
Enter adjacent matrix:
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0
Output incidence matrix:
1 1 1 0 0
1 0 0 1 0
0 1 0 0 1
0 0 1 1 1
sequences Size 10
Number of spanning trees:
8
Incidence matrix of any spanning tree:
1 0 0
0 1 0
0 0 1
1 1 1
Adjacent matrix of any spanning tree:
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0
branches:3
strings:2
Basic cut set system:
{{e5,e2},{e4,e1},{e3,e2,e1}}
Basic loop system:
{e2e5e3,e1e4e3}
The loop space corresponding to the spanning tree:
{null set,e2e5e3,e4e1e5e2,e1e4e3}
Broken set space corresponding to the spanning tree:
{null set,{e5,e2,e1},{e4,e5},{e3,e5},{e4,e2,e1},{e3,e4},{e3,e2,e1}}
Test case II
Enter the number of vertices:
4
Enter adjacent matrix:
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Output incidence matrix:
1 1 0 1 0 0
1 0 1 0 1 0
0 1 1 0 0 1
0 0 0 1 1 1
Number of spanning trees:
16
Incidence matrix of any spanning tree:
1 0 0
0 1 0
0 0 1
1 1 1
Adjacent matrix of any spanning tree:
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0
branches:3
strings:3
Basic cut set system:
{{e6,e2,e3},{e5,e1,e3},{e4,e1,e2}}
Basic loop system:
{e3e6e5,e2e6e4,e1e5e4}
The loop space corresponding to the spanning tree:
{null set,e3e6e5,e4e2e5e3,e4e1e6e3,e2e6e4,e5e1e6e2,e1e5e4,e1e3e2}
Broken set space corresponding to the spanning tree:
{null set,{e6,e2,e3},{e5,e2,e1,e6},{e4,e3,e1,e6},{e5,e1,e3},{e2,e4,e3,e5},{e4,e1,e2},{e4,e6,e5}}
Test case III
Enter the number of vertices:
2
Enter adjacent matrix:
0 1
1 0
Output incidence matrix:
1
1
Number of spanning trees:
1
Incidence matrix of any spanning tree:
1
1
Adjacent matrix of any spanning tree:
0 1
1 0
branches:1
strings:0
Basic cut set system:
{{e1}}
Basic loop system:
null set
The loop space corresponding to the spanning tree:
{null set}
Broken set space corresponding to the spanning tree:
{null set,{e1}}
Test case 4
Enter the number of vertices:
5
Enter adjacent matrix:
0 1 1 0 0
1 0 0 1 0
1 0 0 1 0
0 1 1 0 1
0 0 0 1 0
Output incidence matrix:
1 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 1 1
0 0 0 0 1
Number of spanning trees:
4
Incidence matrix of any spanning tree:
1 0 0 0
0 1 0 0
1 0 1 0
0 1 1 1
0 0 0 1
Adjacent matrix of any spanning tree:
0 0 1 0 0
0 0 0 1 0
1 0 0 1 0
0 1 1 0 1
0 0 0 1 0
branches:4
strings:1
Basic cut set system:
{{e5},{e4,e1},{e3,e1},{e2,e1}}
Basic loop system:
{e1e3e4e2}
The loop space corresponding to the spanning tree:
{null set,e1e3e4e2}
Broken set space corresponding to the spanning tree:
{null set,{e5},{e1,e4,e5},{e1,e3,e5},{e1,e2,e5},{e4,e1},{e3,e4},{e2,e4},{e3,e1},{e2,e3},{e2,e1},{e3,e5,e4},{e2,e5,e4},{e2,e5,e3},{e1,e2,e4,e3},{e1,e3,e5,e4,e2}}