blog/graphs/index.html (view raw)
1<!DOCTYPE html>
2<html>
3<head>
4<meta charset="utf-8" />
5<meta name="viewport" content="width=device-width, initial-scale=1" />
6<title>Graphs</title>
7<link rel="stylesheet" href="../css/style.css">
8</head>
9<body>
10<main>
11<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
12<div class="date-created-modified">2017-06-02</div>
13<noscript>There are a few things which won't render unless you enable
14JavaScript. No tracking, I promise!</noscript>
15<h1 class="title" id="graphs"><a class="anchor" href="#graphs">ΒΆ</a>Graphs</h1>
16<blockquote>
17<p>Don't know English? <a href="spanish.html">Read the Spanish version instead</a>.</p>
18</blockquote>
19<p>Let's imagine we have 5 bus stations, which we'll denote by \(s_i\):</p>
20<p>(\begin{bmatrix}
21& s_1 & s_2 & s_3 & s_4 & s_5 \
22s_1 & & V & & & \
23s_2 & V & & & & V \
24s_3 & & & & V & \
25s_4 & & V & V & & \
26s_5 & V & & & V &
27\end{bmatrix})</p>
28<p>This is known as a <i>"table of direct interconnections"</i>.</p>
29 <p>The \(V\) represent connected paths. For instance, on the first
30 row starting at \(s_1\), reaching the \(V\),
31 allows us to turn up to get to \(s_2\).</p>
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<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<p>Let's now represent its adjacency matrix called A which represents the
43 same table, but uses <mark>1</mark> instead </mark>V</mark> to represent
44 a connection:</p>
45<p>(\begin{bmatrix}
460 & 1 & 0 & 0 & 0 \
471 & 0 & 0 & 0 & 1 \
480 & 0 & 0 & 1 & 0 \
490 & 1 & 1 & 0 & 0 \
501 & 0 & 0 & 1 & 0
51\end{bmatrix})</p>
52<p>This way we can see how the \(a_{2,1}\) element represents the
53 connection \(s_2 \rightarrow s_1\), and the \(a_{5,1}\) element the
54 \(s_5 \rightarrow s_1\) connection, etc.</p>
55<p>In general, \(a_{i,j}\) represents a connection from
56 \(s_i \rightarrow s_j\)as long as \(a_{i,j}\geq 1\).</p>
57<p>Working with matrices allows us to have a computable representation of
58 any graph, which is very useful.</p>
59<hr />
60<p>Graphs have a lot of interesting properties besides being representable
61 by a computer. What would happen if, for instance, we calculated
62 \(A^2\)? We obtain the following matrix:</p>
63<p>(\begin{bmatrix}
641 & 0 & 0 & 0 & 1 \
651 & 1 & 0 & 1 & 0 \
660 & 1 & 1 & 0 & 0 \
671 & 0 & 0 & 1 & 1 \
680 & 2 & 1 & 0 & 0
69\end{bmatrix})</p>
70<p>We can interpret this as the paths of order <b>two</b>.</p>
71 <p>But what does the element \(a_{5,2}=2\) represent? It indicates
72 the amount of possible ways to go from \(s_5 \rightarrow s_i \rightarrow s_2\).</p>
73<p>One can manually multiply the involved row and column to determine which
74 element is the one we need to pass through, this way we have the row
75 \([1 0 0 1 0]\) and the column \([1 0 0 1 0]\) (on
76 vertical). The elements \(s_i\geq 1\) are \(s_1\) and
77 \(s_4\). This is, we can go from \(s_5\) to
78 \(s_2\) via \(s_5 \rightarrow s_1 \rightarrow s_2\) or via
79 \(s_5 \rightarrow s_4 \rightarrow s_2\):</p>
80 <img src="example2.svg" />
81<p>It's important to note that graphs to not consider self-connections, this
82 is, \(s_i \rightarrow s_i\) is not allowed; neither we work with multigraphs
83 here (those which allow multiple connections, for instance, an arbitrary
84 number \(n\) of times).</p>
85<p>(\begin{bmatrix}
861 & 1 & 0 & 1 & 0 \
871 & 2 & \textbf{1} & 0 & 1 \
881 & 0 & 0 & 1 & 1 \
891 & 2 & 1 & 1 & 0 \
902 & 0 & 0 & 1 & 2
91\end{bmatrix})</p>
92<p>We can see how the first \(1\) just appeared on the element
93 \(a_{2,3}\), which means that the shortest path to it is at least
94 of order three.</mark>
95<hr />
96<p>A graph is said to be <b>strongly connected</b> as long as there is a
97 way to reach <i>all</i> its elements.</p>
98<p>We can see all the available paths until now by simply adding up all the
99 direct and indirect ways to reach a node, so for now, we can add
100 \(A+A^2+A^3\) in such a way that:</p>
101<p>(\begin{bmatrix}
1022 & 2 & 0 & 1 & 1 \
1033 & 3 & 1 & 1 & 3 \
1041 & 1 & 1 & 2 & 1 \
1052 & 3 & 2 & 2 & 1 \
1063 & 2 & 1 & 2 & 2
107\end{bmatrix})</p>
108<p>There isn't a connection between \(s_1\) and \(s_3\) yet.
109 If we were to calculate \(A^4\):</p>
110<p>(\begin{bmatrix}
1111 & 2 & 1 & & \
112& & & & \
113& & & & \
114& & & & \
115& & & &<br />
116\end{bmatrix})</p>
117<p>We don't need to calculate anymore. We now know that the graph is
118 strongly connected!</p>
119<hr />
120<p>Congratulations! You've completed this tiny introduction to graphs.
121 Now you can play around with them and design your own connections.</p>
122<p>Hold the left mouse button on the above area and drag it down to create
123 a new node, or drag a node to this area to delete it.</p>
124<p>To create new connections, hold the right mouse button on the node you
125 want to start with, and drag it to the node you want it to be connected to.</p>
126<p>To delete the connections coming from a specific node, middle click it.</p>
127<table><tr><td style="width:100%;">
128 <button onclick="resetConnections()">Reset connections</button>
129 <button onclick="clearNodes()">Clear all the nodes</button>
130 <br />
131 <br />
132 <label for="matrixOrder">Show matrix of order:</label>
133 <input id="matrixOrder" type="number" min="1" max="5"
134 value="1" oninput="updateOrder()">
135 <br />
136 <label for="matrixAccum">Show accumulated matrix</label>
137 <input id="matrixAccum" type="checkbox" onchange="updateOrder()">
138 <br />
139 <br />
140 <div class="matrix">
141 <table id="matrixTable"></table>
142 </div>
143 </td><td>
144 <canvas id="canvas" width="400" height="400" oncontextmenu="return false;">
145 Looks like your browser won't let you see this fancy example :(
146 </canvas>
147 <br />
148 </td></tr></table>
149<script src="tinyparser.js"></script>
150<script src="enhancements.js"></script>
151<script src="graphs.js"></script>
152</main>
153</body>
154</html>
155