 # Exercise 1: Input: Directed graph G=(V,E) Write a pseudo-code alg...

## Question

Exercise 1:
Input: Directed graph G=(V,E)
Write a pseudo-code algorithm that uses DFS (Depth-first search) that decides if a given graph has an unique topological order (topological sort).
What is the running time? Why does it work?

Exercise 2:
Input: Undirected Graph, G=(V,E) and an edge (U,V) ∈ E.
Write a pseudo-code algorithm that decide if a given edge is inside some circle in G but not in ALL the circles in G.
What is the running time? Why does it work?

Exercise 3:
Input: Directed graph G=(V,E) , it is known that E is NOT an empty set.
Write two pseudo-code algorithm:
A) That checks if G is a acyclic graph. If truth, find the minimal set of vertices that form a directed path which can reach all the vertices in the graph.
B) Find the minimal set of vertices that form a directed path which can reach every vertex in the graph.
What is the running time? Why does it work? For A and B.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

Exercise 1:
Input: Directed graph G=(V,E)
Write a pseudo-code algorithm that uses DFS (Depth-first search) that decides if a given graph has an unique topological order(topological sort).
What is the running time? Why does it work?
• Pseduo-code

Boolean isHamiltonPath(v, ADJ, L, stack_size)
If stack_size == size of ADJ then
Return true
For i in range 0 to size of ADJ
If there is a edge from ADJ[v] to ADJ[i] and L[i] == false then
L[i] = true
If isHamiltonPath(i, ADJ, L, stack_size + 1) == true
Return true
L[i] = fasle
Return false

Boolean hasHamiltonPath(G)
L <- empty list of boolean value
Put all vertex in G to an array named ADJ
For i in range of 0 to number of vertex in G
Push false to L
For i in range 0 to size of ADJ
L[i] = true
If isHamiltonPath(i, ADJ, L, 1) == true then
Return true
L[i] = false...

By purchasing this solution you'll be able to access the following files:
Solution.docx.

\$125.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Theoretical Computer Science Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.