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