Graphs | Lonami's Blog

submited by

Style Pass

2021-06-09 19:30:08

There are a few things which won't render unless you enable JavaScript. No tracking, I promise!Don't know English? Read the Spanish version instead.

Let's imagine we have 5 bus stations, which we'll denote by ((s_i)):' s_1 ' s_2 ' s_3 ' s_4 ' s_5 \\ s_1 ' ' V ' ' ' \\ s_2 ' V ' ' ' ' V \\ s_3 ' ' ' ' V ' \\ s_4 ' ' V ' V ' ' \\ s_5 ' V ' ' ' V '

This is known as a "table of direct interconnections". The ((V)) represent connected paths. For instance, on the first row starting at ((s_1)), reaching the ((V)), allows us to turn up to get to ((s_2)).

This type of graph is called, well, a graph, and it's a directed graph (or digraph), since the direction on which the arrows go does matter. It's made up of vertices, joined together by edges (also known as lines or directed arcs).

One can walk from a node to another through different paths. For example, ((s_4 $rightarrow s_2 $rightarrow s_5)) is an indirect path of order two, because we must use two edges to go from ((s_4)) to ((s_5)).