AI Generated Answers. The questions come from this blog’s graph-mining posts and are attributed to Sayed Ahmed. New AI-generated answers, examples and original illustrations are offered for reuse without copyright restrictions asserted by this blog. External resources retain their own licenses; verify technical details.
Course index: Graph Mining – 1. Original question sources: Original post and repost. This part answers questions 02.25 through 02.48.
Conventions: Unless stated otherwise, graphs are simple with no self-loops; V is the vertex count, E is the edge count, and adjacency lists are outgoing-neighbor lists for directed graphs.
Q02.25. Represent the following Graph using Adjacency List approach of Graph Representation Edges: {0, 1} {0, 4} {1, 2} {1, 3} {1, 4} {2, 3} {3, 4}
Answer. For the specified five-vertex graph:0: [1,4]1: [0,2,3,4]2: [1,3]3: [1,2,4]4: [0,1,3]. This is an undirected representation, so each edge is stored at both ends.
Q02.26. What are the advantages/pros of the Adjacency List Representation?
Answer. Adjacency lists use Θ(V+E) space for simple sparse graphs and permit visiting neighbors in time proportional to their number. Traversals such as BFS/DFS run in O(V+E) on this representation.
Q02.27. What are the disadvantages/cons of the Adjacency List Representation?
Answer. For an unsorted list, testing whether u is adjacent to v may take O(deg(u)); removing an edge also requires locating it. For high-degree vertices this can be expensive. A hash-set neighbor representation often makes average membership tests faster at some memory cost.
Q02.28. Describe the Adjacency Tensor approach of Graph Representation.
Answer. An adjacency tensor adds an axis for time, edge relation, or another dimension. For time-indexed snapshots, T[t,i,j] records edge i→j at time t. Its dimensions are time × vertices × vertices; conventions vary by application.
Q02.29. Give a small example graph then represent it using the Adjacency Tensor approach of Graph Representation.
Answer. For three vertices A,B,C at two times: t0 contains A–B only, t1 contains A–B and B–C. The two 3×3 symmetric slices are:t0: [[0,1,0],[1,0,0],[0,0,0]]t1: [[0,1,0],[1,0,1],[0,1,0]].
Q02.30. Represent the following Graph using Adjacency Tensor approach of Graph Representation Edges: {0, 1} {0, 4} {1, 2} {1, 3} {1, 4} {2, 3} {3, 4}
Answer. The seven given edges define one static adjacency matrix (see 02.20). To make a temporal tensor, specify times: for example T[0,:,:] is that matrix, and T[1,:,:] is a second 5×5 matrix after deleting edge {0,4}. Without a time/layer specification there is no unique third axis.
Q02.31. What are the advantages/pros of Adjacency Tensor Representation?
Answer. A tensor can represent multiple snapshots or edge types in a uniform structure and supports vectorized numerical operations, temporal learning, and matrix/tensor factorization. It makes layer-specific or time-specific comparisons explicit.
Q02.32. What are the disadvantages/cons of Adjacency Tensor Representation?
Answer. A dense tensor needs Θ(TV²) space for T snapshots, much more than sparse event logs; absent vertices/time irregularities and missing observations need careful handling. Sparse tensors or temporal edge tables may be more efficient.
Q02.33. True or False? Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph.
Answer. True. For a graph with V vertices, the standard adjacency matrix has dimensions V×V. For some multigraphs or temporal models extra arrays/axes may be needed.
Q02.34. Can the Adjacency Matrix represent weighted graphs?
Answer. Yes. Store an edge’s weight in the corresponding entry. Use a distinct absent-edge sentinel (such as ∞ for some shortest-path formulations or a separate boolean mask) when zero weight is possible.
Q02.35. How easy it is you think to represent graphs using Adjacency Matrix?
Answer. It is straightforward when V is known and the graph is moderately small or dense: index vertices 0…V−1, initialize V×V cells, fill entries. It is less practical for huge sparse graphs or rapidly changing vertex sets.
Q02.36. What is the complexity of removing an edge from Adjacency Matrix representation?
Answer. Removing an edge in a fixed-size adjacency matrix is O(1): set A[u,v] to absent and, if undirected, A[v,u] too. Locating the correct matrix indices is assumed O(1).
Q02.37. What is the complexity of queries such as whether there is an edge between vertex a and b for Adjacency Matrix representation?
Answer. Checking whether edge u→v exists is O(1): read A[u,v]. The matrix must already be indexed; finding an external vertex key’s index may add lookup cost.
Q02.38. What is the Space complexity for Adjacency Matrix representation? Use vertex count to represent.
Answer. A dense adjacency matrix uses Θ(V²) cells, regardless of the number of edges. A bit-packed Boolean matrix can reduce constants but not asymptotic space.
Q02.39. What is the complexity of adding an edge from Adjacency Matrix representation?
Answer. Adding an edge in a fixed-size adjacency matrix is O(1): update A[u,v] (and A[v,u] for an undirected edge). Adding a new vertex is a different, potentially more expensive operation.
Q02.40. For the Adjacency List approach, how many total lists are there? How many vertices each list can have at best?
Answer. One adjacency container is associated with each vertex, so there are V lists (including empty lists for isolated vertices). In a simple graph, any list can contain at most V−1 distinct neighbors without self-loops; with self-loops the bound changes.
Q02.41. For the Adjacency List approach, how many lists are there for one vertex?
Answer. Exactly one outgoing-neighbor list or container per vertex in the usual representation. A separate incoming-neighbor index is optional for directed graphs.
Q02.42. How much Space does the Adjacency List approach take?
Answer. Adjacency lists take Θ(V+E) space for a directed simple graph, or Θ(V+2E)=Θ(V+E) for an undirected graph whose edges appear in both endpoint lists.
Q02.43. How many elements does an Adjacency list contain for an undirected graph? Represent using E = edge count. For the complete representation of the Graph.
Answer. For an undirected simple graph with E edges, the total number of neighbor entries is 2E, excluding list headers/vertex storage and assuming each undirected edge appears once in the edge set.
Q02.44. Why the complete representation of an undirected Graph using Adjacency List will have 2|E| number of elements?
Answer. An undirected edge {u,v} contributes one adjacency entry v in u’s list and another entry u in v’s list. Therefore E undirected edges contribute 2E entries. A self-loop’s exact storage policy should be stated separately.
Q02.45. How many times does an edge appear in the complete representation of the Undirected Graph using the Adjacency List?
Answer. Twice: once from each endpoint in a conventional undirected adjacency list. In the graph’s abstract edge set, the undirected edge is still only one edge.
Q02.46. Why the complete representation of the Directed Graph using Adjacency List will have |E| number of elements?
Answer. For a directed edge (u,v), only v appears in u’s outgoing list. Thus the complete outgoing-adjacency representation stores E neighbor entries. An extra incoming index would also hold E entries.
Q02.47. How many times does an edge appear in the complete representation of the Directed Graph using the Adjacency List?
Answer. Once in the standard outgoing adjacency lists. If you separately maintain incoming lists, each directed edge is stored one additional time in that second index.
Q02.48. How many dimensions will an Adjacency Tensor have for Tensor? What is this for Dynamic Graphs?
Answer. A time-indexed adjacency tensor is usually three-dimensional: T×V×V. With multiple relation types it may be R×T×V×V (four dimensions); the number of axes is a modeling choice, not an immutable rule.
Practice: Convert one model to another
import networkx as nx
import numpy as np
edges = [(0,1),(0,4),(1,2),(1,3),(1,4),(2,3),(3,4)]
G = nx.Graph()
G.add_nodes_from(range(5))
G.add_edges_from(edges)
A = nx.to_numpy_array(G, nodelist=range(5), dtype=int)
print(A)
print("Neighbor entries:", sum(dict(G.degree()).values()))
# The printed 5x5 matrix is symmetric.
# Neighbor entries: 14
Check that each undirected edge produces two ones in the matrix and two adjacency-list entries. Then remove one edge and repeat; no external data is needed.
