Question

Write in pseudocode an algorithm that receives a graph and a set of vertices $S\subseteq V(G)$ and
remove from . Please note that no edge incident to vertices of can exist after removal.

Analyze the execution time of your algorithm if the implementation is done in both representations:
adjacency matrix and adjacency list

Answer 1

Adjacency matrix: The following method removes an existing vertex from the graph by shifting the rows to the left and shifting the columns up to replace the row and column values of that vertex with the next vertex and then decreases the number of vertices by 1 in the graph. Hence, its time complexity is O(n2) for each vertex removal.

 def removeVertex(self, x): # checking if the vertex is present if(x>self.__n): print("Vertex not present !") else: # removing the vertex while(x<self.__n): # shifting the rows to left side for i in range(0, self.__n): self.__g[i][x]= self.__g[i][x + 1] # shifting the columns upwards for i in range(0, self.__n): self.__g[x][i]= self.__g[x + 1][i] x = x + 1 # decreasing the number of vertices self.__n = self.__n - 1

Adjacency List: The following method removes an existing vertex from the graph by iterating through the list of each vertex checking for an edge. If the edge is found, then the vertex is deleted in the same way as delete operation is performed in a linked list. Hence, its time complexity is O(n) for each vertex removal.

 def delvertex(self, k): for i in range(self.v): temp = self.graph[i] if i == k: while temp: self.graph[i]= temp.next temp = self.graph[i] # Delete the vertex # using linked list concept if temp: if temp.vertex == k: self.graph[i]= temp.next temp = None while temp: if temp.vertex == k: break prev = temp temp = temp.next if temp == None: continue prev.next = temp.next temp = None