Assignment: Discrete Structures and Analysis
Problem: Write a program to read simple undirected connected graphs into an n x n 2D array. Then determine whether that graph has an Euler Circuit using the algorithm described below. If the graph has an Euler circuit, find one and print out the nodes in the Euler Circuit. If the graph does not have one, print NO EULER CIRCUIT EXISTS.
Method: First your program must determine if the connected graph input and stored in the 2D array has an Euler Circuit. A graph that has vertices of all even degree contains an Euler Circuit. Second, if the graph does have one, then your program must find an Euler Circuit in the graph using a modification of Fleury's algorithm.
Fleury's algorithm, published 1883 constructs Euler subcircuits by first choosing an arbitrary vertex (say 0) of a graph, and forms a circuit by choosing edges successively. Once an edge is chosen, it is removed. Edges are chosen successively so that each edge begins where the last edge ends, and so that this edge is not a cut edge, unless there is no alternative. The algorithm terminates when the original vertex (0) is reached. If there are no edges remaining in the graph, then the path has the constructed Euler circuit, otherwise it has only found a subcircuit. Just stop there and print out a message that only a subcircuit was found.
Important Notes:
- You must use arrays or vectors in this program.
- If you use arrays, you must dynamically allocate memory for each array and properly free up that memory when you finish processing that particular graph (array).
- You must write functions to
o Open the input and output files
o Read in the graph's edges
o Determine if a graph has an Euler Circuit
o Find and print an Euler Circuit using Fleury's algorithm
o Determine if a graph has edges
- There will not be more than 20 vertices.
- Vertices are labelled 0, 1, 2, ...
Format your assignment according to the following formatting requirements:
1. The answer should be typed, double spaced, using Times New Roman font (size 12), with one-inch margins on all sides.
2. The response also include a cover page containing the title of the assignment, the student's name, the course title, and the date. The cover page is not included in the required page length.
3. Also Include a reference page. The Citations and references should follow APA format. The reference page is not included in the required page length.
Download:- HINTS-for-EC-Program.rar