Multigraph bijections and matrices
Relabel a multigraph without losing parallel edges. Match vertices and edges, and express the same relabelling using matrices.
Concepts for §10.2
Before you begin
Rows, columns and entries
Fix a vertex order. Entry M[i,j] is in row i and column j. For a simple graph it records adjacency as 0 or 1; for a loop-free multigraph it can record the number of parallel edges. Matrix multiplication is explained in this lesson, not assumed as a prerequisite.
Adjacency
Two vertices are adjacent if an edge joins them directly. Being reachable by several edges is a different condition. For an undirected graph, reversing an edge’s endpoint names does not create a new edge.
Definitions and notation for this topic
Matrix of a finite relation
M[a,b]
For R⊆A×B on finite ordered sets, M[a,b]=1 if (a,b)∈R and 0 otherwise. State the row order A and column order B.
An entry represents a particular ordered pair. A multigraph adjacency matrix may count parallel edges and therefore have entries greater than 1; that is a different convention.
Separate glossary example
For A=(1,2), B=(u,v), R={(1,v),(2,u)}, the matrix is [[0,1],[1,0]].
Loops and parallel edges
A loop has the same endpoint twice. Parallel edges are distinct edges with the same endpoints. For an undirected multigraph, retain each edge’s identity and endpoint pair.
A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.
Separate glossary example
e₁=AB and e₂=AB are two edges, not one duplicated set entry. A loop e₃=AA contributes two to deg(A).
Adjacency matrix
M_ij
For a finite loop-free undirected multigraph with fixed vertex order, M_ij is the number of edges between vertices i and j. The diagonal is zero and M is symmetric.
For a simple graph entries are 0 or 1. A directed graph uses a row-to-column direction and need not give a symmetric matrix. Loop-diagonal conventions must be stated separately.
Separate glossary example
Two vertices (A,B) joined by two parallel edges have M=[[0,2],[2,0]].
Matrix powers count walks
(M²)_ij=∑_k M_ik M_kj
For the adjacency matrix of a finite simple graph, (M²)_ij counts walks of length two from i to j, summed over possible intermediate vertices k.
These are walks, not necessarily paths: returning to a previous vertex is allowed. More generally (M^r)_ij counts length-r walks for nonnegative integer r; M⁰ is the identity matrix.
Separate glossary example
In the path 1—2—3, (M²)_13=1 from 1—2—3, and (M²)_11=1 from 1—2—1.
Permutation matrix and relabelling
M_H=PᵀM_GP
For a vertex bijection f from G to H, put P_uv=1 when f(u)=v and 0 otherwise, with rows in G order and columns in H order. For the same adjacency convention, M_H=PᵀM_GP expresses preserved adjacency.
Pᵀ swaps P’s row and column indices. Right multiplication reorders columns and left multiplication by Pᵀ reorders rows. Reversing the convention for P changes the displayed identity; the matrix does not name an edge bijection.
Separate glossary example
If G order is (1,2,3), H order is (p,q,r), and f(1)=r,f(2)=p,f(3)=q, then P=[[0,0,1],[1,0,0],[0,1,0]].
Worked example
Graph G has vertex order (A,B,C,D) and edges e1=AB, e2=AB, e3=BC, e4=CD, e5=DA. Graph H has vertex order (w,x,y,z) and edges h1=wz, h2=xy, h3=wy, h4=xz, h5=wy. Use f(A)=y, f(B)=w, f(C)=z, f(D)=x. Construct a compatible edge bijection and both adjacency matrices. Form P with rows in G order, columns in H order, and P_uv=1 exactly when f(u)=v. Verify M_H=PᵀM_GP.
Your task
G has vertex order (1,2,3) and edges a1=12, a2=12, a3=23, a4=23, a5=13. H has vertex order (p,q,r) and edges b1=pq, b2=pr, b3=qr, b4=pr, b5=pq. Take f(1)=r, f(2)=p, f(3)=q. Give an endpoint-preserving edge bijection. Construct M_G, M_H, and P using rows (1,2,3), columns (p,q,r), with P_uv=1 iff f(u)=v. Verify M_H=PᵀM_GP. How many edge bijections are compatible with this fixed f? Explain your count.
Saved in this browser; not automatically graded.
Review your written reasoning
- I used each target vertex and each target edge exactly once.
- I preserved endpoints and the multiplicity of every vertex pair.
- I wrote the vertex order and counted parallel edges in adjacency entries.
- My orientation of P agrees with the matrix identity I checked.
- I justified four compatible edge bijections, without rejecting equivalent swaps of parallel edges.