IB Mathematics Applications & Interpretation Question Type 2: Creating Adjacency Tables for Weighted and Unweighted Graphs Exercises

An undirected weighted graph has vertices $1,2,3,4$ and the following weighted edges:

• $\{1,2\}$ with weight $5$
• $\{1,3\}$ with weight $2$
• $\{2,4\}$ with weight $7$
• $\{3,4\}$ with weight $4$

Create the adjacency table for this graph.

The weighted adjacency table of an undirected graph is:

$$\begin{array}{cl}\text{Vertex}& \text{Neighbors with weights}\\ 1& (2,4),(3,1)\\ 2& (1,4),(3,2),(4,5)\\ 3& (1,1),(2,2),(4,3)\\ 4& (2,5),(3,3)\end{array}$$

Reconstruct the graph and label each edge with its weight.

The adjacency table of an undirected graph is:

$$\begin{array}{cl}V& \text{Neighbors}\\ 1& 2,3\\ 2& 1,4\\ 3& 1,4\\ 4& 2,3,5\\ 5& 4\end{array}$$

Determine the number of connected components in this graph.

Using the adjacency list below for an undirected graph, determine if the graph is connected:

$$\begin{array}{cl}V& \text{Adjacency List}\\ 1& 2\\ 2& 1,3\\ 3& 2,4\\ 4& 3\\ 5& 6\\ 6& 5\end{array}$$

Given the undirected unweighted graph with vertex set $V=\{A,B,C,D,E\}$ and edge set $E=\{AB,AC,BD,CE,DE\}$, construct its adjacency table.

The adjacency table below defines an undirected graph. Determine whether the graph is bipartite.

$$\begin{array}{cl}V& \text{Neighbors}\\ A& B,C\\ B& A,D\\ C& A,D\\ D& B,C\end{array}$$

Given the adjacency list for an undirected graph:

$$\begin{array}{cl}V& \text{Adjacency List}\\ u& v,w\\ v& u,w,x\\ w& u,v,x\\ x& v,w\end{array}$$

Decide if the graph has an Eulerian circuit. Justify your answer.

Determine the in-degree and out-degree of each vertex.

Construct the adjacency table for the directed weighted graph with vertices $A$, $B$, $C$ and arc weights: $A\to B(3)$, $A\to C(6)$, $B\to C(1)$, and $C\to A(4)$.

Given the adjacency table below for an undirected graph, list all edges and sketch the graph:

$$\begin{array}{cl}\text{Vertex}& \text{Adjacency List}\\ P& Q,R\\ Q& P,R,S\\ R& P,Q,T\\ S& Q\\ T& R\end{array}$$

Convert the undirected adjacency list below into its adjacency matrix, ordering vertices as $A,B,C,D$:

$$\begin{array}{cl}V& \text{Neighbors}\\ A& B,D\\ B& A,C\\ C& B,D\\ D& A,C\end{array}$$

From the adjacency table below for an undirected graph, compute the degree of each vertex:

$$\begin{array}{cl}V& \text{Adjacency List}\\ a& b,c,d\\ b& a,d\\ c& a,d\\ d& a,b,c,e\\ e& d\end{array}$$