Write an algorithm to check whether a given undirected graph contains a vertex that is connected to all other vertices.

To check whether a given undirected graph contains a vertex that is connected to all other vertices, we can follow an algorithmic approach. Such a vertex is often referred to as a "universal vertex" or a "central vertex". Here's a step-by-step algorithm to determine if such a vertex exists in the graph:

Step 1: Represent the Graph

First, we need to represent the graph in a way that is easy to work with. The most common representations are adjacency matrices and adjacency lists.

Adjacency Matrix Representation

An adjacency matrix is a 2D array A where A[i][j] is 1 (or any non-zero value) if there is an edge between vertex i and vertex j, and 0 otherwise.

Adjacency List Representation

An adjacency list is an array of lists. The i-th list contains all the vertices that are connected to the i-th vertex.

Step 2: Check for Universal Vertex

To find a universal vertex, we can check each vertex to see if it is connected to all other vertices. However, there is a more efficient way to do this by using the properties of a universal vertex.

Properties of a Universal Vertex

1. If a universal vertex exists, it is the only one in the graph.
2. A universal vertex must have a degree of n-1, where n is the number of vertices in the graph.

Step 3: Algorithm

Here is a detailed algorithm using the adjacency list representation:

Algorithm: CheckUniversalVertex(graph)
Input: graph - an undirected graph represented as an adjacency list
Output: The index of the universal vertex or -1 if it does not exist

1. Initialize degreeCount array of size n (number of vertices) with all zeros.
2. For each vertex v in the graph:
    a. For each neighbor u of vertex v:
        i. Increment degreeCount[v] by 1.
3. For each vertex v in the graph:
    a. If degreeCount[v] is equal to n - 1:
        i. Return v as the universal vertex.
4. If no universal vertex is found, return -1.

Step 4: Example

Let's consider a simple graph with 4 vertices (0, 1, 2, 3) and the following edges: (0-1), (0-2), (0-3), (1-2).

The adjacency list representation would be:

• Vertex 0: [1, 2, 3]
• Vertex 1: [0, 2]
• Vertex 2: [0, 1]
• Vertex 3: [0]

Running the algorithm on this graph:

• degreeCount after Step 2: [3, 2, 2, 1]
• After Step 3, we find that vertex 0 has a degree of 3, which is equal to n - 1 (4 - 1). Therefore, vertex 0 is the universal vertex.

Step 5: Complexity Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This is because we traverse each edge once when building the degreeCount array, and we traverse each vertex once when checking for the universal vertex.

The space complexity is O(V), as we need to store the degree count for each vertex.

Conclusion

By following the above algorithm, we can efficiently determine if an undirected graph contains a universal vertex and identify it if it exists.