1+++
  2title = "Graphs"
  3date = 2017-06-02
  4updated = 2017-06-02
  5+++
  6
  7<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
  8<noscript>There are a few things which won't render unless you enable
  9JavaScript. No tracking, I promise!</noscript>
 10
 11> Don't know English? [Read the Spanish version instead](spanish.html).
 12
 13  <p>Let's imagine we have 5 bus stations, which we'll denote by \(s_i\):</p>
 14
 15  \(\begin{bmatrix}
 16  & s_1 & s_2 & s_3 & s_4 & s_5 \\
 17  s_1   &   & V &   &   &       \\
 18  s_2   & V &   &   &   & V     \\
 19  s_3   &   &   &   & V &       \\
 20  s_4   &   & V & V &   &       \\
 21  s_5   & V &   &   & V &
 22 \end{bmatrix}\)
 23
 24  <p>This is known as a <i>"table of direct interconnections"</i>.</p>
 25  <p>The \(V\) represent connected paths. For instance, on the first
 26  row starting at \(s_1\), reaching the \(V\),
 27  allows us to turn up to get to \(s_2\).</p>
 28
 29  <p>We can see the above table represented in a more graphical way:</p>
 30  <img src="example1.svg" />
 31  <p>This type of graph is called, well, a <i>graph</i>, and it's a directed
 32  graph (or <i>digraph</i>), since the direction on which the arrows go does
 33  matter. It's made up of vertices, joined together by edges (also known as
 34  lines or directed <b>arcs</b>).</p>
 35
 36  <p>One can walk from a node to another through different <b>paths</b>. For
 37  example, \(s_4 \rightarrow s_2 \rightarrow s_5\) is an indirect path of <b>order</b>
 38  two, because we must use two edges to go from \(s_4\) to
 39  \(s_5\).</p>
 40
 41  <p>Let's now represent its adjacency matrix called A which represents the
 42  same table, but uses <mark>1</mark> instead </mark>V</mark> to represent
 43  a connection:</p>
 44
 45  \(\begin{bmatrix}
 46    0 & 1 & 0 & 0 & 0 \\
 47    1 & 0 & 0 & 0 & 1 \\
 48    0 & 0 & 0 & 1 & 0 \\
 49    0 & 1 & 1 & 0 & 0 \\
 50    1 & 0 & 0 & 1 & 0
 51\end{bmatrix}\)
 52
 53  <p>This way we can see how the \(a_{2,1}\) element represents the
 54  connection \(s_2 \rightarrow s_1\), and the \(a_{5,1}\) element the
 55  \(s_5 \rightarrow s_1\) connection, etc.</p>
 56
 57  <p>In general, \(a_{i,j}\) represents a connection from
 58    \(s_i \rightarrow s_j\)as long as \(a_{i,j}\geq 1\).</p>
 59
 60  <p>Working with matrices allows us to have a computable representation of
 61  any graph, which is very useful.</p>
 62
 63  <hr />
 64
 65  <p>Graphs have a lot of interesting properties besides being representable
 66  by a computer. What would happen if, for instance, we calculated
 67  \(A^2\)? We obtain the following matrix:</p>
 68
 69  \(\begin{bmatrix}
 70  1 & 0 & 0 & 0 & 1 \\
 71  1 & 1 & 0 & 1 & 0 \\
 72  0 & 1 & 1 & 0 & 0 \\
 73  1 & 0 & 0 & 1 & 1 \\
 74  0 & 2 & 1 & 0 & 0
 75  \end{bmatrix}\)
 76
 77  <p>We can interpret this as the paths of order <b>two</b>.</p>
 78  <p>But what does the element \(a_{5,2}=2\) represent? It indicates
 79  the amount of possible ways to go from  \(s_5 \rightarrow s_i \rightarrow s_2\).</p>
 80
 81  <p>One can manually multiply the involved row and column to determine which
 82  element is the one we need to pass through, this way we have the row
 83  \([1 0 0 1 0]\) and the column \([1 0 0 1 0]\) (on
 84  vertical). The elements \(s_i\geq 1\) are \(s_1\) and
 85  \(s_4\). This is, we can go from \(s_5\) to
 86  \(s_2\) via \(s_5 \rightarrow s_1 \rightarrow s_2\) or via
 87  \(s_5 \rightarrow s_4 \rightarrow s_2\):</p>
 88  <img src="example2.svg" />
 89
 90  <p>It's important to note that graphs to not consider self-connections, this
 91  is, \(s_i \rightarrow s_i\) is not allowed; neither we work with multigraphs
 92  here (those which allow multiple connections, for instance, an arbitrary
 93  number \(n\) of times).</p>
 94
 95  \(\begin{bmatrix}
 96  1 & 1 & 0          & 1 & 0 \\
 97  1 & 2 & \textbf{1} & 0 & 1 \\
 98  1 & 0 & 0          & 1 & 1 \\
 99  1 & 2 & 1          & 1 & 0 \\
100  2 & 0 & 0          & 1 & 2
101  \end{bmatrix}\)
102
103  <p>We can see how the first \(1\) just appeared on the element
104    \(a_{2,3}\), which means that the shortest path to it is at least
105  of order three.</mark>
106
107  <hr />
108
109  <p>A graph is said to be <b>strongly connected</b> as long as there is a
110  way to reach <i>all</i> its elements.</p>
111
112  <p>We can see all the available paths until now by simply adding up all the
113  direct and indirect ways to reach a node, so for now, we can add
114  \(A+A^2+A^3\) in such a way that:</p>
115
116  \(\begin{bmatrix}
117  2 & 2 & 0 & 1 & 1 \\
118  3 & 3 & 1 & 1 & 3 \\
119  1 & 1 & 1 & 2 & 1 \\
120  2 & 3 & 2 & 2 & 1 \\
121  3 & 2 & 1 & 2 & 2
122  \end{bmatrix}\)
123
124  <p>There isn't a connection between \(s_1\) and \(s_3\) yet.
125  If we were to calculate \(A^4\):</p>
126
127  \(\begin{bmatrix}
128  1 & 2 & 1 &   &   \\
129    &   &   &   &   \\
130    &   &   &   &   \\
131    &   &   &   &   \\
132    &   &   &   &
133  \end{bmatrix}\)
134
135  <p>We don't need to calculate anymore. We now know that the graph is
136  strongly connected!</p>
137
138  <hr />
139
140  <p>Congratulations! You've completed this tiny introduction to graphs.
141  Now you can play around with them and design your own connections.</p>
142
143  <p>Hold the left mouse button on the above area and drag it down to create
144  a new node, or drag a node to this area to delete it.</p>
145
146  <p>To create new connections, hold the right mouse button on the node you
147  want to start with, and drag it to the node you want it to be connected to.</p>
148
149  <p>To delete the connections coming from a specific node, middle click it.</p>
150
151  <table><tr><td style="width:100%;">
152    <button onclick="resetConnections()">Reset connections</button>
153    <button onclick="clearNodes()">Clear all the nodes</button>
154    <br />
155    <br />
156    <label for="matrixOrder">Show matrix of order:</label>
157    <input id="matrixOrder" type="number" min="1" max="5"
158                            value="1" oninput="updateOrder()">
159    <br />
160    <label for="matrixAccum">Show accumulated matrix</label>
161    <input id="matrixAccum" type="checkbox" onchange="updateOrder()">
162    <br />
163    <br />
164    <div class="matrix">
165      <table id="matrixTable"></table>
166    </div>
167  </td><td>
168    <canvas id="canvas" width="400" height="400" oncontextmenu="return false;">
169    Looks like your browser won't let you see this fancy example :(
170    </canvas>
171    <br />
172  </td></tr></table>
173
174<script src="tinyparser.js"></script>
175<script src="enhancements.js"></script>
176<script src="graphs.js"></script>