Discrete Math: Graph Algorithms and Paths

Using Breadth First Search (BFS), find the shortest path between a start node and an end node in an unweighted graph.

Using the breadth-first search method, find all the nodes discoverable from the root node $A$ in a given graph.

Determine if each graph has an Euler Path, and if it does, find the Euler Path.

What sort of algorithms can be used to allow a computer to efficiently solve the problem of determining connectivity between two vertices?

What is the path of the least length between two vertices in a graph (shortest path problem)?

Does a path exist that uses every edge exactly once in a graph, and what algorithms exist to determine this?

What about the existence of a path that uses every vertex exactly once in a graph, and why is this problem characterized by exponential time algorithms?

Find a Hamiltonian circuit for the given graph, ensuring that each vertex is visited exactly once, and return to the starting vertex.

Determine if a Hamiltonian path or circuit exists for the given graph, considering the structure and connections of its vertices.

Given a graph where the edges have weights, find the optimal Hamiltonian circuit with the lowest total weight. This brings us to the Traveling Salesman Problem, where a salesperson needs to visit each city once and return home at the lowest cost, examining airfare costs between cities.

Given a graph G, determine its vertex connectivity $\kappa(G)$ by identifying the minimum number of vertices that can be deleted to disconnect the graph or make it trivial.

For example, in specific cases, identify if deleting certain vertices (e.g., $V_2$ or $V_5, V_7$) disconnects the graph or reduces it to a trivial graph.