REVIEW: AQR Fall Final Exam

Define: Degree.

• Degree: The number of edges connected to a vertex in a graph.

• Degree: The total number of vertices in a graph.

• Degree: The sum of all edge weights in a graph.

• Degree: The number of isolated vertices in a graph.

Define: Cycle.

• Cycle: A path in a graph that starts and ends at the same vertex, with no repeated edges or vertices (except the starting/ending vertex).

• Cycle: A path in a graph that starts and ends at different vertices, with repeated edges allowed.

• Cycle: A sequence of edges in a graph that never returns to the starting vertex.

• Cycle: A path in a graph that visits every vertex exactly once without returning to the starting vertex.

Define: Tree.

• Tree: A connected graph with no cycles.

• Tree: A graph with cycles.

• Tree: A disconnected graph.

• Tree: A graph with only one vertex.

Define: Minimal Spanning tree.

• Minimal Spanning tree: A spanning tree of a weighted graph that has the minimum possible total edge weight.

• Minimal Spanning tree: A tree that contains all vertices and has the maximum possible total edge weight.

• Minimal Spanning tree: A subgraph with the least number of edges.

• Minimal Spanning tree: A spanning tree with all edges having equal weights.

Define: Weighted Graphs.

• Weighted Graphs: Graphs in which each edge has an associated numerical value (weight).

• Weighted Graphs: Graphs in which each vertex has a color.

• Weighted Graphs: Graphs with only directed edges.

• Weighted Graphs: Graphs that do not contain any cycles.

The difference between Euler path and Hamiltonian path is:

• Euler path visits every edge exactly once, while Hamiltonian path visits every vertex exactly once.

• Euler path visits every vertex exactly once, while Hamiltonian path visits every edge exactly once.

• Both Euler and Hamiltonian paths visit every edge exactly once.

• Both Euler and Hamiltonian paths visit every vertex exactly once.

The difference between Euler circuit and Hamiltonian circuit is:

• Euler circuit visits every edge exactly once, while Hamiltonian circuit visits every vertex exactly once.

• Euler circuit visits every vertex exactly once, while Hamiltonian circuit visits every edge exactly once.

• Both circuits visit every edge exactly once.

• Both circuits visit every vertex exactly once.

How can you quickly tell if a graph has an Euler Circuit?

• All vertices have even degree.

• The graph is connected and has at least one odd degree vertex.

• The graph has exactly two vertices of odd degree.

• The graph contains a Hamiltonian Circuit.

How can you quickly tell if a graph has an Euler Path?

• By checking if exactly two vertices have odd degree.

• By checking if all vertices have even degree.

• By checking if the graph is connected and has no cycles.

• By checking if every vertex has degree one.

Kruskal's Algorithm is used for which of the following purposes?

• Finding the shortest path in a graph

• Constructing a minimum spanning tree

• Sorting elements in an array

• Detecting cycles in a graph