content/blog/graphs/spanish.md.bak (view raw)
1<!DOCTYPE html>
2<html>
3<head>
4 <link href="https://fonts.googleapis.com/css?family=Montserrat|Ubuntu"
5 rel="stylesheet">
6 <link href="css/graphs.css" rel="stylesheet">
7</head>
8<body>
9<main>
10 <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
11 <noscript>Hay cosas que no se van a ver a menos que actives JavaScript.
12 No <i>tracking</i>, ¡lo prometo!</noscript>
13
14 <h1>Grafos</h1>
15 <p class="right"><em>Escrito por
16 <a href="https://lonami.dev" >Imanol H.</a><br />
17 el 02-06-2017. Última revisión el 02-06-2017
18 </em></p>
19
20 <p>Imaginemos 5 estaciones de autobús, que denotaremos por \(s_i\):</p>
21 \(\begin{bmatrix}
22 & s_1 & s_2 & s_3 & s_4 & s_5 \\
23 s_1 & & V & & & \\
24 s_2 & V & & & & V \\
25 s_3 & & & & V & \\
26 s_4 & & V & V & & \\
27 s_5 & V & & & V &
28 \end{bmatrix}\)
29 <p>Esto se conoce como <i>"cuadro de interconexiones directas"</i>.</p>
30 <p>Las \(V\) representan caminos conectados. Por ejemplo, en la
31 primera fila partiendo de \(s_1\), llegando hasta la \(V\),
32 se nos permite girar hacia arriba para llegar a \(s_2\).</p>
33
34 <p>Podemos ver esta misma tabla representada de una manera más gráfica:</p>
35 <img src="example1.svg" />
36 <p>Este tipo de gráfica es un grafo, y además dirigido (o <i>digrafo</i>),
37 ya que el sentido en el que van las flechas sí importa. Está compuesto
38 por vértices, unidos entre si por ejes (también llamados aristas o
39 <b>arcos</b> dirigidos).</p>
40
41 <p>Se puede ir de un nodo otro mediante distintos <b>caminos</b> o
42 <i>tours</i>. Por ejemplo, \(s_4 \rightarrow s_2 \rightarrow s_5\) es un camino
43 indirecto de <b>orden</b> dos, porque debemos usar dos aristas para ir
44 de \(s_4\) a \(s_5\).</p>
45
46 <p>Pasemos ahora a representar la matriz de <b>adyacencia</b> llamada A, que
47 representa el mismo cuadro, pero usa \(1\) en vez de \(V\)
48 para representar una conexión:</p>
49
50 \(\begin{bmatrix}
51 0 & 1 & 0 & 0 & 0 \\
52 1 & 0 & 0 & 0 & 1 \\
53 0 & 0 & 0 & 1 & 0 \\
54 0 & 1 & 1 & 0 & 0 \\
55 1 & 0 & 0 & 1 & 0
56 \end{bmatrix}\)
57
58 <p>Así podemos ver como el elemento \(a_{2,1}\) representa la
59 conexión \(s_2 \rightarrow s_1\), y el \(a_{5,1}\) la
60 \(s_5 \rightarrow s_1\), etc.</p>
61
62 <p>En general, \(a_ij\) representa una conexión de
63 \(s_i \rightarrow s_j\) siempre que \(a_{i,j} \geq 1\).</p>
64
65 <p>Trabajar con matrices nos permite tener una representación computable
66 de un grafo cualquiera, lo cual es realmente útil.</p>
67
68 <hr />
69
70 <p>Los grafos tienen muchas más propiedades interesantes a parte de ser
71 representables computacionalmente. ¿Qué ocurre si, por ejemplo, hallamos
72 \(A^2\)? Resulta la siguiente matriz:</p>
73
74 \(\begin{bmatrix}
75 1 & 0 & 0 & 0 & 1 \\
76 1 & 1 & 0 & 1 & 0 \\
77 0 & 1 & 1 & 0 & 0 \\
78 1 & 0 & 0 & 1 & 1 \\
79 0 & 2 & 1 & 0 & 0
80 \end{bmatrix}\)
81
82 <p>Podemos interpretar esta matriz como los caminos de orden <b>dos</b>.</p>
83 <p>¿Pero qué representa el elemento \(a_{5,2} = 2\)? Indica que hay
84 dos posibles caminos para ir de \(s_5 \rightarrow s_i \rightarrow s_2\)</p>
85
86 <p>Es posible realizar la multiplicación de la fila y columna implicadas
87 para ver qué elemento es el que hay que atravesar, así se tiene la fila
88 \([1, 0, 0, 1, 0]\) y la columna \([1, 0, 0, 1, 0]\) (en
89 vertical). Los elementos \(s_1 \geq 1\) son \(s_1\) y
90 \(s_4\). Es decir, se puede ir de \(s_5\) a
91 \(s_2\) o bien mediante \(s_5 \rightarrow s_1 \rightarrow s_2\) ó bien
92 \(s_5 \rightarrow s_4 \rightarrow s_2\):</p>
93 <img src="example2.svg" />
94
95 <p>Es importante notar que en los gráfos no se consideran lazos, es decir,
96 \(s_i \rightarrow s_i\) no está permitido; ni tampoco se trabaja con
97 multigrafos (que permiten muchas conexiones, por ejemplo, de un número
98 arbitrario \(n\) de veces.</p>
99
100 <p>Terminemos con \(A^3\):</p>
101 \(\begin{bmatrix}
102 1 & 1 & 0 & 1 & 0 \\
103 1 & 2 & \textbf{1} & 0 & 1 \\
104 1 & 0 & 0 & 1 & 1 \\
105 1 & 2 & 1 & 1 & 0 \\
106 2 & 0 & 0 & 1 & 2
107 \end{bmatrix}\)
108
109 <p>Podemos ver como ha aparecido el primer \(1\) en
110 \(a_{2,3}\), lo que representa que el camino más corto es de al menos
111 de orden tres.
112
113 <hr />
114
115 <p>Un grafo es <b>fuertemente conexo</b> siempre que se pueda encontrar una
116 conexión para <i>todos</i> los elementos.</p>
117
118 <p>Para ver todos los caminos posibles hasta ahora, basta con sumar las
119 formas directas más las formas indirectas, por lo que hasta ahora podemos
120 sumar \(A + A^2 + A^3\) tal que:</p>
121
122 \(\begin{bmatrix}
123 2 & 2 & 0 & 1 & 1 \\
124 3 & 3 & 1 & 1 & 3 \\
125 1 & 1 & 1 & 2 & 1 \\
126 2 & 3 & 2 & 2 & 1 \\
127 3 & 2 & 1 & 2 & 2
128 \end{bmatrix}\)
129
130 <p>Sigue sin haber una conexión entre \(s_1\) y \(s_3\).
131 Calculando \(A^4\):</p>
132
133 \(\begin{bmatrix}
134 1 & 2 & 1 & & \\
135 & & & & \\
136 & & & & \\
137 & & & & \\
138 & & & &
139 \end{bmatrix}\)
140
141 <p>No hace falta seguir calculando, ya tenemos un grafo totalmente conexo.
142 </p>
143
144 <hr />
145
146 <p>¡Felicidades! Has completado esta pequeña introducción a los gráficos.
147 Ahora puedes jugar tú y diseñar tus propias conexiones.</p>
148
149 <p>Mantén pulsado el botón izquierdo del ratón en el área de arriba y
150 arrastra hacia abajo para crear un nuevo nodo, o arrastra un nodo a este
151 área para eliminarlo.</p>
152
153 <p>Para crear nuevas conexiones, mantén pulsado el botón derecho del ratón
154 en el nodo del que quiera partir, y arrástralo hasta el nodo con el que
155 lo quieras conectar.</p>
156
157 <p>Para eliminar las conexiones que salen de un nodo en concreto, haz clic
158 con el botón central del ratón en el nodo que quieras.</p>
159
160 <table><tr><td style="width:100%;">
161 <button onclick="resetConnections()">Reiniciar conexiones</button>
162 <button onclick="clearNodes()">Limpiar todos los nodos</button>
163 <br />
164 <br />
165 <label for="matrixOrder">Mostrar matriz de orden:</label>
166 <input id="matrixOrder" type="number" min="1" max="5"
167 value="1" oninput="updateOrder()">
168 <br />
169 <label for="matrixAccum">Mostrar matriz acumulada</label>
170 <input id="matrixAccum" type="checkbox" onchange="updateOrder()">
171 <br />
172 <br />
173 <div class="matrix">
174 <table id="matrixTable"></table>
175 </div>
176 </td><td>
177 <canvas id="canvas" width="400" height="400" oncontextmenu="return false;">
178 Parece que tu navegador no vas a poder probar el ejemplo en tu navegador :(
179 </canvas>
180 <br />
181 </td></tr></table>
182</main>
183
184<script src="tinyparser.js"></script>
185<script src="enhancements.js"></script>
186<script src="graphs.js"></script>
187</body>
188</html>