代写Graph Theory、代做Data Structures、代写C++，Java程序语言

日期：2019-08-07 10:15

Summer Project - 2019

Graph Theory: Representation and Algorithms

1 Introduction

In order to complete this project successfully, the student should be familiar with many basic

notions of graph theory. The questions below whose answers should be included in the project

report will force the student to go over these necessary background notions about graphs. Most

of the background can be studied in the following references, specially Cormen textbook where

graph definitions can be found in Appendix B.4 and the Graph Algorithms can be read in chapters

22 to 26.

1. Introduction to Algorithms, T.H. Cormen et al., 3/e, The MIT Press, 2009.

2. Data Structures & Algorithms in Java, R. Lafore, 2/e, Sams Publishing, 2002.

3. Data Structures & Problem Solving Using C++, M. Weiss, 2/e, Pearson, 2003.

4. Data Structures & Algorithm in C++, M.T. Goodrich et al., 2/e, Wiley, 2011.

1.1 Theoretical Questions

Throughout all this project, we are only concerned with finite graphs.

1. Define the following concepts:

(a) Undirected graph (ungraph) G = (V,E).

(b) Directed graph (digraph) G = (V,E).

(c) Degree (deg) of a vertex in an ungraph.

(d) The in-degree (deg?) and the out-degree (deg+) of a vertex in a digraph.

(e) A simple graph.

(f) A path and simple path in an ungraph and a digraph.

(g) A cycle in ungraph and digraph.

(h) A (strongly) connected ungraph (digraph) and the (strongly) connected components of

a graph (digraph).

(i) A weighted graph.

(j) A directed acyclic graph (DAG).

2. Prove the following (where |E| is the number of edges in G):

(a) If G = (V,E) is an ungraph then

∑

v∈V

degv = 2|E|.

(b) If G = (V,E) is a digraph then

∑

v∈V

deg+ v = ∑

v∈V

deg v = |E|.

3. Prove that any undirected graph has an even number of vertices of odd degree.

4. Show that in a simple graph with at least two vertices there must be two vertices that have

the same degree.

5. Give the definition of a complete graph G = Kn with n vertices. What is the number of edges

in Kn? Explain how this is computed.

6. Given the following digraph G = (V,E)

Figure 1: Digraph.

(a) Give the in-degree and the out-degree of each vertex of G.

(b) Give its adjacency-list representation.

(c) Give its adjacency-matrix representation.

(d) List all the directed cycles in G.

(e) List all the cycles in the underlying undirected graph Gu of G.

(f) Is G strongly connected?

(g) What are its strongly connected components?

2

7. Consider the digraph below.

(0,0) (1,0) (2,0) (3,0)

(0,1) (1,1) (2,1) (3,1)

(0,2) (1,2) (2,2) (3,2)

(0,3) (1,3) (2,3) (3,3)

(a) How many different directed simple paths are there from vertex (3,1) to vertex (3,3)?

List all of them by giving the ordered sequence of vertices.

(b) How many strongly connected components are there in this graph? Specify all of them

by giving the list of vertices.

8. Given an adjacency-list representation of a directed graph, how long does it take to compute

the out-degree of every vertex? How long does it take to compute the in-degrees?

9. The transpose of a directed graph G = (V,E) is the graph G

T = (V,ET), whereE

T = {(v,u) ∈ V ×V : (u, v) ∈ E}.

Thus, GT

is G with all its edges reversed. Describe efficient algorithms for computing GT

from G, for both the adjacency-list and adjacency-matrix representations of G. Analyze the

running times of your algorithms.

10. Give examples of:

(a) Digraphs that are not DAGs

(b) DAGs whose underlying ungraph has (undirected) cycles.

(c) DAGS whose underlying ungraph has no cycles.

3

11. Describe the Depth-First-Traversal and the Breadth-First-Traversal procedures (as described

in Cormen). Show the results of the DFT on the digraph in Figure. Assume that the for

loop of lines 5-7 of the DFT procedure considers the vertices in alphabetical order, and

assume that each adjacency list is ordered alphabetically. Show the discovery and finishing

times for each vertex, and show the classification of each edge.

Figure 2: A digraph for DFS.

12. Describe the algorithm based on the DFS for producing a topological sort order when the

digraph is a DAG.

13. Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on the

dag of Figure ??, under the assumption of the previous exercise.

Figure 3: DAG for Topological Sorting.

14. Describe the Dijkstra’s single-source shortest-paths algorithm and run it on the directed

graph of Figure, first using vertex s as the source and then using vertex z as the source.

Show all the results.

Figure 4: A digraph for shortest path.

4

2 Programming Project

This project involves implementing an adjacency list representation of a weighted graph, and

using it to apply Dijkstra’s shortest paths algorithm (single-source, all destinations(SSAD)) to a

weighted directed graph. The program will read the specification of the problem from a given file

named for instance "File.txt ". The input file will begin with two lines specifying the number of

vertices in the graph, G = (V,E), and the source vertex. Each of those values will be preceded by

a label that ends with a colon character (':'). The next line will be blank. The remainder of the file

will be a matrix (similar to the adjacency-matrix representation) of |V| rows, each containing |V|

integer values for the weights of the edges in the graph. Weights will be integers in the range 1 to

99. Missing edges will be designated by the value 0. Here’s an example:

Output will be written to a file named for instance "Result.txt ". The output file should consist of

two sections, one displaying information about the given graph and the other displaying the results

of running the Dijkstra’s shortest paths SSAD algorithm.

The graph information display consists of a row of labels (see example), followed by |V| rows of

output displaying the graph information in a format similar to the adjacency-list representation of

the graph. For each vertex, there will be one row of data listing the vertex number, followed by a

list of neighbor records. A neighbor record consists of a neighbor (vertex) number, followed by a

colon character, followed by the weight of the corresponding edge. The graph information display

is followed by a blank line.

The SSAD results display begins with two lines of labels (see example), one showing the source

vertex and a blank line, followed by |V| rows showing the results for each possible destination

vertex (including the source vertex itself). Each of these lines consists of three sections, the destination

vertex number, the length (total weight) of the shortest path found, and the actual path

(a sequence of vertex numbers separated by spaces). If a vertex is not reachable from the source

vertex, you should display instead of the length.

5

Here’s an output example that corresponds to the input example above:

2.1 Notes

There are some explicit requirements for the programming project:

Code has to be written in C++, no other platform is accepted.

You must implement a C++ class for the weighted adjacency list representation of a directed

graph; whether it is a template or not is entirely up to you.

Your main class must be called digraph.

The data read from a file and specifying the graph can be stored in a dynamic one dimensional

or two dimensional array as a private member of the class together with the source

vertex.

6

That class must include a member function that writes the display of the graph in the proper

format indicated above.

You have to write an extensive REPORT containing the answers to the 14 theoretical questions

and explaining the programming project, and how to operate your program. For each

input file specification, you have to draw the corresponding digraph in your report and

HIGHLIGHT the shorted path found by the Dijkstra’s SSAD algorithm for each destination

vertex (when the path exists obviously).

Dijkstra’s SSAD algorithm must be implemented as a separate function, not as a member

of the digraph class. That function should take an initialized graph object as one of its

parameters (and the source vertex as the second), and compute the path lengths and shortest

paths, but it should not write any of the display to the output file. That should be done by a

different function that creates the necessary digraph object and calls the SSAD method.

Since you’ll be implementing the complete program, the interfaces of the digraph class and

the SSAD function are up to you.

2.2 Testing

We will include a number of files specifying weighted graphs, and the corresponding SSAD solutions.

You may want to develop additional test cases yourself (there will be some bonus points for

doing that). For marking purposes, it is important to format your output as specified above.

7