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