Graph Theory Quiz

What is a cut in graph theory?

• A way to calculate the flow in a graph

• A way to divide a graph into two non-overlapping subsets

• A method to find the shortest path

• A technique to merge two graphs

What is a cut-set?

• A type of graph traversal

• A collection of vertices in a graph

• A set of edges with each endpoint in different subsets after a cut

• A method to calculate graph distance

What defines a minimum cut?

• It has a size/weight not greater than any other cut

• It has the largest number of edges

• It connects all vertices in the graph

• It is the only cut possible

What is the size of the minimum cut mentioned?

• 2

• 3

• 4

• 5

What does flow represent in a graph?

• The distance between two nodes

• The capacity of an edge

• The number of vertices

• The total weight of the graph

What is a maximum flow?

• The flow that is equal to the number of edges

• The flow that has the least weight

• The flow that connects all vertices

• The flow that can achieve the maximum transfer rate

What is the relationship between maximum flow and minimum cut?

• Maximum flow is always less than minimum cut

• Minimum cut is irrelevant to flow

• They are always different

• The maximum flow value equals the minimum cut value

What is an isomorphic graph?

• Graphs that have no edges

• Graphs that are identical in shape

• Graphs that have the same number of vertices

• Two graphs that can be mapped to each other with a one-to-one correspondence

What does graph edit distance measure?

• The number of changes needed to transform one graph into another

• The weight of the heaviest edge

• The total number of edges in a graph

• The distance between two vertices

Which algorithm is used for graph traversal?

• Minimum spanning tree algorithm

• Shortest path algorithm

• Graph edit distance algorithm

• Graph traversal algorithm