Unit 4: Graphs Theory I - Subjective Questions

MTH401 — Discrete Mathematics • Practice Questions with Detailed Answers

20 questions

Define the following basic graph-theoretic terms with suitable examples: vertex, edge, order, size, adjacent vertices, incident edge, degree, isolated vertex, pendant vertex, loop, and parallel edges.

State and prove the Handshaking Lemma. A graph has six vertices of degree $2$ and four vertices of degree $3$ . Determine the number of edges and the number of vertices of odd degree.

Distinguish among a walk, trail, path, closed walk, circuit, and cycle in an undirected graph. Illustrate the distinctions using a suitable vertex sequence.

Define and compare the complete graph $K_n$ , cycle graph $C_n$ , and an $r$ -regular graph. Derive the number of edges in $K_n$ and state when $K_n$ and $C_n$ are regular.

Explain wheel graphs and cube graphs. Using the convention $W_n=K_1+C_{n-1}$ , determine the degree sequence and number of edges of $W_n$ . Also derive the number of vertices and edges of the $d$ -dimensional cube $Q_d$ .

What is a bipartite graph? Prove that an undirected graph is bipartite if and only if it contains no cycle of odd length.

Define the complete bipartite graph $K_{m,n}$ . Determine its order, size, degree sequence, and regularity condition. Apply the results to $K_{3,4}$ .

Describe the adjacency-list, edge-list, and adjacency-matrix representations of a graph. Compare their storage requirements and suitability for graph algorithms.

Construct the adjacency matrix of the undirected graph with $V=\{a,b,c,d\}$ and $E=\{ab,ac,bc,cd\}$ . Use the matrix to determine the degree of every vertex and verify the number of edges.

Explain the significance of powers of an adjacency matrix. If $A$ is the adjacency matrix of a graph, what does the entry $(A^k)_{ij}$ represent? Demonstrate the result for $k=2$ .

Define the incidence matrix of an undirected graph. Construct it for $V=\{1,2,3,4\}$ and $E=\{e_1=12,e_2=23,e_3=31,e_4=34\}$ . State two important properties of this matrix.

Define graph isomorphism and explain how graph invariants are used to test whether two graphs may be isomorphic. Why is equality of degree sequences not sufficient?

Let $G$ have edges $\{12,23,34,41,15\}$ and let $H$ have edges $\{ac,ce,eb,ba,ad\}$ . Determine whether $G$ and $H$ are isomorphic. If they are, provide and verify an isomorphism.

Define connectedness and connected components in an undirected graph. Prove that the relation $u\sim v$ defined by the existence of a path from $u$ to $v$ is an equivalence relation.

Define a cut vertex and a bridge. For the graph with edges $\{12,23,31,34,45,56,64,67\}$ , identify all cut vertices and bridges, giving reasons.

Distinguish among strongly connected, unilaterally connected, and weakly connected digraphs. Classify the digraph with arcs $\{a\to b,b\to c,c\to a,c\to d\}$ and find its strongly connected components.

Explain how an adjacency matrix represents a digraph. How can the in-degree, out-degree, directed walks, and reachability of vertices be obtained from the matrix?

Describe Dijkstra's algorithm for finding single-source shortest paths. Give its main steps, explain the relaxation operation, and state its correctness condition.

Apply Dijkstra's algorithm from source $A$ to the undirected weighted graph with edges $AB=4$ , $AC=1$ , $CB=2$ , $CD=5$ , $BD=1$ , $BE=7$ , and $DE=3$ . Find all shortest distances and shortest paths.

Initialize

$d(A)=0,\qquad d(B)=d(C)=d(D)=d(E)=\infty.$

Step 1: Settle $A$

Through $AB$ , set $d(B)=4$ .
Through $AC$ , set $d(C)=1$ .

Step 2: Settle $C$ , since it has the smallest tentative distance $1$ .

Through $CB$ , obtain $1+2=3<4$ , so update $d(B)=3$ with predecessor $C$ .
Through $CD$ , set $d(D)=1+5=6$ .

Step 3: Settle $B$ , with distance $3$ .

Through $BD$ , obtain $3+1=4<6$ , so update $d(D)=4$ with predecessor $B$ .
Through $BE$ , set $d(E)=3+7=10$ .

Step 4: Settle $D$ , with distance $4$ .

Through $DE$ , obtain $4+3=7<10$ , so update $d(E)=7$ with predecessor $D$ .

Step 5: Settle $E$ , with distance $7$ .

The final results are:

Vertex	Shortest distance from $A$	Shortest path
$A$	$0$	$A$
$C$	$1$	$A\to C$
$B$	$3$	$A\to C\to B$
$D$	$4$	$A\to C\to B\to D$
$E$	$7$	$A\to C\to B\to D\to E$

The vertices are settled in the order $A,C,B,D,E$ .

Explain why Dijkstra's algorithm requires nonnegative edge weights. Give a counterexample with a negative edge, outline the correctness argument for nonnegative weights, and compare common implementations.

Question 1

Tap card to reveal answer

Answer 1

A graph is written as $G=(V,E)$ , where $V$ is the set of vertices and $E$ is the set of edges.

Vertex: A fundamental point or node of a graph. For example, if $V=\{a,b,c\}$ , then $a$ , $b$ , and $c$ are vertices.
Edge: A connection between two vertices. The edge joining $a$ and $b$ is denoted by $\{a,b\}$ or $ab$ .
Order: The number of vertices in the graph, namely $|V|$ .
Size: The number of edges in the graph, namely $|E|$ .
Adjacent vertices: Two vertices are adjacent if an edge joins them.
Incident edge: An edge is incident with each of its endpoints.
Degree: The degree $\deg(v)$ is the number of edges incident with vertex $v$ . A loop contributes $2$ to the degree.
Isolated vertex: A vertex of degree $0$ .
Pendant vertex: A vertex of degree $1$ .
Loop: An edge whose two endpoints are the same vertex.
Parallel edges: Two or more distinct edges having the same pair of endpoints.

A graph without loops or parallel edges is called a simple graph.

Tap card to flip back

Question 2

State and prove the Handshaking Lemma. A graph has six vertices of degree $2$ and four vertices of degree $3$ . Determine the number of edges and the number of vertices of odd degree.

Tap card to reveal answer

Answer 2

Handshaking Lemma: For every finite undirected graph $G=(V,E)$ ,

$\sum_{v\in V}\deg(v)=2|E|.$

Proof:

Every edge has two endpoints.
While summing the degrees of all vertices, each edge is counted once at each endpoint.
Therefore, every edge contributes exactly $2$ to the degree sum.
Hence, $\sum_{v\in V}\deg(v)=2|E|$ .

For the given graph,

$\sum_{v\in V}\deg(v)=6(2)+4(3)=12+12=24.$

Therefore,

$2|E|=24 \implies |E|=12.$

The four vertices of degree $3$ have odd degree. Thus:

Number of edges: $12$
Number of odd-degree vertices: $4$

The number of odd-degree vertices is even, which is also a consequence of the Handshaking Lemma.

Tap card to flip back

Question 3

Distinguish among a walk, trail, path, closed walk, circuit, and cycle in an undirected graph. Illustrate the distinctions using a suitable vertex sequence.

Tap card to reveal answer

Answer 3

A walk is a sequence $v_0,e_1,v_1,\ldots,e_k,v_k$ in which each edge $e_i$ joins $v_{i-1}$ and $v_i$ . Vertices and edges may repeat.
A trail is a walk in which no edge is repeated, although vertices may repeat.
A path is a walk in which no vertex is repeated. Consequently, no edge is repeated.
A closed walk is a walk whose first and last vertices are the same, so $v_0=v_k$ .
A circuit is a closed trail; it has no repeated edge.
A cycle is a closed path in which only the first and last vertices are equal and all other vertices are distinct.

For edges $ab,bc,ca,cd$ :

$a-b-c-a-b$ is a walk but not a trail because $ab$ is repeated.
$a-b-c-a$ is a circuit and a cycle.
$a-b-c-d$ is a path if all four vertices are distinct.

The length of a walk, trail, or path is the number of edges it contains.

Tap card to flip back

Question 4

Define and compare the complete graph $K_n$ , cycle graph $C_n$ , and an $r$ -regular graph. Derive the number of edges in $K_n$ and state when $K_n$ and $C_n$ are regular.

Tap card to reveal answer

Answer 4

A complete graph $K_n$ is a simple graph in which every pair of distinct vertices is joined by an edge.
A cycle graph $C_n$ , for $n\geq 3$ , consists of $n$ vertices arranged in one cycle.
An $r$ -regular graph is a graph in which every vertex has degree $r$ .

In $K_n$ , every vertex is adjacent to the other $n-1$ vertices, so

$\deg(v)=n-1.$

Using the Handshaking Lemma,

$2|E|=n(n-1),$

and hence

$|E(K_n)|=\frac{n(n-1)}{2}.$

Therefore, $K_n$ is an $(n-1)$ -regular graph.

In $C_n$ , every vertex has exactly two neighbors. Thus,

$|E(C_n)|=n,$

and $C_n$ is $2$ -regular for every $n\geq 3$ .

Tap card to flip back

Question 5

Tap card to reveal answer

Answer 5

Wheel graph: Under the stated convention, $W_n$ is formed by taking a cycle $C_{n-1}$ and adding one new central vertex adjacent to every cycle vertex.

The central vertex has degree $n-1$ .
Each cycle vertex has degree $3$ : two cycle neighbors and the central vertex.
The degree sequence is therefore

$(n-1,\underbrace{3,3,\ldots,3}_{n-1\text{ times}}).$

The cycle contributes $n-1$ edges and the spokes contribute another $n-1$ edges. Hence,

$|E(W_n)|=2(n-1).$

Cube graph: The $d$ -dimensional cube $Q_d$ has all binary strings of length $d$ as its vertices. Two vertices are adjacent when their strings differ in exactly one position.

Number of vertices: $2^d$ .
Each vertex has degree $d$ .
By the Handshaking Lemma,

$2|E(Q_d)|=d2^d,$

$|E(Q_d)|=d2^{d-1}.$

Thus, $Q_d$ is a $d$ -regular bipartite graph.

Tap card to flip back

Question 6

What is a bipartite graph? Prove that an undirected graph is bipartite if and only if it contains no cycle of odd length.

Tap card to reveal answer

Answer 6

A graph $G=(V,E)$ is bipartite if its vertex set can be partitioned into two disjoint sets $X$ and $Y$ such that every edge has one endpoint in $X$ and the other in $Y$ .

Forward direction: Suppose $G$ is bipartite.

While traversing any cycle, the vertices must alternate between $X$ and $Y$ .
To return to the starting vertex, an even number of edges must be traversed.
Therefore, every cycle has even length, so no odd cycle exists.

Reverse direction: Suppose $G$ has no odd cycle.

In each connected component, choose a vertex $s$ .
Put vertices at even distance from $s$ in $X$ and vertices at odd distance from $s$ in $Y$ .
If an edge joined two vertices in the same set, their paths from $s$ , together with that edge, would create an odd cycle.
This contradicts the assumption.

Thus, every edge joins a vertex of $X$ to a vertex of $Y$ , and $G$ is bipartite.

Hence,

$G\text{ is bipartite}\iff G\text{ has no odd cycle}.$

Tap card to flip back

Question 7

Define the complete bipartite graph $K_{m,n}$ . Determine its order, size, degree sequence, and regularity condition. Apply the results to $K_{3,4}$ .

Tap card to reveal answer

Answer 7

A complete bipartite graph $K_{m,n}$ is a bipartite graph with partite sets $X$ and $Y$ , where $|X|=m$ , $|Y|=n$ , and every vertex of $X$ is adjacent to every vertex of $Y$ .

For $K_{m,n}$ :

Order:

$|V|=m+n.$

Size: Each of the $m$ vertices in $X$ is joined to all $n$ vertices in $Y$ , so

$|E|=mn.$

Every vertex in $X$ has degree $n$ .
Every vertex in $Y$ has degree $m$ .
The graph is regular exactly when $m=n$ . In that case, $K_{n,n}$ is $n$ -regular.

For $K_{3,4}$ :

Order: $3+4=7$ .
Size: $3\times 4=12$ .
Three vertices have degree $4$ .
Four vertices have degree $3$ .
It is not regular because $3\neq 4$ .

Tap card to flip back

Question 8

Describe the adjacency-list, edge-list, and adjacency-matrix representations of a graph. Compare their storage requirements and suitability for graph algorithms.

Tap card to reveal answer

Answer 8

Adjacency list:

For each vertex, it stores a list of its neighboring vertices.
Its space requirement is $O(|V|+|E|)$ .
It is efficient for sparse graphs and for traversals such as BFS and DFS.

Edge list:

It stores each edge as a pair $(u,v)$ , or as a triple $(u,v,w)$ for a weighted graph.
Its space requirement is $O(|E|)$ .
It is simple and useful for algorithms that process all edges, but testing whether two particular vertices are adjacent may be slow.

Adjacency matrix:

It is a $|V|\times |V|$ matrix $A$ where $A_{ij}=1$ if $v_i$ and $v_j$ are adjacent, and $A_{ij}=0$ otherwise.
Its space requirement is $O(|V|^2)$ .
Adjacency testing takes $O(1)$ time.
It is suitable for dense graphs and matrix-based computations.

Thus, adjacency lists are usually preferable for sparse graphs, while adjacency matrices are convenient for dense graphs and fast adjacency queries.

Tap card to flip back

Question 10

Explain the significance of powers of an adjacency matrix. If $A$ is the adjacency matrix of a graph, what does the entry $(A^k)_{ij}$ represent? Demonstrate the result for $k=2$ .

Tap card to reveal answer

Answer 10

Let $A$ be the adjacency matrix of a graph. The entry

$(A^k)_{ij}$

is the number of walks of length $k$ from vertex $v_i$ to vertex $v_j$ .

For $k=2$ ,

$(A^2)_{ij}=\sum_{r=1}^{n}A_{ir}A_{rj}.$

The product $A_{ir}A_{rj}$ equals $1$ exactly when both edges $v_iv_r$ and $v_rv_j$ exist. Thus, each nonzero term corresponds to a walk

$v_i-v_r-v_j$

of length $2$ . The sum counts all such intermediate vertices $v_r$ .

For a simple undirected graph, the diagonal entry $(A^2)_{ii}$ equals $\deg(v_i)$ because every neighbor $v_r$ produces the length-two walk $v_i-v_r-v_i$ .

This matrix property is useful for counting walks and studying reachability. It counts walks, not necessarily paths, because vertices and edges may repeat.

Tap card to flip back

Question 11

Define the incidence matrix of an undirected graph. Construct it for $V=\{1,2,3,4\}$ and $E=\{e_1=12,e_2=23,e_3=31,e_4=34\}$ . State two important properties of this matrix.

Tap card to reveal answer

Answer 11

For an undirected graph, the incidence matrix $B$ has one row for each vertex and one column for each edge. For a graph without loops,

$B_{ij}=\begin{cases}1,&\text{if vertex }v_i\text{ is incident with edge }e_j,\\0,&\text{otherwise.}\end{cases}$

Using rows $(1,2,3,4)$ and columns $(e_1,e_2,e_3,e_4)$ ,

$B=\begin{bmatrix} 1&0&1&0\\ 1&1&0&0\\ 0&1&1&1\\ 0&0&0&1 \end{bmatrix}.$

Properties:

Every column contains exactly two $1$ s because every non-loop edge has two endpoints.
The sum of the entries in a row equals the degree of the corresponding vertex.

Thus, the row sums are $2,2,3,1$ , and their total is $8=2|E|$ . For an oriented incidence matrix, one endpoint is represented by $-1$ and the other by $+1$ .

Tap card to flip back

Question 12

Define graph isomorphism and explain how graph invariants are used to test whether two graphs may be isomorphic. Why is equality of degree sequences not sufficient?

Tap card to reveal answer

Answer 12

Two graphs $G=(V_G,E_G)$ and $H=(V_H,E_H)$ are isomorphic if there exists a bijection

$f:V_G\rightarrow V_H$

such that

$uv\in E_G\iff f(u)f(v)\in E_H.$

The function $f$ must preserve both adjacency and non-adjacency.

Properties preserved by isomorphism are called graph invariants. Important invariants include:

Number of vertices and edges.
Degree sequence.
Number of connected components.
Connectedness.
Number and lengths of cycles.
Number of pendant or isolated vertices.
Presence of cut vertices and bridges.
Bipartiteness.

If any invariant differs, the graphs cannot be isomorphic. However, matching invariants do not always prove isomorphism.

For example, $C_6$ and the disjoint union of two triangles both have six vertices, six edges, and degree sequence $(2,2,2,2,2,2)$ . They are not isomorphic because $C_6$ is connected, whereas the union of two triangles has two connected components. Therefore, equal degree sequences are necessary but not sufficient.

Tap card to flip back

Question 14

Define connectedness and connected components in an undirected graph. Prove that the relation $u\sim v$ defined by the existence of a path from $u$ to $v$ is an equivalence relation.

Tap card to reveal answer

Answer 14

An undirected graph is connected if a path exists between every pair of vertices. A connected component is a maximal connected subgraph.

Define a relation on $V$ by

$u\sim v\iff \text{there is a path from }u\text{ to }v.$

To prove that $\sim$ is an equivalence relation:

Reflexive: Every vertex has a path of length $0$ to itself. Hence, $u\sim u$ .
Symmetric: If a path exists from $u$ to $v$ , traversing the same edges in reverse order gives a path from $v$ to $u$ . Hence, $u\sim v$ implies $v\sim u$ .
Transitive: If a path exists from $u$ to $v$ and another path exists from $v$ to $w$ , concatenating them gives a walk from $u$ to $w$ . Removing repeated portions produces a path, so $u\sim w$ .

Thus, $\sim$ is an equivalence relation. Its equivalence classes are precisely the connected components of the graph. A graph is connected exactly when this relation has only one equivalence class.

Tap card to flip back

Question 15

Define a cut vertex and a bridge. For the graph with edges $\{12,23,31,34,45,56,64,67\}$ , identify all cut vertices and bridges, giving reasons.

Tap card to reveal answer

Answer 15

A cut vertex or articulation vertex is a vertex whose removal, together with its incident edges, increases the number of connected components. A bridge is an edge whose removal increases the number of connected components.

The edges $12,23,31$ form a triangle on $\{1,2,3\}$ , and $45,56,64$ form a triangle on $\{4,5,6\}$ . Edge $34$ joins the two triangles, while $67$ attaches the pendant vertex $7$ .

Cut vertices:

Vertex $3$ : Removing it separates vertices $1,2$ from the rest of the graph.
Vertex $4$ : Removing it separates the first triangle from vertices $5,6,7$ .
Vertex $6$ : Removing it isolates vertex $7$ .

Therefore, the cut vertices are

$\{3,4,6\}.$

Bridges:

Edge $34$ is the only connection between the two triangular regions.
Edge $67$ is the only edge incident with vertex $7$ .

Therefore, the bridges are

$\{34,67\}.$

No edge belonging to either triangle is a bridge because an alternative path exists around the corresponding cycle.

Tap card to flip back

Question 16

Tap card to reveal answer

Answer 16

A digraph is strongly connected if, for every pair of vertices $u$ and $v$ , there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$ .
It is unilaterally connected if, for every pair $u,v$ , there is a directed path from $u$ to $v$ or from $v$ to $u$ .
It is weakly connected if replacing every directed arc by an undirected edge produces a connected undirected graph.

In the given digraph, $a,b,c$ lie on the directed cycle

$a\to b\to c\to a,$

so each of these vertices can reach the other two. Also, $c\to d$ , so every vertex among $a,b,c$ can reach $d$ . However, $d$ has no outgoing path back to $a$ , $b$ , or $c$ .

Therefore:

The digraph is not strongly connected.
It is unilaterally connected, because for every pair involving $d$ , the other vertex can reach $d$ .
It is also weakly connected.

Its strongly connected components are

$\{a,b,c\}\quad\text{and}\quad\{d\}.$

Tap card to flip back

Question 17

Explain how an adjacency matrix represents a digraph. How can the in-degree, out-degree, directed walks, and reachability of vertices be obtained from the matrix?

Tap card to reveal answer

Answer 17

For a digraph with vertices $v_1,\ldots,v_n$ , its adjacency matrix $A$ is defined by

$A_{ij}=\begin{cases}1,&\text{if the arc }v_i\to v_j\text{ exists},\\0,&\text{otherwise.}\end{cases}$

Unlike the adjacency matrix of an undirected graph, $A$ need not be symmetric.

The out-degree of $v_i$ is the sum of row $i$ :

$\deg^+(v_i)=\sum_{j=1}^{n}A_{ij}.$

The in-degree of $v_j$ is the sum of column $j$ :

$\deg^-(v_j)=\sum_{i=1}^{n}A_{ij}.$

The entry $(A^k)_{ij}$ gives the number of directed walks of length $k$ from $v_i$ to $v_j$ .
Vertex $v_j$ is reachable from $v_i$ if $(A^k)_{ij}>0$ for some $k$ with $1\leq k\leq n-1$ .

A reachability matrix can be obtained from the Boolean sum

$I\lor A\lor A^2\lor\cdots\lor A^{n-1},$

where arithmetic is interpreted in the Boolean sense. A digraph is strongly connected when every entry of its reachability matrix is $1$ .

Tap card to flip back

Question 18

Describe Dijkstra's algorithm for finding single-source shortest paths. Give its main steps, explain the relaxation operation, and state its correctness condition.

Tap card to reveal answer

Answer 18

Dijkstra's algorithm finds the shortest paths from a source vertex $s$ to all other vertices in a weighted graph whose edge weights are nonnegative.

Initialization:

Set $d(s)=0$ .
Set $d(v)=\infty$ for every $v\neq s$ .
Set the predecessor of every vertex to undefined.
Insert the vertices into a min-priority queue according to their tentative distances.

Main procedure:

Extract an unsettled vertex $u$ having the smallest tentative distance.
Mark $u$ as settled.
For every outgoing edge $(u,v)$ of weight $w(u,v)$ , perform relaxation.
Continue until the queue is empty or all required vertices are settled.

Relaxation: If

$d(u)+w(u,v)<d(v),$

update

$d(v)=d(u)+w(u,v)$

and set the predecessor of $v$ to $u$ .

When a vertex is extracted with the minimum tentative distance, that distance is final because all edge weights are nonnegative. The predecessor links can be followed backward to reconstruct shortest paths.

With an adjacency list and a binary heap, the running time is

$O((|V|+|E|)\log |V|).$

Tap card to flip back

Question 19

Tap card to reveal answer

Answer 19

Initialize

$d(A)=0,\qquad d(B)=d(C)=d(D)=d(E)=\infty.$

Step 1: Settle $A$

Through $AB$ , set $d(B)=4$ .
Through $AC$ , set $d(C)=1$ .

Step 2: Settle $C$ , since it has the smallest tentative distance $1$ .

Through $CB$ , obtain $1+2=3<4$ , so update $d(B)=3$ with predecessor $C$ .
Through $CD$ , set $d(D)=1+5=6$ .

Step 3: Settle $B$ , with distance $3$ .

Through $BD$ , obtain $3+1=4<6$ , so update $d(D)=4$ with predecessor $B$ .
Through $BE$ , set $d(E)=3+7=10$ .

Step 4: Settle $D$ , with distance $4$ .

Through $DE$ , obtain $4+3=7<10$ , so update $d(E)=7$ with predecessor $D$ .

Step 5: Settle $E$ , with distance $7$ .

The final results are:

Vertex	Shortest distance from $A$	Shortest path
$A$	$0$	$A$
$C$	$1$	$A\to C$
$B$	$3$	$A\to C\to B$
$D$	$4$	$A\to C\to B\to D$
$E$	$7$	$A\to C\to B\to D\to E$

The vertices are settled in the order $A,C,B,D,E$ .

Tap card to flip back

Question 20

Tap card to reveal answer

Answer 20

Why nonnegative weights are required: Dijkstra's algorithm permanently settles the vertex with the smallest tentative distance. This decision is safe only if extending another path cannot later reduce that settled distance. Nonnegative weights guarantee this property.

Consider the directed weighted graph with edges

$s\to a=2,\qquad s\to b=5,\qquad b\to a=-10.$

Dijkstra's algorithm may settle $a$ with distance $2$ before processing $b$ . However, the actual shortest path is

$s\to b\to a$

with total weight

$5+(-10)=-5.$

Thus, a negative edge can invalidate a settled distance.

Correctness idea for nonnegative weights: Suppose $u$ is the unsettled vertex with minimum tentative distance. Any alternative path to $u$ through an unsettled vertex must first reach some unsettled vertex $x$ . Since $d(u)\leq d(x)$ and every remaining edge has nonnegative weight, continuing from $x$ cannot produce a path shorter than $d(u)$ . Therefore, $d(u)$ is final when $u$ is settled.

Complexities:

Array or adjacency-matrix implementation: $O(|V|^2)$ .
Binary heap with adjacency lists: $O((|V|+|E|)\log |V|)$ .
Fibonacci heap: $O(|E|+|V|\log |V|)$ .

For graphs with negative edges but no reachable negative cycle, the Bellman-Ford algorithm should be used instead.

Tap card to flip back

1 / 20

Unit3 Unit5

Unit 4: Graphs Theory I - Subjective Questions

Did this save you a night before the exam?