/* You work for a space-communications company and you are told that a network should be free of any loops. Otherwise loops will cause reverberation of the signal. You are given matrices that represent different networks of some spaceships in galaxies far far away. The matrices represent how the spaceships connect to each other(0 not connected, 1 is connected). The matrices are adjency matrices. The question is are there any loops in those networks? How many connections should be removed. Note: a tree graph is a graph with no loops. *************************************************** 1T⋅A⋅1 is the sum of all the entries in the matrix A. These entries are, in position ij, 1 if there is an edge from vertex i to vertex j, and 0 otherwise. (Or, in a multigraph, the number of edges from vertex i to vertex j.) Since the graph is undirected, each edge shows up twice: once in position ij and once in position ji (except for any loops, which just show up in position ii.) So, adding all these up gives us twice the number of edges in the graph, at least if there are no loops. (With loops, it is still true, if we adopt an appropriate convention, e.g. put a 1 in entry ii and count loops as half an edge, or else put a 2 in entry ii (because the loop is incident to vertex i twice.)) if(half==rows-diagonal) then it has no loops and vice versa. */ #include #include int main() { std::vector>> networks{ { {0,1,0}, {1,0,1}, {0,1,0} }, //no loops { {0,1,1}, {1,0,1}, {1,1,0} }, //loopk { {0,1,1,1}, {1,0,0,0}, {1,0,0,0}, {1,0,0,0} }, //no loops { {0,1,1,1}, {1,0,0,0}, {1,0,0,1}, {1,0,1,0} }, //loop { {0,1,0,1}, {1,0,1,0}, {0,1,0,1}, {1,0,1,0} }, //loop { {0,1,0,1,1,0,1,1}, {1,0,1,0,0,1,1,0}, {0,1,0,1,1,0,0,1}, {0,1,1,0,1,0,1,0}, {1,0,1,0,0,1,1,0}, {0,1,0,1,1,0,0,1}, {0,1,0,1,1,0,1,1}, {1,0,1,0,0,1,1,0} }, //loop }; // matrix's diagonal{(1,1),(2,2),(3,3)...} const size_t diagonal{1}; // iterate over networks for (auto& v : networks) { // no of 1s in matrix size_t ones{0}; // display matrix for (size_t i{0},j{0}; ij) ones++; // display matrix status std::cout<<((ones==v.size()-diagonal?"no loop(s)":"loop(s)"))<<"\n\n"; } }

adjacencyMatrixGraph