Maths of computer science

2021-06-20
2 min read

Seven Bridges of Königsberg

Question: Is there any route for the following tour such that every bridge is crossed exact once?

drawing

Solution: Reduce the problem to graph by converting landmass to vertices and bridges to edges, we obtain the following undirected graph. In order for every edge to be crossed only once, we can only enter a vertex by one bridge and leave the vertex with another bridge.

drawing

That means, every vertex must belong to an even number of edges. This is clearly not the case, for example green belongs to 3 edges, blue belongs to 5 edges, etc.

Finding paths of length $K$ in a graph

Question: Considering a loop-free graph, how many paths with length of exact $K$ are there in this graph?

Solution sketch: Converting the graph to adjacency matrix. An adjacency matrix is a $n \times n$ matrix $A$ where $a_{ij} = 1$ if there is a path from vertex $i$ to vertex $j$, else $a_{ij} = 0$.

drawing

Claim: The matrix $A^{K}$ is non-zero at $A^{K}_{ij}$ if there is a path of length $K$ from $i$ to $j$.

Proof by induction:

At the induction base, the matrix $A^1 = A$ is non-zero at $a_{ij}$ if and only if there an edge from $i$ to $j$. This edge is by definition a path of length 1.

For the induction step, $A^K$ indicates there exists path from $i$ to $j$ of length $K$. In the matrix-matrix-product, row $i$ of $A^K$ is multiplied with column $j$ of $A$. Row $i$ of $A^k$ indicates all paths of length $K$ from vertex $i$ to any vertex $k$.
Column $j$ of $A$ indicates all vertices for any vertex $k$ to $j$. $A^{k + 1}$ is non-zero at $A^{k + 1}_{ij}$ if there is a path with of length $K$ from $i$ to $k$ and a vertex from $k$ to $j$, in other words, a path from $i$ to $j$ with length $k + 1$.