A simple graph G = (V,E) consists of V, a nonempty set of vertices (nodes), and...

Transcribed Image Text:

A simple graph G = (V,E) consists of V, a nonempty set of vertices (nodes), and E, a set of unordered pairs of distinct elements of V called edges (arcs). This definition of a graph does not permit multiple edges connecting a pair of vertices. It also does not permit a loop, an edge that connects a vertex to itself. Objects with such edges are called multigraphs. We consider multigraphs without loops. The degree of a vertex v is the number of edges incident with it. The degree of v is denoted with d(v). Suppose a graph has m nodes, numbered n, n2, ..., nm. We can form an m x m matrix where entry i, j is the number of edges (arcs) between vertices n, and n,. This matrix is called the adjacency matrix A of the graph. Thus aj=p where there are p edges between n; and nj. A path in a multigraph is a sequence of alternating vertices and edges, such that all edges are distinct. A path can cross a vertex more than once, but can only cross an edge once. An Euler path in a graph is a path such that every edge is traversed exactly once. An Euler path exists in a connected graph if and only if d(v) is even for every vertex v of G or two vertices have d(v) odd and all others are even. In the first case the path can begin at any vertex and will end there. In the second case the path must begin at one of the vertex with d(v) odd and will end at the other vertex with d(v) odd. Thus if a graph has more than two vertices of d(v) even, then it cannot have an Euler path. Given the adjacency matrix A = 0 2 1 0 0 20 200 1 2022 00202 0 0 2 2 0/ write a C++ program that tests for these three cases. A simple graph G = (V,E) consists of V, a nonempty set of vertices (nodes), and E, a set of unordered pairs of distinct elements of V called edges (arcs). This definition of a graph does not permit multiple edges connecting a pair of vertices. It also does not permit a loop, an edge that connects a vertex to itself. Objects with such edges are called multigraphs. We consider multigraphs without loops. The degree of a vertex v is the number of edges incident with it. The degree of v is denoted with d(v). Suppose a graph has m nodes, numbered n, n2, ..., nm. We can form an m x m matrix where entry i, j is the number of edges (arcs) between vertices n, and n,. This matrix is called the adjacency matrix A of the graph. Thus aj=p where there are p edges between n; and nj. A path in a multigraph is a sequence of alternating vertices and edges, such that all edges are distinct. A path can cross a vertex more than once, but can only cross an edge once. An Euler path in a graph is a path such that every edge is traversed exactly once. An Euler path exists in a connected graph if and only if d(v) is even for every vertex v of G or two vertices have d(v) odd and all others are even. In the first case the path can begin at any vertex and will end there. In the second case the path must begin at one of the vertex with d(v) odd and will end at the other vertex with d(v) odd. Thus if a graph has more than two vertices of d(v) even, then it cannot have an Euler path. Given the adjacency matrix A = 0 2 1 0 0 20 200 1 2022 00202 0 0 2 2 0/ write a C++ program that tests for these three cases.