x

1 files changed, 1646 insertions, 0 deletions

diff --git a/graf/n4.lyx b/graf/n4.lyx
new file mode 100644
index 0000000..ed819e4
--- /dev/null
+++ b/graf/n4.lyx
@@ -0,0 +1,1646 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Un 
+\series bold
+bosque
+\series default
+ o grafo 
+\series bold
+acíclico
+\series default
+ es un grafo sin ciclos.
+ Un 
+\series bold
+árbol
+\series default
+ es un bosque conexo.
+ Un 
+\series bold
+árbol generador
+\series default
+ de un grafo es un subgrafo generador que es un árbol.
+\end_layout
+
+\begin_layout Standard
+Como 
+\series bold
+teorema
+\series default
+, un grafo 
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ no vacío es un árbol si y sólo si entre cada 
+\begin_inset Formula $u,v\in V$
+\end_inset
+
+ distintos existe un único camino, si y sólo si es conexo con 
+\begin_inset Formula $|E|=|V|-1$
+\end_inset
+
+, si y sólo si es acíclico con 
+\begin_inset Formula $|E|=|V|-1$
+\end_inset
+
+, si y sólo si es conexo minimal (todos los ejes son de corte), si y solo
+ si es acíclico maximal (añadir un eje forma un ciclo), en cuyo caso el
+ ciclo formado al añadir el eje es único.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $1\implies2]$
+\end_inset
+
+ El camino existe por conexión.
+ Supongamos que existen 
+\begin_inset Formula $u,v\in V$
+\end_inset
+
+ distintos con dos caminos de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+ distintos, 
+\begin_inset Formula $uu_{1}\cdots u_{p-1}v$
+\end_inset
+
+ y 
+\begin_inset Formula $uv_{1}\cdots v_{q-1}v$
+\end_inset
+
+.
+ Sean 
+\begin_inset Formula $u_{0}:=v_{0}:=u$
+\end_inset
+
+, 
+\begin_inset Formula $u_{p}:=u_{q}:=v$
+\end_inset
+
+ e 
+\begin_inset Formula $i\in\{1,\dots,\min\{p,q\}\}$
+\end_inset
+
+ mínimo con 
+\begin_inset Formula $u_{i}\neq v_{i}$
+\end_inset
+
+, el paseo 
+\begin_inset Formula $u_{i}\cdots u_{p-1}vv_{q-1}\cdots v_{i}$
+\end_inset
+
+, que no contiene a 
+\begin_inset Formula $u_{i-1}=v_{i-1}$
+\end_inset
+
+, contiene un camino no trivial 
+\begin_inset Formula $P$
+\end_inset
+
+ de 
+\begin_inset Formula $u_{i}$
+\end_inset
+
+ a 
+\begin_inset Formula $v_{i}$
+\end_inset
+
+, y entonces 
+\begin_inset Formula $(u_{i-1},u_{i})P(v_{i},v_{i-1})$
+\end_inset
+
+ es un ciclo y 
+\begin_inset Formula $G$
+\end_inset
+
+ no es un árbol.
+\begin_inset Formula $\#$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $2\implies3]$
+\end_inset
+
+ Claramente es conexo.
+ Si 
+\begin_inset Formula $|V|=1$
+\end_inset
+
+, debe ser 
+\begin_inset Formula $|E|=0$
+\end_inset
+
+.
+ Supuesto esto probado cuando 
+\begin_inset Formula $|V|=n\geq1$
+\end_inset
+
+, para 
+\begin_inset Formula $|V|=n+1$
+\end_inset
+
+, sea 
+\begin_inset Formula $e:=(u,v)\in E$
+\end_inset
+
+, 
+\begin_inset Formula $e$
+\end_inset
+
+ es el único camino de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+ y por tanto 
+\begin_inset Formula $G-e$
+\end_inset
+
+ es disconexo con dos componentes conexas de órdenes 
+\begin_inset Formula $n_{1},n_{2}\in\{1,\dots,n\}$
+\end_inset
+
+.
+ Entre dos vértices distintos de la misma componente hay un único camino,
+ luego por la hipótesis de inducción estas tienen 
+\begin_inset Formula $n_{1}-1$
+\end_inset
+
+ y 
+\begin_inset Formula $n_{2}-1$
+\end_inset
+
+ ejes respectivamente y 
+\begin_inset Formula $|E|=|E\setminus\{e\}|+1=n_{1}-1+n_{2}-1+1=n-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $3\implies4]$
+\end_inset
+
+ Si 
+\begin_inset Formula $G$
+\end_inset
+
+ tuviera un ciclo, sea 
+\begin_inset Formula $e$
+\end_inset
+
+ un eje en un ciclo, 
+\begin_inset Formula $G-e=:(V,E')$
+\end_inset
+
+ sería conexo con 
+\begin_inset Formula $|E'|=|E|-1=|V|-1$
+\end_inset
+
+, pero la conexión implica 
+\begin_inset Formula $|E'|\geq|V|-1\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $4\implies3]$
+\end_inset
+
+ Si 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene componentes conexas 
+\begin_inset Formula $G_{1},\dots,G_{q}$
+\end_inset
+
+ y 
+\begin_inset Formula $G_{i}$
+\end_inset
+
+ tiene orden 
+\begin_inset Formula $n_{i}$
+\end_inset
+
+ y tamaño 
+\begin_inset Formula $m_{i}$
+\end_inset
+
+, como cada 
+\begin_inset Formula $G_{i}$
+\end_inset
+
+ es conexa y acíclica, usando (
+\begin_inset Formula $1\implies3$
+\end_inset
+
+) es 
+\begin_inset Formula $m_{i}=n_{i}-1$
+\end_inset
+
+, luego 
+\begin_inset Formula $m=\sum_{i=1}^{q}m_{i}=\sum_{i=1}^{q}(n_{i}-1)=n-q$
+\end_inset
+
+, y despejando 
+\begin_inset Formula $q=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $3\implies5]$
+\end_inset
+
+ Dado un eje 
+\begin_inset Formula $e$
+\end_inset
+
+, 
+\begin_inset Formula $G-e=:(V,E')$
+\end_inset
+
+ cumple 
+\begin_inset Formula $|E'|=|E|-1=|V|-2$
+\end_inset
+
+, luego 
+\begin_inset Formula $G-e$
+\end_inset
+
+ es disconexo y 
+\begin_inset Formula $e$
+\end_inset
+
+ es un eje de corte.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $5\implies6]$
+\end_inset
+
+ Si hubiera un ciclo, al quitar un eje del ciclo el grafo seguiría siendo
+ conexo, luego el eje no sería de corte.
+\begin_inset Formula $\#$
+\end_inset
+
+ Sean ahora 
+\begin_inset Formula $u,v\in V$
+\end_inset
+
+ distintos no adyacentes y 
+\begin_inset Formula $P$
+\end_inset
+
+ una cadena de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+ en 
+\begin_inset Formula $G$
+\end_inset
+
+, que tendrá longitud al menos 2, añadiendo 
+\begin_inset Formula $(u,v)$
+\end_inset
+
+ a 
+\begin_inset Formula $E$
+\end_inset
+
+ tendríamos el ciclo 
+\begin_inset Formula $P(v,u)$
+\end_inset
+
+.
+ Claramente todo ciclo tiene que contener a 
+\begin_inset Formula $(u,v)$
+\end_inset
+
+, pero como 
+\begin_inset Formula $P$
+\end_inset
+
+ es único, el ciclo es único.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $6\implies1]$
+\end_inset
+
+ Para ver que 
+\begin_inset Formula $G$
+\end_inset
+
+ es conexo, sean 
+\begin_inset Formula $u,v\in V$
+\end_inset
+
+, si 
+\begin_inset Formula $u$
+\end_inset
+
+ y 
+\begin_inset Formula $v$
+\end_inset
+
+ son iguales o adyacentes no hay que hacer nada, y en otro caso, sea 
+\begin_inset Formula $P$
+\end_inset
+
+ el ciclo que se forma al añadir 
+\begin_inset Formula $e:=(u,v)$
+\end_inset
+
+ a 
+\begin_inset Formula $E$
+\end_inset
+
+, que debe contener a 
+\begin_inset Formula $e$
+\end_inset
+
+ y podemos suponer de la forma 
+\begin_inset Formula $ee_{1}\cdots e_{k}$
+\end_inset
+
+, 
+\begin_inset Formula $e_{k}\cdots e_{1}$
+\end_inset
+
+ es un camino de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Todo árbol de orden al menos 2 tiene dos hojas.
+ En efecto, sea 
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ un árbol de orden 
+\begin_inset Formula $n\geq2$
+\end_inset
+
+ y tamaño 
+\begin_inset Formula $m=n-1$
+\end_inset
+
+ con 
+\begin_inset Formula $h$
+\end_inset
+
+ hojas, 
+\begin_inset Formula 
+\[
+2n-2=2(n-1)=\sum_{v\in V}o(v)=\sum_{v\text{ hoja}}1+\sum_{v\text{ no hoja}}o(v)\geq h+2(n-h)=2n-h,
+\]
+
+\end_inset
+
+y despejando es 
+\begin_inset Formula $h\geq2$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+árbol con raíz
+\series default
+ o 
+\series bold
+enraizado
+\series default
+ es un par 
+\begin_inset Formula $(T,r)$
+\end_inset
+
+ donde 
+\begin_inset Formula $T=:(V,E)$
+\end_inset
+
+ es un árbol y 
+\begin_inset Formula $r\in V$
+\end_inset
+
+ es la 
+\series bold
+raíz
+\series default
+.
+ Entonces un 
+\series bold
+nudo
+\series default
+ es un nodo del árbol que distinto de la raíz que no es hoja.
+ Dados 
+\begin_inset Formula $u,v\in V$
+\end_inset
+
+ distintos, si el único camino de 
+\begin_inset Formula $v$
+\end_inset
+
+ a la raíz contiene a 
+\begin_inset Formula $u$
+\end_inset
+
+, 
+\begin_inset Formula $u$
+\end_inset
+
+ es 
+\series bold
+predecesor
+\series default
+ de 
+\begin_inset Formula $v$
+\end_inset
+
+ y 
+\begin_inset Formula $v$
+\end_inset
+
+ es 
+\series bold
+sucesor
+\series default
+ de 
+\begin_inset Formula $u$
+\end_inset
+
+.
+ El nodo 
+\series bold
+padre
+\series default
+ de un nodo es su único predecesor adyacente, y sus nodos 
+\series bold
+hijo
+\series default
+ son sus sucesores adyacentes.
+\end_layout
+
+\begin_layout Standard
+Dos nodos 
+\begin_inset Formula $u$
+\end_inset
+
+ y 
+\begin_inset Formula $v$
+\end_inset
+
+ son 
+\series bold
+comparables
+\series default
+ si son iguales o uno es sucesor de otro.
+ El 
+\series bold
+nivel
+\series default
+ de un nodo es la longitud del único camino del nodo a la raíz, y la 
+\series bold
+altura
+\series default
+ del árbol es el nivel máximo de sus nodos.
+\end_layout
+
+\begin_layout Section
+Árboles binarios
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+árbol binario
+\series default
+ es un árbol con raíz en que todos los nodos tienen grado 1 o 3 excepto
+ la raíz, que tiene grado 2.
+ Propiedades: Sea 
+\begin_inset Formula $T$
+\end_inset
+
+ un árbol binario de orden 
+\begin_inset Formula $n$
+\end_inset
+
+:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $n$
+\end_inset
+
+ es impar y al menos 3.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Sea 
+\begin_inset Formula $T=:(V,E,r)$
+\end_inset
+
+, como 
+\begin_inset Formula $\sum_{v\in V}o(v)=2+\sum_{v\in V\setminus\{r\}}o(v)$
+\end_inset
+
+ es par y 
+\begin_inset Formula $o(v)$
+\end_inset
+
+ es impar para 
+\begin_inset Formula $v\in V\setminus\{r\}$
+\end_inset
+
+, 
+\begin_inset Formula $|V\setminus\{r\}|$
+\end_inset
+
+ es par y por tanto 
+\begin_inset Formula $n$
+\end_inset
+
+ es impar.
+ Para 
+\begin_inset Formula $n\geq3$
+\end_inset
+
+, como 
+\begin_inset Formula $o(r)=2$
+\end_inset
+
+, 
+\begin_inset Formula $2\leq|E|=n-1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $T$
+\end_inset
+
+ tiene 
+\begin_inset Formula $\frac{n+1}{2}$
+\end_inset
+
+ nodos hoja y 
+\begin_inset Formula $\frac{n-3}{2}$
+\end_inset
+
+ nudos.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Si 
+\begin_inset Formula $T$
+\end_inset
+
+ tiene 
+\begin_inset Formula $h$
+\end_inset
+
+ hojas, tiene 
+\begin_inset Formula $n-h-1$
+\end_inset
+
+ nudos y 
+\begin_inset Formula $2n-2=\sum_{v\in V}o(v)=2+h+3(n-h-1)=3n-2h-1$
+\end_inset
+
+, luego 
+\begin_inset Formula $2h=n+1$
+\end_inset
+
+, 
+\begin_inset Formula $h=\frac{n+1}{2}$
+\end_inset
+
+ y hay 
+\begin_inset Formula $n-h-1=n-\frac{n+1}{2}-1=\frac{n-3}{2}$
+\end_inset
+
+ nudos.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+La altura de 
+\begin_inset Formula $T$
+\end_inset
+
+ está entre 
+\begin_inset Formula $\lceil\lg(n+1)-1\rceil$
+\end_inset
+
+ y 
+\begin_inset Formula $\frac{n-1}{2}$
+\end_inset
+
+, y estos extremos son alcanzables.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\lg x:=\log_{2}x$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Todos los niveles hasta el 
+\begin_inset Formula $h$
+\end_inset
+
+ de un árbol de altura 
+\begin_inset Formula $h$
+\end_inset
+
+, salvo el nivel 0, tienen al menos 2 nodos, luego su orden mínimo es 
+\begin_inset Formula $2h+1$
+\end_inset
+
+, pero 
+\begin_inset Formula $n\geq2h+1\iff h\leq\frac{n-1}{2}$
+\end_inset
+
+.
+ Como 
+\begin_inset Formula $\frac{n-1}{2}\in\mathbb{Z}$
+\end_inset
+
+, la igualdad 
+\begin_inset Formula $h=\frac{n-1}{2}$
+\end_inset
+
+ se alcanza en 
+\begin_inset Formula $T':=(V',E')$
+\end_inset
+
+ dado por 
+\begin_inset Formula $V':=\{b_{0},a_{1},b_{1},\dots,a_{h},b_{h}\}$
+\end_inset
+
+ y 
+\begin_inset Formula $E':=\{(a_{k},b_{k-1}),(b_{k},b_{k-1})\}_{k\in\{1,\dots,h\}}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Como en cada nivel puede haber como máximo el doble de nodos que en el nivel
+ anterior, en el nivel 
+\begin_inset Formula $k$
+\end_inset
+
+ hay un máximo de 
+\begin_inset Formula $2^{k}$
+\end_inset
+
+ vértices, de modo que un árbol de altura 
+\begin_inset Formula $h$
+\end_inset
+
+ tiene un máximo de 
+\begin_inset Formula $\sum_{k=0}^{h}2^{k}=2^{h+1}-1$
+\end_inset
+
+, pero 
+\begin_inset Formula 
+\[
+n\leq2^{h+1}-1\iff n+1\leq2^{h+1}\iff\lg(n+1)-1\leq h\overset{h\in\mathbb{Z}}{\iff}h\geq\lceil\lg(n+1)-1\rceil.
+\]
+
+\end_inset
+
+ La igualdad se alcanza en 
+\begin_inset Formula $T':=(V',E')$
+\end_inset
+
+ con 
+\begin_inset Formula $V':=\{1,\dots,n\}$
+\end_inset
+
+ y 
+\begin_inset Formula $E':=\{(k,\lfloor\frac{k}{2}\rfloor)\}_{k\in\{2,\dots,n\}}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Section
+Árboles generadores mínimos
+\end_layout
+
+\begin_layout Standard
+Una 
+\series bold
+red
+\series default
+ es una terna 
+\begin_inset Formula $(V,E,\ell)$
+\end_inset
+
+ donde 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+ es un grafo y 
+\begin_inset Formula $\ell:E\to\mathbb{R}$
+\end_inset
+
+ es la 
+\series bold
+función de peso
+\series default
+ o 
+\series bold
+de longitud
+\series default
+.
+ Dados una red conexa 
+\begin_inset Formula $G=(V,E,\ell)$
+\end_inset
+
+ y un árbol generador 
+\begin_inset Formula $T=(V,E')$
+\end_inset
+
+ de 
+\begin_inset Formula $G$
+\end_inset
+
+, el 
+\series bold
+peso
+\series default
+ del árbol es
+\begin_inset Formula 
+\[
+\ell(T):=\sum_{e\in E'}\ell(e).
+\]
+
+\end_inset
+
+
+\begin_inset Formula $T$
+\end_inset
+
+ es un árbol generador 
+\series bold
+minimal
+\series default
+ o 
+\series bold
+mínimo
+\series default
+ si tiene el mínimo peso entre los árboles generadores de 
+\begin_inset Formula $G$
+\end_inset
+
+, si y sólo si para 
+\begin_inset Formula $a\in E\setminus E'$
+\end_inset
+
+ y 
+\begin_inset Formula $e\in E'$
+\end_inset
+
+ en el único camino de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+ en 
+\begin_inset Formula $T$
+\end_inset
+
+ es 
+\begin_inset Formula $\ell(e)\leq\ell(a)$
+\end_inset
+
+, si y sólo si para 
+\begin_inset Formula $e\in E'$
+\end_inset
+
+ que separa 
+\begin_inset Formula $T$
+\end_inset
+
+ en componentes conexas 
+\begin_inset Formula $V_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $V_{2}$
+\end_inset
+
+ y 
+\begin_inset Formula $a\in\omega_{G}(V_{1})$
+\end_inset
+
+ es 
+\begin_inset Formula $\ell(e)\leq\ell(a)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $1\implies2]$
+\end_inset
+
+ Si fuera 
+\begin_inset Formula $\ell(a)<\ell(e)$
+\end_inset
+
+, como el grafo 
+\begin_inset Formula $(V,E'\cup\{a\}\setminus\{e\})$
+\end_inset
+
+ es un árbol al ser conexo y acíclico, y su peso sería menor que el de 
+\begin_inset Formula $T$
+\end_inset
+
+, 
+\begin_inset Formula $T$
+\end_inset
+
+ no sería minimal.
+\begin_inset Formula $\#$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $2\implies3]$
+\end_inset
+
+ Sean 
+\begin_inset Formula $e\in T$
+\end_inset
+
+, 
+\begin_inset Formula $V_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $V_{2}$
+\end_inset
+
+ las componentes conexas de 
+\begin_inset Formula $T-e$
+\end_inset
+
+, y 
+\begin_inset Formula $u\in V_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $v\in V_{2}$
+\end_inset
+
+ tales que 
+\begin_inset Formula $a:=(u,v)\in E$
+\end_inset
+
+, si 
+\begin_inset Formula $a=e$
+\end_inset
+
+ hemos terminado, y en otro caso 
+\begin_inset Formula $a\in E\setminus E'$
+\end_inset
+
+ y 
+\begin_inset Formula $e$
+\end_inset
+
+ está en el único camino que conecta 
+\begin_inset Formula $u$
+\end_inset
+
+ con 
+\begin_inset Formula $v$
+\end_inset
+
+ en 
+\begin_inset Formula $T$
+\end_inset
+
+, luego 
+\begin_inset Formula $\ell(e)\leq\ell(a)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $3\implies1]$
+\end_inset
+
+ Elegimos un árbol generador minimal 
+\begin_inset Formula $T_{0}=(V,E_{0})$
+\end_inset
+
+.
+ Si 
+\begin_inset Formula $T=T_{0}$
+\end_inset
+
+, hemos terminado.
+ En otro caso, como 
+\begin_inset Formula $|E'|=|E_{0}|$
+\end_inset
+
+, existe 
+\begin_inset Formula $e\in E'\setminus E_{0}$
+\end_inset
+
+.
+ Sean 
+\begin_inset Formula $V_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $V_{2}$
+\end_inset
+
+ las componentes conexas de 
+\begin_inset Formula $T-e$
+\end_inset
+
+ y 
+\begin_inset Formula $S:=(V,E_{0}\cup\{e\})$
+\end_inset
+
+, como 
+\begin_inset Formula $S$
+\end_inset
+
+ tiene un ciclo que contiene a 
+\begin_inset Formula $e\in\omega_{T}(V_{1})$
+\end_inset
+
+, debe contener a otro 
+\begin_inset Formula $a\in\omega_{T}(V_{1})\cap E_{0}$
+\end_inset
+
+, luego por hipótesis 
+\begin_inset Formula $\ell(e)\leq\ell(a)$
+\end_inset
+
+ y 
+\begin_inset Formula $T_{1}:=(V,E_{1}:=E_{0}\cup\{e\}\setminus\{a\})$
+\end_inset
+
+ tiene menor o igual (en concreto igual) peso que 
+\begin_inset Formula $T_{0}$
+\end_inset
+
+ pero que se diferencia de 
+\begin_inset Formula $T$
+\end_inset
+
+ en un nodo menos que 
+\begin_inset Formula $T_{0}$
+\end_inset
+
+.
+ Repitiendo este proceso llegamos a que 
+\begin_inset Formula $T_{0}$
+\end_inset
+
+ tiene el mismo peso que 
+\begin_inset Formula $T$
+\end_inset
+
+ y por tanto 
+\begin_inset Formula $T$
+\end_inset
+
+ es minimal.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Red conexa $G=(V,E,
+\backslash
+ell)$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Árbol generador minimal $(V,T)$ de $G$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+Ordenar los nodos de $E$ en orden creciente de peso $
+\backslash
+ell$ en la lista $L$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$T
+\backslash
+gets
+\backslash
+emptyset$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$i
+\backslash
+gets1$ 
+\backslash
+KwA $|L|$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	$(u,v)
+\backslash
+gets L_i$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lSSi{no existe un camino de $u$ a $v$ en $(V,T)$}{añadir $L_i$ a $T$}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:kruskal"
+
+\end_inset
+
+Algoritmo de Kruskal.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+algoritmo de Kruskal
+\series default
+ (algoritmo 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:kruskal"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+) construye el árbol generador minimal de una red conexa, pues se asegura
+ de que todo par de vértices adyacentes de la red estén conectados en el
+ árbol, no crea ciclos y, si una arista 
+\begin_inset Formula $(u,v)$
+\end_inset
+
+ queda fuera del árbol, todas las aristas del camino de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+ en el árbol ya habían sido consideradas y por tanto tienen peso menor.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Red conexa $G=(V,E,
+\backslash
+ell)$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Árbol generador minimal $(V,T)$ de $G$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+Tomar $r
+\backslash
+in V$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$V_1
+\backslash
+gets
+\backslash
+{r
+\backslash
+}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$V_2
+\backslash
+gets V
+\backslash
+setminus
+\backslash
+{r
+\backslash
+}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$T
+\backslash
+gets
+\backslash
+emptyset$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{$|V_1|<|V|$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	Tomar $v_1
+\backslash
+in V_1$ y $v_2
+\backslash
+in V_2$ con $e:=(v_1,v_2)
+\backslash
+in E$ de peso mínimo
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	Añadir $e$ a $T$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	Mover $v_2$ de $V_2$ a $V_1$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:prim"
+
+\end_inset
+
+Algoritmo de Prim.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+algoritmo de Prim
+\series default
+ (algoritmo 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:prim"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+) hace lo mismo, pues se asegura de que todos los vértices estén conectados
+ a 
+\begin_inset Formula $r$
+\end_inset
+
+, no crea ciclos porque no considera ejes cuyos vértices ya hayan sido conectado
+s en el árbol y, cuando selecciona una arista 
+\begin_inset Formula $e$
+\end_inset
+
+, que estaría separando al árbol en 
+\begin_inset Formula $V_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $V_{2}$
+\end_inset
+
+, se asegura de que tenga peso mínimo entre las aristas de 
+\begin_inset Formula $\omega_{G}(V_{1})$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Red conexa $(V,E,
+\backslash
+ell)$}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Árbol generador minimal $(V,T)$ de $G$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+$T
+\backslash
+gets
+\backslash
+emptyset$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{$(V,T)$ sea disconexo}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+ParaCada{componente conexa $V_i$ de $(V,T)$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		Tomar $u_i
+\backslash
+in V_i$ y $v_i
+\backslash
+in V
+\backslash
+setminus V_i$ con $(u_i,v_i)
+\backslash
+in E$ de peso mínimo
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+ParaCada{componente conexa $V_i$ de $(V,T)$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		
+\backslash
+lSSi{$u_i$ y $v_i$ no están conectados en $(V,T)$}{$T
+\backslash
+gets T
+\backslash
+cup(u_i,v_i)$}
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:boruvka"
+
+\end_inset
+
+Algoritmo de Sollin.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Otro algoritmo para hacer esto es el 
+\series bold
+algoritmo de Sollin
+\series default
+ (algoritmo 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:boruvka"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+)
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Se recomienda comprobar la conexión de 
+\begin_inset Formula $(V,T)$
+\end_inset
+
+ manteniendo un conjunto cociente con las componentes conexas.
+ Ver el capítulo 3 de los apuntes de AED I para más información.
+\end_layout
+
+\end_inset
+
+.
+ Finalmente, podemos calcular un árbol generador 
+\series bold
+maximal
+\series default
+ o 
+\series bold
+máximo
+\series default
+ de una red 
+\begin_inset Formula $(V,E,\ell)$
+\end_inset
+
+ (el de mayor peso) como un árbol generador minimal de 
+\begin_inset Formula $(V,E,-\ell)$
+\end_inset
+
+, o invirtiendo el sentido de las comparaciones en los algoritmos anteriores.
+\end_layout
+
+\end_body
+\end_document