#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}\coloneqq v_{0}\coloneqq u$
\end_inset

, 
\begin_inset Formula $u_{p}\coloneqq u_{q}\coloneqq 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\coloneqq (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\coloneqq (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\coloneqq \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'\coloneqq (V',E')$
\end_inset

 dado por 
\begin_inset Formula $V'\coloneqq \{b_{0},a_{1},b_{1},\dots,a_{h},b_{h}\}$
\end_inset

 y 
\begin_inset Formula $E'\coloneqq \{(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'\coloneqq (V',E')$
\end_inset

 con 
\begin_inset Formula $V'\coloneqq \{1,\dots,n\}$
\end_inset

 y 
\begin_inset Formula $E'\coloneqq \{(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\coloneqq (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\coloneqq (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}\coloneqq (V,E_{1}\coloneqq 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
\backslash
coloneqq (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