Exploring Graph Algorithms and TSP

What is Kruskal's Algorithm used for?

• Finding the largest connected component in a graph.

• Finding the minimum spanning tree of a graph.

• Sorting a list of numbers.

• Calculating the shortest path in a graph.

Describe the main steps of Prim's Algorithm.

• Start with all vertices included and remove the largest edge.

• Select edges randomly until all vertices are connected.

• Use a depth-first search to explore all edges before adding them.

• The main steps of Prim's Algorithm are: initialize a tree, add the smallest edge, and repeat until all vertices are included.

What defines a Minimum Spanning Tree (MST)?

• A Minimum Spanning Tree is a tree that includes all edges of the graph.

• A Minimum Spanning Tree connects all vertices with the minimum total edge weight and no cycles.

• A Minimum Spanning Tree connects all vertices with the maximum total edge weight.

• A Minimum Spanning Tree can have cycles as long as it connects all vertices.

List one real-world application of the Traveling Salesman Problem (TSP).

• Logistics and delivery route optimization.

• Traveling Salesman Problem in social media marketing.

• Traveling Salesman Problem in video game level design.

• Traveling Salesman Problem for scheduling classes.

What is a heuristic method in the context of TSP?

• A heuristic method is an approach to find approximate solutions to the TSP efficiently.

• A heuristic method is a mathematical proof used to solve the TSP.

• A heuristic method is a random approach to solving the TSP.

• A heuristic method guarantees the optimal solution to the TSP.

Explain the difference between a tree and a graph.

• A tree can be disconnected and still be considered a tree.

• A tree is a connected, acyclic graph with a hierarchical structure, while a graph can have cycles and may not be connected.

• A graph is always a tree with a single root node.

• A tree is a type of graph that can have cycles.

How does Kruskal's Algorithm ensure that no cycles are formed?

• Kruskal's Algorithm uses a depth-first search to find cycles.

• Kruskal's Algorithm adds edges randomly without checking for cycles.

• Kruskal's Algorithm requires all edges to be connected before processing.

• Kruskal's Algorithm ensures no cycles by using a union-find structure to check if vertices are in the same component before adding an edge.

What is the time complexity of Prim's Algorithm using a priority queue?

• O(V^2)

• O(E)

• O(E + V)

• O(E log V)

Name a common heuristic used to solve the TSP.

• Genetic Algorithm

• Nearest Neighbor

• Brute Force

• Dynamic Programming

What is the significance of edge weights in graph theory?

• Edge weights are only relevant in directed graphs.

• Edge weights represent the number of vertices in a graph.

• Edge weights determine the cost or value of traversing edges, impacting pathfinding and optimization in graphs.

• Edge weights indicate the color of the edges.