Otras dos asignaturas

6 files changed, 7056 insertions, 0 deletions

diff --git a/aed1/graph.svg b/aed1/graph.svg
new file mode 100644
index 0000000..b5e834f
--- /dev/null
+++ b/aed1/graph.svg
@@ -0,0 +1,69 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
+<!-- Generated by dot version 2.8 (Fri Nov 17 20:26:27 UTC 2006)
+     For user: (azatoth) Carl Furstenberg,,, -->
+<!-- Title: untitled Pages: 1 -->
+<svg width="266pt" height="176pt" viewBox="0 0 266 176" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" style="font-family:Times-Roman;font-size:14.00;">
+<title>untitled</title>
+<polygon style="fill:none;stroke:none;" points="-2,178 -2,-2 268,-2 268,178 -2,178"/>
+<!-- 1 -->
+<g id="node1" class="node"><title>1</title>
+<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="237" cy="83" rx="24" ry="24"/>
+<text text-anchor="middle" x="237" y="90" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">1</text>
+</g>
+<!-- 2 -->
+<g id="node2" class="node"><title>2</title>
+<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="187" cy="135" rx="24" ry="24"/>
+<text text-anchor="middle" x="187" y="142" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">2</text>
+</g>
+<!-- 1&#45;&#45;2 -->
+<g id="edge5" class="edge"><title>1--2</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M220,100C215,106 209,112 204,117"/>
+</g>
+<!-- 3 -->
+<g id="node3" class="node"><title>3</title>
+<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="109" cy="147" rx="24" ry="24"/>
+<text text-anchor="middle" x="109" y="154" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">3</text>
+</g>
+<!-- 2&#45;&#45;3 -->
+<g id="edge6" class="edge"><title>2--3</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M163,139C153,140 142,142 133,143"/>
+</g>
+<!-- 5 -->
+<g id="node5" class="node"><title>5</title>
+<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="170" cy="58" rx="24" ry="24"/>
+<text text-anchor="middle" x="170" y="65" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">5</text>
+</g>
+<!-- 2&#45;&#45;5 -->
+<g id="edge9" class="edge"><title>2--5</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M182,111C180,102 177,91 175,82"/>
+</g>
+<!-- 4 -->
+<g id="node4" class="node"><title>4</title>
+<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="92" cy="70" rx="24" ry="24"/>
+<text text-anchor="middle" x="92" y="77" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">4</text>
+</g>
+<!-- 3&#45;&#45;4 -->
+<g id="edge7" class="edge"><title>3--4</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M104,123C102,114 99,103 97,94"/>
+</g>
+<!-- 4&#45;&#45;5 -->
+<g id="edge3" class="edge"><title>4--5</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M116,66C126,65 137,63 146,62"/>
+</g>
+<!-- 5&#45;&#45;1 -->
+<g id="edge4" class="edge"><title>5--1</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M193,66C200,69 207,72 214,75"/>
+</g>
+<!-- 6 -->
+<g id="node6" class="node"><title>6</title>
+<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="29" cy="29" rx="24" ry="24"/>
+<text text-anchor="middle" x="29" y="36" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">6</text>
+</g>
+<!-- 6&#45;&#45;4 -->
+<g id="edge2" class="edge"><title>6--4</title>
+<path style="fill:none;stroke:black;stroke-width:3;" d="M49,42C56,47 65,52 72,57"/>
+</g>
+</g>
+</svg>
\ No newline at end of file
diff --git a/aed1/n.lyx b/aed1/n.lyx
new file mode 100644
index 0000000..069c70b
--- /dev/null
+++ b/aed1/n.lyx
@@ -0,0 +1,219 @@
+#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
+\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 10
+\spacing single
+\use_hyperref false
+\papersize a5paper
+\use_geometry true
+\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
+\leftmargin 0.2cm
+\topmargin 0.7cm
+\rightmargin 0.2cm
+\bottommargin 0.7cm
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style swiss
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle empty
+\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 Title
+Algoritmos y Estructuras de Datos I
+\end_layout
+
+\begin_layout Date
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+def
+\backslash
+cryear{2018}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "../license.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Bibliografía:
+\end_layout
+
+\begin_layout Itemize
+Programa de teoría (diapositivas), A.E.D.
+ 1, Facultad de Informática, Universidad de Murcia.
+\end_layout
+
+\begin_layout Itemize
+Texto guía, anónimo.
+\end_layout
+
+\begin_layout Itemize
+Wikipedia, la Enciclopedia Libre (
+\begin_inset Flex URL
+status open
+
+\begin_layout Plain Layout
+
+https://es.wikipedia.org/
+\end_layout
+
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Itemize
+Competitive Programming 3: The New Lower Bound of Programming Contests (2013),
+ Steven & Felix Halim.
+\end_layout
+
+\begin_layout Chapter
+Abstracción y especificación
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n1.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Chapter
+Conjuntos y diccionarios
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n2.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Chapter
+Árboles
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n3.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Chapter
+Grafos
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n4.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document
diff --git a/aed1/n1.lyx b/aed1/n1.lyx
new file mode 100644
index 0000000..d39e26b
--- /dev/null
+++ b/aed1/n1.lyx
@@ -0,0 +1,1680 @@
+#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
+\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
+Una 
+\series bold
+abstracción
+\series default
+ consiste en dejar a un lado lo irrelevante y centrarse en lo importante.
+ Distinguimos 
+\series bold
+niveles de abstracción
+\series default
+ según el nivel de detalle.
+ El 
+\series bold
+diseño mediante abs
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+trac
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+cio
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+nes
+\series default
+ consiste en identificar los subproblemas de cierto problema, especificar
+ cada uno de forma abstracta, resolverlos de forma separada, unir las soluciones
+ y verificar la solución para el problema original.
+ Esto se hace de forma recursiva.
+\end_layout
+
+\begin_layout Standard
+Junto con el concepto de abstracción viene el de 
+\series bold
+especificación
+\series default
+ de dicha abstracción.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Mecanismos de abstracción
+\series default
+:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Por especificación
+\series default
+: Nos quedamos con la descripción del efecto o resultado, in
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+de
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+pen
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+dien
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+te
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+men
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+te de cómo calcularlo (
+\series bold
+principio de ocultación de la implementación
+\series default
+).
+ Da lugar a la 
+\series bold
+encapsulación
+\series default
+, agrupar un conjunto de operaciones o tipos relacionados en un mismo módulo
+ o paquete.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Por parametrización
+\series default
+: El significado de la abstracción no es fijo, sino que depende de parámetros.
+ En la 
+\series bold
+parametrización de tipo
+\series default
+, el parámetro es un tipo de datos.
+\end_layout
+
+\begin_layout Section
+Especificaciones informales
+\end_layout
+
+\begin_layout Standard
+Una 
+\series bold
+especificación
+\series default
+ es la descripción de una abstracción, bien textualmente mediante el lenguaje
+ natural (especificación 
+\series bold
+informal
+\series default
+) o bien con una notación precisa de las propiedades de la abstracción (especifi
+cación 
+\series bold
+formal
+\series default
+), mediante una 
+\series bold
+notación
+\series default
+.
+ A continuación vemos los tipos de abstracciones y una notación propuesta
+ para su especificación informal.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Funcionales
+\series default
+: Abstraemos un trozo de código en una 
+\series bold
+rutina
+\series default
+, 
+\series bold
+procedimiento
+\series default
+ o 
+\series bold
+función
+\series default
+, al que asignamos un nombre.
+ Su especificación indica los parámetros de entrada, los de salida y el
+ efecto que tendrá su ejecución.
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Tabular
+<lyxtabular version="3" rows="2" columns="1">
+<features tabularvalignment="middle">
+<column alignment="left" valignment="top" width="90text%">
+<row>
+<cell alignment="left" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Especificación informal
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+Operación
+\series default
+ 
+\emph on
+nombre
+\emph default
+ 
+\family default
+[
+\family sans
+[
+\emph on
+T
+\emph default
+,
+\family default
+...
+\family sans
+:
+\emph on
+TipoDeTipo
+\emph default
+; 
+\family default
+...
+\family sans
+]
+\family default
+]
+\family sans
+ (
+\family default
+[
+\family sans
+\series bold
+ent
+\series default
+ 
+\emph on
+v1
+\emph default
+, 
+\family default
+...
+\family sans
+:
+\emph on
+Tipo
+\emph default
+1; 
+\emph on
+vn
+\emph default
+, 
+\family default
+...
+\family sans
+:
+\emph on
+Tipo2
+\emph default
+; 
+\family default
+...[
+\family sans
+;
+\family default
+]]
+\family sans
+ 
+\family default
+[
+\family sans
+\series bold
+sal
+\series default
+ 
+\emph on
+tipoResultado
+\family default
+\emph default
+]
+\family sans
+)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+Require:
+\series default
+ 
+\emph on
+Opcional, requisitos y restricciones de uso de la operación.
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+Modifica:
+\series default
+ 
+\emph on
+Opcional, lista de parámetros de entrada que pueden ser
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+modificados.
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+Calcula:
+\series default
+ 
+\emph on
+Descripción del resultado de la operación.
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\begin_inset Newline newline
+\end_inset
+
+Donde el 
+\family sans
+\emph on
+TipoDeTipo
+\family default
+\emph default
+ suele ser 
+\family sans
+tipo
+\family default
+.
+ Tanto en la especificación informal como en el pseudocódigo, los tipos
+ tanto de los parámetros de tipo como los propios de la función pueden depender
+ de parámetros anteriores.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+De datos
+\series default
+: Se abstrae un dominio de valores, junto con operaciones sobre ese dominio
+ con 
+\series bold
+ocultación de la implementación
+\series default
+, en un 
+\series bold
+tipo abstracto de datos
+\series default
+ (
+\series bold
+TAD
+\series default
+).
+ Un 
+\series bold
+tipo contenedor
+\series default
+ es un TAD compuesto por un número arbitrario de valores de otro tipo.
+ Generalmente están 
+\series bold
+parametrizados
+\series default
+: dependen de un parámetro que indica el tipo de objetos almacenados.
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Tabular
+<lyxtabular version="3" rows="2" columns="1">
+<features tabularvalignment="middle">
+<column alignment="left" valignment="top" width="90text%">
+<row>
+<cell alignment="left" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Especificación informal
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+TAD
+\series default
+ 
+\emph on
+nombre
+\emph default
+ 
+\series bold
+es
+\series default
+ 
+\emph on
+listaDeOperaciones
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+Descripción
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+Descripción del significado, comportamiento y modo de uso del TAD.
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+Operaciones
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+Especificación informal de cada operación de la lista, según el punto anterior.
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+Fin
+\series default
+ 
+\emph on
+nombre
+\emph default
+.
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\begin_inset Newline newline
+\end_inset
+
+Así, un 
+\series bold
+tipo de datos
+\series default
+ es un concepto de implementación que debe ajustarse al comportamiento de
+ un TAD, y una 
+\series bold
+estructura de datos
+\series default
+ es la disposición en memoria de estos datos.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+De iteradores
+\series default
+: Permiten realizar un recorrido de forma abstracta sobre los elementos
+ de una colección.
+ La especificación informal puede ser:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+Similar a la de una abstracción funcional, cambiando 
+\family sans
+\series bold
+Operación
+\family default
+\series default
+ por 
+\family sans
+\series bold
+Iterador
+\family default
+\series default
+ y añadiendo un parámetro de entrada de tipo 
+\family sans
+Operacion
+\family default
+.
+ La función puede devolver un valor si, por ejemplo, el iterador filtra
+ una colección de valores de un cierto tipo.
+\end_layout
+
+\begin_layout Itemize
+Similar a la de un TAD, cambiando 
+\family sans
+\series bold
+TAD
+\family default
+\series default
+ por 
+\family sans
+\series bold
+TipoIterador
+\family default
+\series default
+ y añadiendo operaciones como 
+\family sans
+Iniciar
+\family default
+, 
+\family sans
+Actual
+\family default
+, 
+\family sans
+Avanzar
+\family default
+ y 
+\family sans
+EsUltimo
+\family default
+.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+La abstracción en lenguajes de programación generalmente consiste en ofrecer
+ características más próximas al concepto teórico de TAD.
+ Los lenguajes primitivos como Fortran o BASIC ofrecían un conjunto predefinido
+ de tipos elementales, pero no permitían definir nuevos tipos, con lo que
+ el programador debía definir y manejar las variables adecuadas de forma
+ manual.
+ Posteriormente, lenguajes como C y Pascal permiten agrupar un conjunto
+ de variables bajo un mismo nombre, aunque no hay ocultación.
+ Los módulos o paquetes permiten agrupar bajo un mismo nombre una serie
+ de tipos y operaciones relacionados, y en algunos casos como en Modula-2,
+ estos ofrecen ocultación de la implementación: los tipos definidos en un
+ módulo sólo se pueden usar a través de las operaciones de este.
+\end_layout
+
+\begin_layout Standard
+Finalmente, en la programación orientada a objetos surge el concepto de
+ clase, que es al mismo tiempo un tipo definido por el usuario y un módulo
+ donde se encapsulan sus datos y operaciones, y soportan ocultación.
+ Un objeto es una instancia de una clase.
+ El 
+\series bold
+principio de acceso uniforme
+\series default
+ consiste en que los atributos y operaciones de una clase están conceptualmente
+ al mismo nivel, y se accede con 
+\family typewriter
+\emph on
+objeto
+\emph default
+.
+\emph on
+atributo
+\family default
+\emph default
+ u 
+\family typewriter
+\emph on
+objeto
+\emph default
+.
+\emph on
+operación
+\emph default
+(
+\family default
+...
+\family typewriter
+)
+\family default
+.
+ Algunos lenguajes orientados a objetos permiten parametrización de tipo,
+ dando lugar a TAD genéricos o parametrizados.
+\end_layout
+
+\begin_layout Standard
+Una implementación es 
+\series bold
+robusta
+\series default
+ si se autoprotege de valores inconsistentes de entrada, bien lanzando una
+ excepción o mediante programación por contrato, en la que el usuario se
+ compromete, de forma comprobable, a no pasar un valor inconsistente según
+ la especificación de la función.
+ 
+\end_layout
+
+\begin_layout Section
+Especificaciones formales
+\end_layout
+
+\begin_layout Standard
+Una 
+\series bold
+especificación formal
+\series default
+ define un TAD u operación de forma precisa, permitiendo la verificación
+ automática y formal de la corrección del programa y el uso de la especificación
+ en distintos ámbitos.
+ Estas especificaciones pueden llegar a ser ejecutables.
+ Distinguimos entre el 
+\series bold
+método axiomático
+\series default
+ o 
+\series bold
+algebraico
+\series default
+, que establece el significado de las operaciones de forma implícita mediante
+ 
+\series bold
+axiomas
+\series default
+ que especifican sus relaciones, y el 
+\series bold
+método constructivo
+\series default
+ u 
+\series bold
+operacional
+\series default
+, en el que cada operación se define por sí misma con significado explícito.
+\end_layout
+
+\begin_layout Standard
+Veremos un método constructivo al que llamaremos método axiomático, y que
+ escribimos en lenguaje Maude, describiendo un TAD del siguiente modo:
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset Tabular
+<lyxtabular version="3" rows="6" columns="2">
+<features tabularvalignment="middle">
+<column alignment="left" valignment="top" width="45text%">
+<column alignment="left" valignment="top" width="45text%">
+<row>
+<cell alignment="left" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Especificación formal
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="left" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Maude
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+NOMBRE
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+NombreTAD
+\family default
+\emph default
+ [
+\family sans
+[
+\emph on
+T1
+\emph default
+,
+\family default
+...
+\family sans
+]
+\family default
+]
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+\series bold
+fmod
+\series default
+ 
+\emph on
+NOMBRETAD
+\emph default
+ 
+\series bold
+is
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+CONJUNTOS
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+CONJ
+\emph default
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+Descripción
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+protecting 
+\emph on
+TADIMPORTADO
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+sort 
+\emph on
+CONJ
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+subsort 
+\emph on
+A
+\emph default
+ < 
+\emph on
+B
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+SINTAXIS
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family sans
+\emph on
+operación
+\emph default
+:
+\family default
+ [
+\family sans
+\emph on
+conjPar1
+\family default
+\emph default
+
+\begin_inset Formula $\times$
+\end_inset
+
+...]
+\family sans
+ 
+\begin_inset Formula $\rightarrow$
+\end_inset
+
+ 
+\emph on
+conjResultado
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+op 
+\emph on
+operación
+\emph default
+ : 
+\family default
+[
+\family typewriter
+\emph on
+conjPar11
+\emph default
+ 
+\begin_inset Formula $\times$
+\end_inset
+
+ ...
+\family default
+]
+\family typewriter
+ -> 
+\emph on
+conjResultado1
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+ops 
+\emph on
+op1
+\emph default
+ 
+\family default
+...
+
+\family typewriter
+ : 
+\family default
+[
+\family typewriter
+\emph on
+conjPar21
+\emph default
+ 
+\begin_inset Formula $\times$
+\end_inset
+
+ ...
+\family default
+]
+\family typewriter
+ -> 
+\emph on
+conjResultado2
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+SEMÁNTICA
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Formula $\forall$
+\end_inset
+
+
+\family sans
+\emph on
+ var1
+\emph default
+, 
+\family default
+...
+
+\family sans
+ 
+\begin_inset Formula $\in$
+\end_inset
+
+
+\emph on
+ CONJ
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\emph on
+ExprA
+\emph default
+ = 
+\emph on
+ExprB
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+var 
+\emph on
+v
+\emph default
+ : 
+\emph on
+CONJ
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+vars 
+\emph on
+v1
+\emph default
+ 
+\family default
+...
+
+\family typewriter
+ : 
+\emph on
+CONJ
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+eq 
+\emph on
+ExprA
+\emph default
+ = 
+\emph on
+ExprB
+\emph default
+ .
+\end_layout
+
+\begin_layout Plain Layout
+
+\family typewriter
+\begin_inset space \qquad{}
+\end_inset
+
+
+\family default
+...
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+\series bold
+endfm
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El nombre de los conjuntos suele ser de una letra, y debe haber un conjunto
+ asociado al TAD, y si el TAD es genérico, uno para cada parámetro con el
+ mismo nombre dado en la sección anterior (
+\family sans
+\emph on
+T1
+\family default
+\emph default
+, etc.).
+ También, en la especificación se declaran conjuntos asociados a otros TADs
+ pero que se usan en este, mientras que en Maude se usa 
+\family typewriter
+protecting
+\family default
+ para importar todos los conjuntos, junto con sus operaciones, de otro TAD.
+ Para tipos finitos en la especificación, si en la 
+\family sans
+\emph on
+Descripción
+\family default
+\emph default
+ se añade al final 
+\family sans
+{
+\emph on
+valor1
+\emph default
+, 
+\family default
+...
+\family sans
+}
+\family default
+, estos valores se pueden usar en la semántica.
+\end_layout
+
+\begin_layout Standard
+Entre las operaciones encontramos 
+\series bold
+constructores
+\series default
+, operaciones cuya semántica no se define y que sirven para definir elementos
+ del TAD, y tales que, si es posible, un elemento del TAD debería tener
+ representación única en términos de estos.
+ El resto son de 
+\series bold
+modificación
+\series default
+ o de 
+\series bold
+consulta
+\series default
+ según si devuelven un elemento del conjunto asociado al TAD o de otro tipo,
+ respectivamente.
+\end_layout
+
+\begin_layout Standard
+Si una operación que normalmente devuelve valores de tipo 
+\family sans
+T
+\family default
+ no esta definida para cierta entrada, se crea un conjunto 
+\family sans
+M
+\family default
+ de mensajes cuya descripción contiene al final 
+\family sans
+{
+\begin_inset Quotes fls
+\end_inset
+
+
+\emph on
+Texto mensaje 1
+\emph default
+
+\begin_inset Quotes frs
+\end_inset
+
+, 
+\family default
+...
+\family sans
+}
+\family default
+, y el conjunto resultado de la operación se declara 
+\family sans
+T
+\begin_inset Formula $\cup$
+\end_inset
+
+M
+\family default
+, mientras que en Maude se crea un tipo de errores 
+\family typewriter
+NoT
+\family default
+ con un constructor sin parámetros para cada tipo de error y se usa 
+\family typewriter
+subsort No
+\emph on
+T
+\emph default
+ < 
+\emph on
+T
+\family default
+\emph default
+ para indicar que toda operación que toda operación que devuelva un valor
+ de 
+\family typewriter
+\emph on
+T
+\family default
+\emph default
+ también puede devolver uno de 
+\family typewriter
+No
+\emph on
+T
+\family default
+\emph default
+.
+\end_layout
+
+\begin_layout Standard
+La semántica consiste en una serie de reglas que, dada una expresión, Maude
+ va comprobando de arriba a abajo sucesivamente para ver si parte de la
+ expresión coincide con 
+\family sans
+\emph on
+ExprA
+\family default
+\emph default
+ y sustituirla en tan caso por 
+\family sans
+\emph on
+ExprB
+\family default
+\emph default
+ hasta que no queden sustituciones por hacer, momento en que la expresión
+ debería estar en términos de constructores.
+ Una expresión tiene sintaxis 
+\family typewriter
+\emph on
+op
+\family default
+\emph default
+[
+\family typewriter
+(
+\emph on
+par1
+\emph default
+, 
+\family default
+...
+\family typewriter
+)
+\family default
+], donde los parámetros de la operación son a su vez otras expresiones.
+ 
+\family sans
+\emph on
+ExprB
+\family default
+\emph default
+ o alguna de sus subexpresiones puede ser 
+\family sans
+\series bold
+SI
+\series default
+ 
+\emph on
+condición
+\emph default
+ 
+\begin_inset Formula $\implies$
+\end_inset
+
+ 
+\emph on
+valorSiCierto
+\emph default
+ | 
+\emph on
+valorSiFalso
+\family default
+\emph default
+, o en Maude, 
+\family typewriter
+if 
+\emph on
+condición
+\emph default
+ then 
+\emph on
+valorSiCierto
+\emph default
+ else 
+\emph on
+valorSiFalso
+\emph default
+ fi
+\family default
+.
+\end_layout
+
+\begin_layout Standard
+En Maude, fuera de la definición de un TAD podemos usar 
+\family typewriter
+in 
+\emph on
+nombre
+\emph default
+ .
+
+\family default
+ para leer todo lo que hay en un fichero llamado 
+\family typewriter
+\emph on
+nombre
+\family default
+\emph default
+ o 
+\family typewriter
+\emph on
+nombre
+\emph default
+.maude
+\family default
+ o 
+\family typewriter
+red 
+\emph on
+expr
+\family default
+\emph default
+ para reducir una expresión según la semántica de las operaciones.
+ Un fallo en Maude puede tiene consecuencias impredecibles porque Maude
+ es una mierda.
+\end_layout
+
+\begin_layout Standard
+Si el orden de las reglas no es relevante las llamamos axiomas
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Cada vez que llamas axiomas a algo que depende del orden muere un matemático
+ y un gatito.
+\end_layout
+
+\end_inset
+
+, y estos deben cumplir las propiedades de 
+\series bold
+completitud
+\series default
+ (deben ser suficientes para deducir el significado de cualquier expresión)
+ y 
+\series bold
+corrección
+\series default
+; dicho de otra forma, se deben considerar todos los casos al definir cada
+ operación no constructora.
+\end_layout
+
+\begin_layout Section
+Órdenes de ejecución
+\end_layout
+
+\begin_layout Standard
+Medimos el tiempo que tarda en ejecutarse un algoritmo con una función 
+\begin_inset Formula $t:\mathbb{N}\rightarrow\mathbb{R}^{\geq0}$
+\end_inset
+
+ para cada uno de los casos mejor, peor y promedio, que toma el tamaño del
+ problema medido de algún modo y devuelve el tiempo que tarda en realizarse
+ en cierta máquina, el número de instrucciones total o el de un tipo de
+ instrucción que sabemos que es la más relevante.
+ En la práctica se usan 
+\series bold
+notaciones asintóticas
+\series default
+:
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f(x)=O(g(x)):\iff\exists x_{0},k>0:\forall x\geq x_{0},|f(x)|\leq k|g(x)|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f(x)=\Omega(g(x)):\iff\exists x_{0},k>0:\forall x\geq x_{0},kg(x)\leq f(x)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Comment
+status open
+
+\begin_layout Itemize
+\begin_inset Formula $f(x)=\Theta(g(x)):\iff f(x)=O(g(x))\land f(x)=\Omega(g(x))$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $f(x)=o(g(x)):\iff\lim_{x\rightarrow+\infty}\frac{f(x)}{g(x)}=0$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Estas definiciones sólo son válidas cuando 
+\begin_inset Formula $x$
+\end_inset
+
+ tiende a 
+\begin_inset Formula $+\infty$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document
diff --git a/aed1/n2.lyx b/aed1/n2.lyx
new file mode 100644
index 0000000..26201e5
--- /dev/null
+++ b/aed1/n2.lyx
@@ -0,0 +1,788 @@
+#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
+\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 Section
+Conjuntos
+\end_layout
+
+\begin_layout Standard
+Un conjunto es una colección no ordenada de elementos distintos.
+ El TAD 
+\family sans
+Conjunto[
+\begin_inset Formula $T$
+\end_inset
+
+]
+\family default
+ define conjuntos finitos con elementos de un cierto tipo.
+ Operaciones comunes:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+\begin{array}{rrr}
+\mathsf{Vacío}:\rightarrow C & \mathsf{Unión}:C\times C\rightarrow C & \mathsf{Intersección}:C\times C\rightarrow C\\
+\mapsto\emptyset & (a,b)\mapsto a\cup b & (a,b)\mapsto a\cap b\\
+\\
+\mathsf{Diferencia}:C\times C\rightarrow C & \mathsf{Combina}:C\times C\rightarrow C & \mathsf{Miembro}:T\times C\rightarrow B\\
+(a,b)\mapsto a\backslash b & (a,b)\rightarrow a\dot{\cup}b & (x,a)\mapsto x\in a\\
+\\
+\mathsf{Inserta}:T\times C\rightarrow C & \mathsf{Suprime}:T\times C\rightarrow C & \mathsf{Igual}:C\times C\rightarrow B\\
+(x,a)\mapsto a\cup\{x\} & (x,a)\mapsto a\backslash\{x\} & (a,b)\mapsto a=b
+\end{array}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Si además tenemos un orden total sobre 
+\begin_inset Formula $T$
+\end_inset
+
+, podemos definir 
+\begin_inset Formula $\mathsf{Min}:C\rightarrow T$
+\end_inset
+
+ y 
+\begin_inset Formula $\mathsf{Max}:C\rightarrow T$
+\end_inset
+
+ para conjuntos no vacíos.
+ Implementaciones básicas:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Tabla de booleanos
+\series default
+, donde cada elemento de 
+\family sans
+T
+\family default
+ se representa con un bit 1 si pertenece al conjunto o 0 en caso contrario.
+ La unión, intersección, diferencia y comprobación de igualdad son 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ con 
+\begin_inset Formula $n:=|T|$
+\end_inset
+
+, mientras que la inserción y eliminación y comprobación de pertenencia
+ son 
+\begin_inset Formula $O(1)$
+\end_inset
+
+.
+ Las operaciones son muy sencillas de implementar y no hace falta memoria
+ dinámica, pero el tamaño de un conjunto es proporcional a 
+\begin_inset Formula $|T|$
+\end_inset
+
+ y por tanto solo es adecuado cuando 
+\begin_inset Formula $|T|$
+\end_inset
+
+ es pequeño.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Lista de elementos
+\series default
+.
+
+\series bold
+ 
+\series default
+La unión, intersección y diferencia son 
+\begin_inset Formula $O(mn)$
+\end_inset
+
+ siendo 
+\begin_inset Formula $m$
+\end_inset
+
+ y 
+\begin_inset Formula $n$
+\end_inset
+
+ el tamaño de los conjuntos de entrada, mientras que la comprobación de
+ pertenencia, inserción y eliminación son 
+\begin_inset Formula $O(n)$
+\end_inset
+
+.
+ La comprobación de igualdad es 
+\begin_inset Formula $O(1)$
+\end_inset
+
+ en el caso mejor (
+\begin_inset Formula $m\neq n$
+\end_inset
+
+) y 
+\begin_inset Formula $O(n^{2})$
+\end_inset
+
+ en el peor.
+ Se usa un espacio proporcional al del conjunto representado, pero es más
+ complejo de implementar, y las operaciones son menos eficientes si el conjunto
+ es grande o 
+\begin_inset Formula $|T|$
+\end_inset
+
+ es pequeño.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{sloppypar}
+\end_layout
+
+\end_inset
+
+
+\series bold
+Lista de elementos ordenada
+\series default
+.
+ La unión, intersección y diferencia pasan a ser 
+\begin_inset Formula $O(\max\{m,n\})$
+\end_inset
+
+ en el caso mejor y 
+\begin_inset Formula $O(m+n)$
+\end_inset
+
+ en el peor, y la comprobación de igualdad en el caso peor pasa a ser 
+\begin_inset Formula $O(n)$
+\end_inset
+
+.
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{sloppypar}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Diccionarios
+\end_layout
+
+\begin_layout Standard
+Una asociación es un par clave-valor, y un diccionario es un conjunto de
+ asociaciones sin más de un valor para una misma clave.
+ Nos limitamos a 
+\family sans
+Diccionario[
+\begin_inset Formula $T_{k}$
+\end_inset
+
+, 
+\begin_inset Formula $T_{v}$
+\end_inset
+
+]
+\family default
+, diccionarios finitos con claves de un cierto tipo 
+\begin_inset Formula $T_{k}$
+\end_inset
+
+ y valores de tipo 
+\begin_inset Formula $T_{v}$
+\end_inset
+
+.
+ Operaciones comunes:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+\begin{array}{rr}
+\mathsf{Inserta}:T_{k}\times T_{v}\times D\rightarrow D & \mathsf{Consulta}:T_{k}\times D\rightarrow T_{v}\\
+(k,v,d)\overset{k\notin\text{Dom}(d)}{\mapsto}D\cup\{(k,v)\} & (k,d)\overset{k\in\text{Dom}(d)}{\mapsto}d(k)\\
+\mathsf{}\\
+\mathsf{Suprime}:T_{k}\times D\rightarrow D & \mathsf{Vacío}:\rightarrow D\\
+(k,d)\mapsto\{(a,b)\in d:a\neq k\} & \mapsto\emptyset
+\end{array}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+La representación más sencilla es mediante una lista de asociaciones.
+\end_layout
+
+\begin_layout Section
+Tablas de dispersión
+\end_layout
+
+\begin_layout Standard
+Permiten una representación más eficiente de conjuntos y diccionarios mediante
+ una lista contigua de 
+\begin_inset Formula $M$
+\end_inset
+
+ elementos y una 
+\series bold
+función
+\series default
+ 
+\series bold
+\emph on
+hash
+\series default
+\emph default
+ o 
+\series bold
+de dispersión
+\series default
+ 
+\begin_inset Formula $h:T\rightarrow\{0,\dots,M-1\}$
+\end_inset
+
+.
+ La idea es que, para diccionarios, 
+\begin_inset Formula $h$
+\end_inset
+
+ solo dependa de la clave de la asociación, no del valor.
+ Se dice que 
+\begin_inset Formula $x\neq y\in T$
+\end_inset
+
+ son sinónimos si 
+\begin_inset Formula $h(x)=h(y)$
+\end_inset
+
+.
+ Existen dos formas de dispersión:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Abierta
+\series default
+: Los elementos de la tabla son apuntadores a listas (enlazadas) de elementos,
+ llamadas 
+\series bold
+cubetas
+\series default
+, que contienen los elementos 
+\begin_inset Formula $\{e\in c:h(e)=k\}$
+\end_inset
+
+, siendo 
+\begin_inset Formula $c$
+\end_inset
+
+ el conjunto y 
+\begin_inset Formula $k$
+\end_inset
+
+ el índice de la cubeta.
+\begin_inset Newline newline
+\end_inset
+
+El tamaño de las cubetas en un reparto uniforme (lo ideal) es 
+\begin_inset Formula $\frac{n}{M}$
+\end_inset
+
+, siendo 
+\begin_inset Formula $n$
+\end_inset
+
+ el número de elementos del conjunto, luego en este caso la búsqueda es
+ 
+\begin_inset Formula $O(\frac{n}{M})$
+\end_inset
+
+ y la inserción es 
+\begin_inset Formula $O(1+\frac{n}{M})$
+\end_inset
+
+.
+ El uso de memoria es el de 
+\begin_inset Formula $M+n$
+\end_inset
+
+ apuntadores y 
+\begin_inset Formula $n$
+\end_inset
+
+ elementos.
+ Así, a más cubetas las operaciones son más rápidas, pero se usa más memoria.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Cerrada
+\series default
+: Los elementos de la tabla son del tipo 
+\begin_inset Formula $T$
+\end_inset
+
+, y si al ir a insertar un elemento 
+\begin_inset Formula $e$
+\end_inset
+
+ en el índice 
+\begin_inset Formula $h(e)$
+\end_inset
+
+ este ya está ocupado se dice que ocurre una 
+\series bold
+colisión
+\series default
+, y se hace una 
+\series bold
+redispersión
+\series default
+: se aplican sucesivamente los elementos de una sucesión de funciones 
+\begin_inset Formula $(h_{n}:T\rightarrow\{0,\dots,M-1\})_{n}$
+\end_inset
+
+ sobre 
+\begin_inset Formula $e$
+\end_inset
+
+ hasta que devuelva un índice de la tabla no ocupado, donde se guarda 
+\begin_inset Formula $e$
+\end_inset
+
+.
+ 
+\begin_inset Newline newline
+\end_inset
+
+Llamamos 
+\series bold
+cadena
+\series default
+ o 
+\series bold
+secuencia de búsqueda
+\series default
+ a la secuencia 
+\begin_inset Formula $h(e),h_{1}(e),\dots$
+\end_inset
+
+ de posiciones recorridas en este proceso.
+ Al consultar un elemento se recorre esta secuencia hasta encontrar el elemento
+ o una celda vacía, que indica que este no está.
+ En la eliminación, para no romper la secuencia, se sustituye el elemento
+ por una marca de eliminado, que se trata como celda libre en la inserción
+ pero no en la búsqueda, o bien se mueven elementos cuya secuencia de búsqueda
+ pase por la posición eliminada.
+\begin_inset Newline newline
+\end_inset
+
+Como la probabilidad de colisión es 
+\begin_inset Formula $\frac{n}{M}$
+\end_inset
+
+ y se ha de encontrar un elemento libre, el coste de una inserción es 
+\begin_inset Formula $O(\frac{1}{1-\frac{n}{M}})$
+\end_inset
+
+, que tiende a infinito cuando 
+\begin_inset Formula $n\rightarrow M$
+\end_inset
+
+, mientras que el de búsqueda es de 
+\begin_inset Formula $O(\frac{1}{1-\frac{n-1}{M}})$
+\end_inset
+
+.
+ El uso de memoria es el de 
+\begin_inset Formula $M$
+\end_inset
+
+ elementos, o el de 
+\begin_inset Formula $M$
+\end_inset
+
+ apuntadores más 
+\begin_inset Formula $n$
+\end_inset
+
+ elementos si se decide que la tabla almacene apuntadores.
+\end_layout
+
+\begin_layout Standard
+Para evitar la pérdida de eficiencia cuando 
+\begin_inset Formula $n$
+\end_inset
+
+ aumenta, la tabla se puede 
+\series bold
+reestructurar
+\series default
+, creando una nueva con distinto 
+\begin_inset Formula $M$
+\end_inset
+
+ y copiando los elementos, por ejemplo cuando 
+\begin_inset Formula $n>2M$
+\end_inset
+
+ en dispersión abierta o cuando 
+\begin_inset Formula $n>\frac{3}{4}M$
+\end_inset
+
+ en cerrada.
+ Para que las tablas de dispersión sean eficientes se debe usar una buena
+ función, que reparta los elementos de la forma más aleatoria pero a la
+ vez sea fácil de calcular.
+\end_layout
+
+\begin_layout Standard
+Métodos para enteros:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+División
+\series default
+: 
+\begin_inset Formula $h(k):=k\mod M$
+\end_inset
+
+, siendo 
+\begin_inset Formula $M$
+\end_inset
+
+ normalmente primo.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Multiplicación
+\series default
+: 
+\begin_inset Formula $h(k):=\lfloor Ck\rfloor\mod M,C\in\mathbb{R}$
+\end_inset
+
+.
+ 
+\begin_inset Newline newline
+\end_inset
+
+Variante: 
+\begin_inset Formula $h(k):=\lfloor\text{d}(\frac{Ak}{W})M\rfloor,\text{mcd}(A,K)=1$
+\end_inset
+
+, donde 
+\begin_inset Formula $\text{d}(x)$
+\end_inset
+
+ es la parte decimal de 
+\begin_inset Formula $x$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Centro del cuadrado
+\series default
+: 
+\begin_inset Formula $h(k):=\lfloor\frac{k^{2}}{C}\rfloor\mod M$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Para secuencias:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Suma
+\series default
+: 
+\begin_inset Formula $h(k):=\sum_{i}x_{i}\mod M$
+\end_inset
+
+.
+ Muchas colisiones.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Suma posicional
+\series default
+: 
+\begin_inset Formula $h(k):=\sum_{i}k^{i}x_{i}\mod M$
+\end_inset
+
+, siendo 
+\begin_inset Formula $k$
+\end_inset
+
+ normalmente primo.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Plegado
+\series default
+ (
+\emph on
+folding
+\emph default
+): 
+\begin_inset Formula $h(k):=\sum_{i=0}^{\lfloor n/p\rfloor}\prod_{j=1}^{p}x_{ip+j}\mod M$
+\end_inset
+
+, tomando 
+\begin_inset Formula $x_{k}=1\forall k>n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Extracción
+\series default
+: 
+\begin_inset Formula $h(k):=x_{n_{1}}\cdots x_{n_{k}}\mod M$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Iterativos
+\series default
+: Tomar un valor inicial y, para cada 
+\begin_inset Formula $x_{i}$
+\end_inset
+
+, en orden, multiplicar por un valor base y combinar el resultado con 
+\begin_inset Formula $x_{i}$
+\end_inset
+
+ mediante alguna operación.
+ Devolver esto módulo 
+\begin_inset Formula $M$
+\end_inset
+
+.
+ Así, la suma posicional toma como valor inicial, base y combinación, respectiva
+mente, 0, 
+\begin_inset Formula $k$
+\end_inset
+
+ y 
+\begin_inset Formula $+$
+\end_inset
+
+; djb2 toma 5381, 33 y 
+\begin_inset Formula $+$
+\end_inset
+
+; djb2a toma 5381, 33 y XOR, y FNV-1 toma 2166136261, 16777619 y XOR.
+\end_layout
+
+\begin_layout Standard
+Funciones de redispersión:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Lineal
+\series default
+: 
+\begin_inset Formula $h_{i}(k):=h(k)+i\mod M$
+\end_inset
+
+.
+ Sufre 
+\series bold
+agrupamiento
+\series default
+: Si se llenan varias cubetas consecutivas y hay colisión, se debe consultar
+ todo el grupo.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Con saltos
+\series default
+: 
+\begin_inset Formula $h_{i}(k):=h(k)+Ci\mod M$
+\end_inset
+
+.
+ Sufre agrupamiento.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Cuadrática
+\series default
+: 
+\begin_inset Formula $h_{i}(k):=h(k)+D(i)\mod M$
+\end_inset
+
+ con
+\begin_inset Formula 
+\[
+D(i)=\begin{cases}
+\left(\frac{i+1}{2}\right)^{2} & \text{si }x\text{ es impar}\\
+-\left(\frac{i}{2}\right)^{2} & \text{si }x\text{ es par}
+\end{cases}
+\]
+
+\end_inset
+
+Funciona cuando 
+\begin_inset Formula $M=4R+3$
+\end_inset
+
+ para algún 
+\begin_inset Formula $R\in\mathbb{N}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Doble
+\series default
+: 
+\begin_inset Formula $h_{i}(k)=h(k)+C(k)i\mod M$
+\end_inset
+
+ para 
+\begin_inset Formula $C:T\rightarrow\{1,\dots,M-1\}$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document
diff --git a/aed1/n3.lyx b/aed1/n3.lyx
new file mode 100644
index 0000000..955b960
--- /dev/null
+++ b/aed1/n3.lyx
@@ -0,0 +1,753 @@
+#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
+\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 Section
+Árboles Trie
+\end_layout
+
+\begin_layout Standard
+Sea 
+\begin_inset Formula $A$
+\end_inset
+
+ un conjunto llamado 
+\series bold
+alfabeto
+\series default
+, un árbol Trie o 
+\series bold
+de prefijos
+\series default
+ es aquél en que la raíz del árbol representa una cadena vacía (
+\begin_inset Formula $()$
+\end_inset
+
+) y un nodo puede tener un hijo etiquetado para cada elemento de 
+\begin_inset Formula $A\cup\{\$\}$
+\end_inset
+
+, con la condición de que un nodo etiquetado con 
+\begin_inset Formula $\$$
+\end_inset
+
+, la 
+\series bold
+marca de fin
+\series default
+, es hoja.
+ Llamamos 
+\series bold
+palabra
+\series default
+ a la tupla de etiquetas desde la raíz hasta un nodo con 
+\begin_inset Formula $\$$
+\end_inset
+
+, sin contarlo.
+ Un 
+\family sans
+ArbolTrie[
+\begin_inset Formula $A$
+\end_inset
+
+]
+\family default
+ (
+\begin_inset Formula $T$
+\end_inset
+
+) es un apuntador a un 
+\family sans
+NodoTrie[
+\begin_inset Formula $A$
+\end_inset
+
+]
+\family default
+ (
+\begin_inset Formula $N$
+\end_inset
+
+), un 
+\family sans
+Diccionario[
+\begin_inset Formula $A$
+\end_inset
+
+,ArbolTrie[
+\begin_inset Formula $A$
+\end_inset
+
+]]
+\family default
+.
+ Operaciones:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+\begin{array}{rrr}
+\mathsf{Consulta}:N\times A\rightarrow T & \mathsf{Inserta}:N\times A\rightarrow N & \mathsf{PonMarca}:N\rightarrow N\\
+(n,x)\overset{x\in Dom(n)}{\mapsto}n(x) & (n,x)\overset{x\notin Dom(n)}{\mapsto}n\cup\{(x,\emptyset)\} & n\mapsto n\cup\{(\$,\emptyset)\}\\
+\\
+\mathsf{QuitaMarca}:N\rightarrow N & \mathsf{HayMarca}:N\rightarrow B\\
+n\mapsto n\backslash\{(\$,\emptyset)\} & n\mapsto(\$,\emptyset)\in n
+\end{array}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Los objetos devueltos por 
+\family sans
+Consulta
+\family default
+ son apuntadores, luego se puede insertar sobre ellos.
+ Otra operación es 
+\family sans
+
+\begin_inset Formula $\mathsf{Inserta}:T\times\bigcup_{n=1}^{\infty}A^{n}\rightarrow T$
+\end_inset
+
+
+\family default
+, que inserta una palabra en un árbol.
+ Podemos implementar un nodo trie:
+\end_layout
+
+\begin_layout Itemize
+Como una tupla de apuntadores en la que cada índice corresponde a un elemento
+ de 
+\begin_inset Formula $A\cup\{\$\}$
+\end_inset
+
+ de forma biyectiva.
+ Permite un acceso a los valores en 
+\begin_inset Formula $O(n)$
+\end_inset
+
+, siendo 
+\begin_inset Formula $n$
+\end_inset
+
+ la longitud de la palabra, pero si 
+\begin_inset Formula $p$
+\end_inset
+
+ es el total de prefijos y 
+\begin_inset Formula $d=|A\cup\{\$\}|$
+\end_inset
+
+, esto requerirá la memoria usada por 
+\begin_inset Formula $(p+1)d$
+\end_inset
+
+ apuntadores (mucha).
+\end_layout
+
+\begin_layout Itemize
+Como una lista enlazada de asociaciones.
+ Presenta un uso de memoria razonable, el usado por 
+\begin_inset Formula $4p+2$
+\end_inset
+
+ apuntadores y 
+\begin_inset Formula $2p+1$
+\end_inset
+
+ caracteres de 
+\begin_inset Formula $A$
+\end_inset
+
+, pero el acceso es 
+\begin_inset Formula $O(ns)$
+\end_inset
+
+ en promedio, siendo 
+\begin_inset Formula $s$
+\end_inset
+
+ la longitud media de las listas (normalmente despreciable).
+\end_layout
+
+\begin_layout Standard
+Si el total de la longitud de las palabras entre el número de prefijos es
+ grande, digamos mayor que 6, las palabras comparten muchos prefijos y suele
+ ser conveniente una representación como tupla, mientras que de lo contrario
+ es mejor usar una lista enlazada.
+\end_layout
+
+\begin_layout Section
+Relaciones de equivalencia
+\end_layout
+
+\begin_layout Standard
+Definimos el TAD 
+\family sans
+RelEquiv[
+\begin_inset Formula $T$
+\end_inset
+
+]
+\family default
+ como el de las relaciones de equivalencia en un 
+\family sans
+Conjunto[
+\begin_inset Formula $T$
+\end_inset
+
+]
+\family default
+.
+ Operaciones:
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\mathsf{Crear}:C\rightarrow R$
+\end_inset
+
+: Crea una relación de equivalencia con 
+\begin_inset Formula $x\approx y:\iff x=y$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\mathsf{Encuentra}:R\times T\rightarrow R$
+\end_inset
+
+: Devuelve un representante canónico de la clase del elemento dado.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\mathsf{Unión}:R\times T\times T\rightarrow R$
+\end_inset
+
+: Hace equivalentes a los dos elementos dados de 
+\begin_inset Formula $T$
+\end_inset
+
+, combinando sus clases de equivalencia.
+ En el análisis posterior supondremos que los elementos dados son representantes
+ canónicos.
+\end_layout
+
+\begin_layout Standard
+Representaciones básicas:
+\end_layout
+
+\begin_layout Itemize
+Mediante una tabla en la que cada índice corresponde a un elemento del conjunto
+ y contiene el índice de su representante canónico.
+ La búsqueda de clase de equivalencia es 
+\begin_inset Formula $O(1)$
+\end_inset
+
+ pero la unión es 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ con 
+\begin_inset Formula $n$
+\end_inset
+
+ el cardinal del conjunto.
+\end_layout
+
+\begin_layout Itemize
+Mediante listas (enlazadas) de clases, con una lista para cada clase cuyo
+ nombre es el del representante canónico.
+ La unión es 
+\begin_inset Formula $O(1)$
+\end_inset
+
+ con una representación adecuada de las listas, pero la búsqueda es 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ con 
+\begin_inset Formula $n$
+\end_inset
+
+ el cardinal del conjunto.
+\end_layout
+
+\begin_layout Standard
+Otra forma es una estructura de árboles disjuntos, una representación por
+ tabla en la que cada índice contiene el índice del padre en su árbol (o
+ un valor especial si es la raíz), cada árbol es una clase de equivalencia
+ y el representante canónico es la raíz del árbol.
+ De esta forma la unión es 
+\begin_inset Formula $O(1)$
+\end_inset
+
+ y la búsqueda es 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ en caso promedio, siendo 
+\begin_inset Formula $n$
+\end_inset
+
+ el cardinal de la clase de equivalencia, aunque sigue siendo 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ en el caso peor.
+ Para evitar esto:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Balanceo
+\series default
+: Al unir los árboles 
+\begin_inset Formula $a$
+\end_inset
+
+ y 
+\begin_inset Formula $b$
+\end_inset
+
+, podemos poner como hijo al menos alto, para lo cual guardamos en la raíz
+ (indicando apropiadamente que es la raíz, por ejemplo, con números negativos)
+ la altura del árbol.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Compresión de caminos
+\series default
+: Al hacer una búsqueda, poner la raíz del árbol como el padre del elemento
+ buscado, y del resto de elementos recorridos.
+\end_layout
+
+\begin_layout Standard
+Así, la búsqueda es 
+\begin_inset Formula $O(1)$
+\end_inset
+
+ en el caso mejor y 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ en el peor.
+\end_layout
+
+\begin_layout Section
+Árboles AVL
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+árbol binario de búsqueda
+\series default
+ (ABB) es un árbol binario en que, para cada nodo, los elementos del subárbol
+ izquierdo son menores que el valor del nodo y los del derecho son mayores.
+ El recorrido ordenado es 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ y la búsqueda e inserción son 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ en el caso promedio, pero 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ en el peor.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+ABB perfectamente balanceado
+\series default
+ es aquel en que, para cada nodo, la cantidad de elementos en sus dos subárboles
+ difiere como mucho en 1.
+ La búsqueda es 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ en el peor caso, pero en este caso la inserción es 
+\begin_inset Formula $O(n)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+árbol balanceado
+\series default
+ o 
+\series bold
+Adelson-Velskii-Landis
+\series default
+ (
+\series bold
+AVL
+\series default
+) es un ABB en que, para cada nodo, la altura de sus subárboles difiere
+ como mucho en 1.
+ La búsqueda es 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ en el caso peor y se hace igual que en un ABB.
+ La inserción y eliminación requieren 
+\series bold
+rebalancear
+\series default
+ el árbol a la vuelta de la llamada recursiva usada para insertar o eliminar
+ el elemento, lo que se hace almacenando la altura de cada nodo en el propio
+ nodo y mediante 
+\series bold
+rotaciones
+\series default
+:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+RSI
+\series default
+ (rotación simple a la izquierda): Sobre un nodo 
+\family typewriter
+A
+\family default
+, el proceso es:
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Formula $\mathtt{B}\leftarrow\mathtt{LEFT[A]}$
+\end_inset
+
+, 
+\begin_inset Formula $\mathtt{LEFT[A]}\leftarrow\mathtt{RIGHT[B]}$
+\end_inset
+
+, 
+\begin_inset Formula $\mathtt{RIGHT[B]}\leftarrow\mathtt{A}$
+\end_inset
+
+,
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Formula $\mathtt{HEIGHT[A]}\leftarrow1+\max\{\mathtt{HEIGHT[LEFT[A]]},\mathtt{HEIGHT[RIGHT[A]]\}}$
+\end_inset
+
+,
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Formula $\mathtt{HEIGHT[B]}\leftarrow1+\max\{\mathtt{HEIGHT[LEFT[B]]},\mathtt{HEIGHT[A]}\}$
+\end_inset
+
+ y 
+\begin_inset Formula $\mathtt{A}\leftarrow\mathtt{B}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+RSD
+\series default
+ (rotación simple a la derecha): Simétrico de RSI.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+RDI
+\series default
+ (rotación doble a la izquierda): Equivale a 
+\begin_inset Formula $\mathtt{RSD(LEFT[A])}$
+\end_inset
+
+ seguido de 
+\begin_inset Formula $\mathtt{RSI(A)}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+RDD
+\series default
+ (rotación doble a la derecha): Simétrico de RDI.
+\end_layout
+
+\begin_layout Standard
+Tras la inserción, si 
+\begin_inset Formula $|\mathtt{HEIGHT[LEFT[A]]}-\mathtt{HEIGHT[RIGHT[A]]}|>1$
+\end_inset
+
+ se rebalancea, con 4 situaciones según cuál de las ramas que hay 2 niveles
+ bajo 
+\family typewriter
+A
+\family default
+ tiene mayor altura (dónde se ha insertado).
+ Si es la rama II (izquierda-izquierda) se hace RSI, para DD se hace RSD,
+ para ID (izquierda y después derecha) se hace RDI y para DI se hace RDD.
+ Ninguno de los casos cambia la altura final del árbol.
+\end_layout
+
+\begin_layout Standard
+Para la eliminación, si el nodo a eliminar es hoja, se elimina directamente.
+ Si solo tiene un hijo, se conecta el padre del nodo eliminado con este
+ hijo.
+ Si tiene dos hijos, se escoge el más a la derecha del subárbol izquierdo,
+ o el más a la izquierda del derecho, para sustituirlo.
+ 
+\end_layout
+
+\begin_layout Standard
+Tras esto puede ser necesario rebalancear, para lo cual hay 3 casos de eliminaci
+ón en el subárbol izquierdo según las alturas 
+\begin_inset Formula $h_{l}$
+\end_inset
+
+ y 
+\begin_inset Formula $h_{r}$
+\end_inset
+
+ de los subárboles respectivos izquierdo y derecho del hijo derecho, más
+ sus 3 casos simétricos de eliminación en el derecho.
+ Así, si 
+\begin_inset Formula $h_{l}=h_{r}$
+\end_inset
+
+ se aplica 
+\begin_inset Formula $RSD$
+\end_inset
+
+ y la altura final del árbol no cambia; si 
+\begin_inset Formula $h_{l}<h_{r}$
+\end_inset
+
+ se aplica 
+\begin_inset Formula $RSD$
+\end_inset
+
+ y la altura disminuye en 1, y si 
+\begin_inset Formula $h_{l}>h_{r}$
+\end_inset
+
+ se hace RDD y la altura disminuye en 1.
+ Así, la inserción y eliminación son 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ en todos los casos.
+\end_layout
+
+\begin_layout Section
+Árboles B
+\end_layout
+
+\begin_layout Standard
+Un árbol B de orden 
+\begin_inset Formula $p$
+\end_inset
+
+ o árbol 
+\begin_inset Formula $p$
+\end_inset
+
+-ario de búsqueda es aquel en que cada nodo está formado por hasta 
+\begin_inset Formula $p-1$
+\end_inset
+
+ claves y 
+\begin_inset Formula $p$
+\end_inset
+
+ hijos (siempre una clave menos que hijos), la raíz no tiene hijos o tiene
+ entre 2 y 
+\begin_inset Formula $p$
+\end_inset
+
+, los nodos internos (ni raíz ni hoja) tienen entre 
+\begin_inset Formula $\lceil\frac{p}{2}\rceil$
+\end_inset
+
+ y 
+\begin_inset Formula $p$
+\end_inset
+
+ hijos y los nodos hoja aparecen todos al mismo nivel (condición de balanceo)
+ y, para cada nodo con 
+\begin_inset Formula $M$
+\end_inset
+
+ hijos, las claves del primer subárbol son todas menores que la primera
+ de este, los del 
+\begin_inset Formula $M$
+\end_inset
+
+-ésimo son mayores que las de la última clave, las del 
+\begin_inset Formula $k$
+\end_inset
+
+-ésimo, 
+\begin_inset Formula $1<k<M$
+\end_inset
+
+, están entre la 
+\begin_inset Formula $(k-1)$
+\end_inset
+
+-ésima clave y la 
+\begin_inset Formula $k$
+\end_inset
+
+-ésima, y las claves de un mismo nodo están ordenadas de menor a mayor.
+ Se usan mucho en bases de datos, ajustando 
+\begin_inset Formula $p$
+\end_inset
+
+ para que cada nodo esté en un bloque de disco minimizando las operaciones
+ de E/S, y existen variantes como 
+\begin_inset Formula $B+$
+\end_inset
+
+, 
+\begin_inset Formula $B^{*}$
+\end_inset
+
+, etc.
+\end_layout
+
+\begin_layout Standard
+La búsqueda es igual que en los árboles binarios y es 
+\begin_inset Formula $O(\frac{\log n}{\log p})$
+\end_inset
+
+, siendo 
+\begin_inset Formula $n$
+\end_inset
+
+ el número de elementos.
+ Para la inserción se empieza buscando el nodo hoja donde se debería colocar
+ la entrada.
+ Si quedan huecos libres, se inserta.
+ Si no, la hoja (que ya tiene 
+\begin_inset Formula $p-1$
+\end_inset
+
+ claves) se divide en 2 hojas con 
+\begin_inset Formula $\lceil\frac{p-1}{2}\rceil$
+\end_inset
+
+ y 
+\begin_inset Formula $\lfloor\frac{p-1}{2}\rfloor$
+\end_inset
+
+ claves, añadiendo, de los 
+\begin_inset Formula $p$
+\end_inset
+
+ valores, el que queda en medio en el nodo padre, repitiendo el proceso
+ en este recursivamente si es necesario.
+\end_layout
+
+\end_body
+\end_document
diff --git a/aed1/n4.lyx b/aed1/n4.lyx
new file mode 100644
index 0000000..db68fda
--- /dev/null
+++ b/aed1/n4.lyx
@@ -0,0 +1,3547 @@
+#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
+\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
+grafo dirigido
+\series default
+ o 
+\series bold
+digrafo
+\series default
+ es un par 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+ formado por un conjunto de 
+\series bold
+vértices
+\series default
+ o 
+\series bold
+nodos
+\series default
+ 
+\begin_inset Formula $V\neq\emptyset$
+\end_inset
+
+ y un conjunto de 
+\series bold
+aristas
+\series default
+ 
+\begin_inset Formula $E\subseteq\{(a,b)\in V\times V:a\neq b\}$
+\end_inset
+
+, mientras que uno 
+\series bold
+no dirigido
+\series default
+ es un par 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+ con 
+\begin_inset Formula $V\neq\emptyset$
+\end_inset
+
+ y 
+\begin_inset Formula $E\subseteq\{x\in{\cal P}(V):|x|=2\}$
+\end_inset
+
+.
+ Algunas definiciones permiten 
+\series bold
+bucles
+\series default
+, aristas de un nodo a sí mismo, y entonces basta que sea 
+\begin_inset Formula $E\subseteq V\times V$
+\end_inset
+
+ para que el grafo sea dirigido o que 
+\begin_inset Formula $E\subseteq\{x\in{\cal P}(V):|x|\in\{1,2\}\}$
+\end_inset
+
+ para que sea no dirigido.
+ En adelante identificamos los grafos no dirigidos 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+ con los correspondientes grafos dirigidos 
+\begin_inset Formula $(V,\bigcup_{\{u,v\}\in E}\{(u,v),(v,u)\})$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+grafo etiquetado
+\series default
+ es una terna 
+\begin_inset Formula $(V,E,\sigma)$
+\end_inset
+
+ donde 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+ es un grafo (dirigido o no) y 
+\begin_inset Formula $\sigma:E\rightarrow X$
+\end_inset
+
+ es una función que relaciona cada arista con una 
+\series bold
+etiqueta
+\series default
+.
+ Un 
+\series bold
+grafo con pesos
+\series default
+ es un grafo etiquetado 
+\begin_inset Formula $(V,E,\sigma)$
+\end_inset
+
+ con 
+\begin_inset Formula $\sigma:E\rightarrow\mathbb{R}$
+\end_inset
+
+.
+ Un grafo es 
+\series bold
+finito
+\series default
+ si 
+\begin_inset Formula $V$
+\end_inset
+
+ lo es.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+subgrafo
+\series default
+ de un grafo 
+\begin_inset Formula $G:=(V,E)$
+\end_inset
+
+ es un grafo 
+\begin_inset Formula $(V',E')$
+\end_inset
+
+ con 
+\begin_inset Formula $V'\subseteq V$
+\end_inset
+
+ y 
+\begin_inset Formula $E'\subseteq E$
+\end_inset
+
+.
+ Un subgrafo de un grafo etiquetado 
+\begin_inset Formula $G:=(V,E,\sigma)$
+\end_inset
+
+ es un grafo etiquetado 
+\begin_inset Formula $(V',E',\sigma|_{E'})$
+\end_inset
+
+ donde 
+\begin_inset Formula $(V',E')$
+\end_inset
+
+ es subgrafo de 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un nodo 
+\begin_inset Formula $u\in V$
+\end_inset
+
+ es 
+\series bold
+adyacente a
+\series default
+ 
+\begin_inset Formula $v\in V$
+\end_inset
+
+ si 
+\begin_inset Formula $(v,u)\in E$
+\end_inset
+
+, y es 
+\series bold
+adyacente de
+\series default
+ 
+\begin_inset Formula $v$
+\end_inset
+
+ si 
+\begin_inset Formula $(u,v)\in E$
+\end_inset
+
+.
+ Un 
+\series bold
+camino
+\series default
+ de 
+\begin_inset Formula $u$
+\end_inset
+
+ a 
+\begin_inset Formula $v$
+\end_inset
+
+ es una secuencia 
+\begin_inset Formula $(w_{1},\dots,w_{q})$
+\end_inset
+
+ de elementos de 
+\begin_inset Formula $V$
+\end_inset
+
+ con 
+\begin_inset Formula $(w_{i-1},w_{i})\in E\forall i\in\{2,\dots,q\}$
+\end_inset
+
+, y es 
+\series bold
+simple
+\series default
+ si para 
+\begin_inset Formula $i,j\in\{1,\dots,q\}$
+\end_inset
+
+ con 
+\begin_inset Formula $i\neq j$
+\end_inset
+
+ e 
+\begin_inset Formula $\{i,j\}\neq\{1,q\}$
+\end_inset
+
+ se tiene 
+\begin_inset Formula $w_{i}\neq w_{j}$
+\end_inset
+
+.
+ Si 
+\begin_inset Formula $w_{1}=w_{q}$
+\end_inset
+
+, el camino es un 
+\series bold
+ciclo
+\series default
+.
+ Un grafo es 
+\series bold
+acíclico
+\series default
+ si no contiene ciclos.
+\end_layout
+
+\begin_layout Standard
+Es 
+\series bold
+conexo
+\series default
+ o 
+\series bold
+conectado
+\series default
+ si existe un camino entre cualquier par de vértices, y es 
+\series bold
+fuertemente conexo
+\series default
+ si además es dirigido.
+ Un 
+\series bold
+componente conexo
+\series default
+ de un grafo (también 
+\series bold
+fuertemente conexo
+\series default
+ si el grafo es dirigido) es un subgrafo conexo que no es subgrafo de ningún
+ otro subgrafo conexo del grafo.
+\end_layout
+
+\begin_layout Standard
+Un grafo es 
+\series bold
+completo
+\series default
+ si existe una arista entre cualquier par de vértices.
+ En un grafo no dirigido 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+, el 
+\series bold
+grado
+\series default
+ de un vértice 
+\begin_inset Formula $v\in V$
+\end_inset
+
+ es el número de arcos adyacentes a él (
+\begin_inset Formula $|\{X\in E:v\in X\}|$
+\end_inset
+
+), mientras que en uno dirigido 
+\begin_inset Formula $(V,A)$
+\end_inset
+
+, definimos el 
+\series bold
+grado de entrada
+\series default
+ de un vértice 
+\begin_inset Formula $v\in V$
+\end_inset
+
+ como 
+\begin_inset Formula $|\{(a,b)\in A:b=v\}|$
+\end_inset
+
+ y el 
+\series bold
+grado de salida
+\series default
+ como 
+\begin_inset Formula $|\{(a,b)\in A:a=v\}|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Operaciones elementales:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula 
+\[
+\begin{array}{rr}
+\mathsf{Vacío}:\rightarrow G & \mathsf{Crear}:\mathbb{N}\rightarrow G\\
+\mapsto(\emptyset,\emptyset) & n\mapsto(\{1,\dots,n\},\emptyset)\\
+\\
+\mathsf{IntertarNodo}:G\times{\cal U}\rightarrow G & \mathsf{InsertarArista}:G\times({\cal U}\times{\cal U})\rightarrow G\\
+((V,E),v)\mapsto(V\cup\{v\},E) & ((V,E),(a,b))\overset{a,b\in V}{\mapsto}(V,E\cup\{e\})\\
+\\
+\mathsf{EliminarNodo}:G\times{\cal U}\rightarrow G & \mathsf{EliminarArista}:G\times({\cal U}\times{\cal U})\rightarrow G\\
+((V,E),v)\mapsto(V\backslash\{e\},\{(a,b)\in E:a,b\neq v\}) & ((V,E),e)\mapsto(V,E\backslash\{e\})\\
+\\
+\mathsf{ConsultarArista}:G\times({\cal U}\times{\cal U})\rightarrow B\\
+((V,E),(a,b))\mapsto(a,b)\in A
+\end{array}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Donde 
+\begin_inset Formula ${\cal U}$
+\end_inset
+
+ es el conjunto de los vértices.
+ Definimos también iteradores sobre los nodos adyacentes a un cierto 
+\begin_inset Formula $v\in V$
+\end_inset
+
+ o adyacentes de este.
+\end_layout
+
+\begin_layout Section
+Representación
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float figure
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\align center
+\begin_inset Graphics
+	filename graph.svg
+	scale 60
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+Grafo no dirigido.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Podemos dibujar un grafo indicando los nodos mediante círculos con etiqueta
+ (o cualquier otra forma) y uniendo con una línea los vértices de cada arista.
+ Si el grafo es dirigido, cada línea es una flecha que apunta al segundo
+ elemento del par.
+ Si es etiquetado, cada línea tendrá su etiqueta indicada.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{sloppypar}
+\end_layout
+
+\end_inset
+
+En un ordenador podemos representar un grafo finito 
+\begin_inset Formula $(V:=\{1,\dots,n\},E)$
+\end_inset
+
+ o 
+\begin_inset Formula $(V:=\{1,\dots,n\},E,\sigma:E\rightarrow X)$
+\end_inset
+
+ mediante:
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{sloppypar}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Matrices de adyacencia
+\series default
+: Matriz 
+\begin_inset Formula $n\times n$
+\end_inset
+
+ de booleanos 
+\begin_inset Formula $((i,j)\in E)_{ij}$
+\end_inset
+
+.
+ Si el grafo es etiquetado, cuando 
+\begin_inset Formula $(i,j)\in E$
+\end_inset
+
+ se añade en la celda la etiqueta, lo que en general se hace tomando un
+ valor 
+\begin_inset Formula $c\notin X$
+\end_inset
+
+ que representa que 
+\begin_inset Formula $(i,j)\notin E$
+\end_inset
+
+ y entendiendo que cualquier otro valor implica 
+\begin_inset Formula $(i,j)\in E$
+\end_inset
+
+.
+ Si el grafo es no dirigido, la matriz es simétrica.
+ Las operaciones son sencillas y el acceso a una arista dada es 
+\begin_inset Formula $O(1)$
+\end_inset
+
+, pero si 
+\begin_inset Formula $|E|\ll n^{2}$
+\end_inset
+
+ (
+\series bold
+matriz escasa
+\series default
+) se usa mucha memoria (
+\begin_inset Formula $O(n^{2})$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Listas de adyacencia
+\series default
+: 
+\begin_inset Formula $n$
+\end_inset
+
+ conjuntos 
+\begin_inset Formula $(C_{1},\dots,C_{n})$
+\end_inset
+
+ (representados como listas enlazadas en una lista contigua) de los que
+ 
+\begin_inset Formula $C_{i}=\{j:(i,j)\in E\}$
+\end_inset
+
+.
+ Si el grafo es etiquetado, 
+\begin_inset Formula $C_{i}=\{(j,\sigma(i,j)):(i,j)\in E\}$
+\end_inset
+
+.
+ Esto es más adecuado si 
+\begin_inset Formula $|E|\ll n^{2}$
+\end_inset
+
+, pues la memoria usada es 
+\begin_inset Formula $O(n+|E|)$
+\end_inset
+
+, pero la representación es más compleja y es ineficiente para encontrar
+ las aristas adyacentes de un cierto nodo.
+\end_layout
+
+\begin_layout Standard
+En adelante, salvo que se indique lo contrario, suponemos un grafo 
+\begin_inset Formula $(V:=\{1,\dots,n\},E,\sigma:E\rightarrow X)$
+\end_inset
+
+, y que las variables en pseudocódigo se inicializan con su valor por defecto.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Para 
+\family sans
+booleano
+\family default
+ es 
+\family sans
+falso
+\family default
+; para 
+\family sans
+entero
+\family default
+, 
+\family sans
+real
+\family default
+ y 
+\begin_inset Formula $[0,+\infty]$
+\end_inset
+
+ es 
+\family sans
+0
+\family default
+; para 
+\family sans
+\series bold
+array
+\family default
+\series default
+s y 
+\family sans
+\series bold
+registro
+\family default
+\series default
+s se inicializa con el valor por defecto de cada campo; para tipos contenedor
+ se crea una instancia vacía, y para 
+\family sans
+RelEquiv
+\family default
+ las clases de equivalencia son de un solo elemento.
+ Las variables del resto de tipos no se inicializan por defecto.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Recorridos
+\end_layout
+
+\begin_layout Standard
+Ambos son 
+\begin_inset Formula $O(|V|^{2})$
+\end_inset
+
+ con matrices de adyacencia y 
+\begin_inset Formula $O(|V|+|E|)$
+\end_inset
+
+ con listas de adyacencia.
+\end_layout
+
+\begin_layout Subsubsection*
+
+\series bold
+Búsqueda primero en profundidad
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ visitado: 
+\series bold
+array
+\series default
+ [1..n]
+\series bold
+ de
+\series default
+ booleano()
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ dfs(u: [1..n])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+visitado[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero; visitar(u)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyacente a u 
+\series bold
+hacer si no
+\series default
+ visitado[v] 
+\series bold
+entonces
+\series default
+ dfs(u)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer si no 
+\series default
+visitado[i] 
+\series bold
+entonces
+\series default
+ dfs(i)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Podemos ver el órden de visita de unos nodos a otros como un 
+\series bold
+árbol de expansión en profundidad
+\series default
+ asociado al grafo o, si aparecen varios árboles, como un 
+\series bold
+bosque de expansión en profundidad
+\series default
+.
+ Para construirlo, hacemos que cada elemento de 
+\family sans
+visitado
+\family default
+ pueda almacenar un valor 
+\family sans
+[1..n]
+\family default
+ indicando el padre del nodo, lo que nos permite encontrar los componentes
+ conexos de un grafo no dirigido.
+ Decimos que 
+\begin_inset Formula $(a,b)\in E$
+\end_inset
+
+ es:
+\end_layout
+
+\begin_layout Itemize
+Un 
+\series bold
+arco de avance
+\series default
+ si 
+\begin_inset Formula $a$
+\end_inset
+
+ es padre a 
+\begin_inset Formula $b$
+\end_inset
+
+ en uno de los árboles del bosque.
+\end_layout
+
+\begin_layout Itemize
+Un 
+\series bold
+arco de retroceso
+\series default
+ si 
+\begin_inset Formula $a$
+\end_inset
+
+ es hijo de 
+\begin_inset Formula $b$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+Un 
+\series bold
+arco de cruce
+\series default
+ si no es de avance ni de retroceso.
+\end_layout
+
+\begin_layout Standard
+Un grafo no dirigido contiene un ciclo si y sólo si algún arco no está en
+ el árbol de expansión.
+ Un grafo dirigido contiene un ciclo si y sólo si algún arco es de retroceso.
+\end_layout
+
+\begin_layout Subsubsection*
+Búsqueda primero en anchura o amplitud
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ visitado: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+C: Cola[[1..n]]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ bfs(u: [1..n])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+visitado[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero; C.meter(u); visitar(u)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+mientras no
+\series default
+ C.vacía 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+v 
+\begin_inset Formula $:=$
+\end_inset
+
+ C.cabeza; C.sacar
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo w adyacente a v 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si no
+\series default
+ visitado[w] 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+visitado[w] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero; C.meter(w); visitar(w)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer si no
+\series default
+ visitado[i] 
+\series bold
+entonces
+\series default
+ bfs(i)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Árboles de expansión mínimos
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+árbol de expansión
+\series default
+ de un grafo no dirigido y conexo es un subgrafo acíclico conexo.
+ El 
+\series bold
+coste
+\series default
+ de un grafo con pesos
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+En general, de un grafo etiquetado por elementos de algún grupo.
+\end_layout
+
+\end_inset
+
+ es la suma de los costes de las aristas.
+ Los siguientes algoritmos obtienen coste del árbol de expansión de coste
+ mínimo de un grafo, donde la variable 
+\family sans
+coste
+\family default
+ contiene dicho coste.
+\end_layout
+
+\begin_layout Subsubsection*
+Algoritmo de Prim
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ visitado: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+C: ColaPrioridad[
+\series bold
+registro
+\series default
+ coste: real; nodo: [1..n]] 
+\begin_inset Formula $//$
+\end_inset
+
+ 
+\emph on
+A menor coste, mayor prioridad
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+coste: real
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ procesar(u: [1..n])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+visitado[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyancente a u con peso w 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si no
+\series default
+ visitado[v] 
+\series bold
+entonces
+\series default
+ C.meter((w, v))
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+procesar(0)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+mientras no
+\series default
+ C.vacía 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+p 
+\begin_inset Formula $:=$
+\end_inset
+
+ C.cabeza; C.sacar
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si no
+\series default
+ visitado(p.nodo) 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+coste 
+\begin_inset Formula $:=$
+\end_inset
+
+ coste 
+\begin_inset Formula $+$
+\end_inset
+
+ p.coste
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+procesar(p.nodo)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Como introducir y extraer elementos de la cola de prioridad es 
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+, siendo 
+\begin_inset Formula $n$
+\end_inset
+
+ el total de elementos de la cola que será proporcional a 
+\begin_inset Formula $|E|$
+\end_inset
+
+, el algoritmo se ejecuta en 
+\begin_inset Formula $O(|E|\log|E|)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsubsection*
+Algoritmo de Kruskal
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ RE: RelEquiv[[1..n]]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+coste: real
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para cada
+\series default
+ arista (u, v) con peso w ordenadas por peso ascendente 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ RE.encuentra(u) 
+\begin_inset Formula $\ne$
+\end_inset
+
+ RE.encuentra(v) 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+coste 
+\begin_inset Formula $:=$
+\end_inset
+
+ coste 
+\begin_inset Formula $+$
+\end_inset
+
+ w
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+RE.unión(u, v)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El algoritmo se ejecuta en 
+\begin_inset Formula $O(|E|\log|E|)$
+\end_inset
+
+, pues es lo que se tarda en ordenar las aristas.
+\end_layout
+
+\begin_layout Section
+Caminos mínimos
+\end_layout
+
+\begin_layout Standard
+El coste de un camino es la suma de los costes de las aristas por las que
+ pasa, y el 
+\series bold
+camino mínimo
+\series default
+ entre dos nodos es el que tiene menor coste de entre los que empiezan en
+ el primero y terminan en el segundo.
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+algoritmo de Dijkstra
+\series default
+ obtiene el mínimo coste del camino de cierto nodo (que supondremos que
+ es el 1) y todos los demás.
+ Para ello trabaja con un conjunto de nodos 
+\series bold
+escogidos
+\series default
+, para los cuales se conoce ya el camino mínimo desde el origen, y otro
+ de 
+\series bold
+candidatos
+\series default
+, de los que no sabemos el camino mínimo salvo si nos restringimos a 
+\series bold
+caminos especiales
+\series default
+, los que pasan solo por nodos escogidos (más él mismo al final).
+ En cada paso el algoritmo toma el nodo candidato con menor distancia al
+ origen, lo añade a los candidatos y recalcula los caminos mínimos del resto
+ de candidatos.
+ Tras repetir esto 
+\begin_inset Formula $n-1$
+\end_inset
+
+ veces, el camino mínimo de cada nodo coincide con su camino especial.
+ La siguiente versión del algoritmo funciona con una matriz de adyacencia
+ 
+\family sans
+C
+\family default
+ que usa 
+\begin_inset Formula $+\infty$
+\end_inset
+
+ para indicar la ausencia de arista:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ coste: 
+\series bold
+array
+\series default
+ [2..n] 
+\series bold
+de 
+\begin_inset Formula $\mathsf{real}\cup\{+\infty\}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+paso: 
+\series bold
+array
+\series default
+ [2..n] 
+\series bold
+de
+\series default
+ [1..n]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+escogido: 
+\series bold
+array
+\series default
+ [2..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 2 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+coste[i] 
+\begin_inset Formula $:=$
+\end_inset
+
+ C[1, i]; paso[i] 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1; escogido[v] 
+\begin_inset Formula $:=$
+\end_inset
+
+ falso
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n
+\begin_inset Formula $-$
+\end_inset
+
+1 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+u 
+\begin_inset Formula $:=$
+\end_inset
+
+ i 
+\series bold
+si no
+\series default
+ escogido[i] 
+\series bold
+minimizando
+\series default
+ coste[i]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+escogido[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyacente a u 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si no
+\series default
+ escogido[v] 
+\series bold
+y
+\series default
+ coste[u] 
+\begin_inset Formula $+$
+\end_inset
+
+ C[u, v] 
+\begin_inset Formula $<$
+\end_inset
+
+ coste[v] 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+coste[v] 
+\begin_inset Formula $:=$
+\end_inset
+
+ coste[u] 
+\begin_inset Formula $+$
+\end_inset
+
+ C[u, v]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+paso[v] 
+\begin_inset Formula $:=$
+\end_inset
+
+ u
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El algoritmo almacena en 
+\family sans
+coste[i]
+\family default
+ el coste del camino mínimo del nodo 
+\family sans
+1
+\family default
+ al 
+\family sans
+i
+\family default
+, y en 
+\family sans
+paso[i]
+\family default
+ el vértice que precede a 
+\family sans
+i
+\family default
+ en este camino, con lo que accediendo sucesivamente podemos encontrar el
+ camino mínimo
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Los caminos mínimos desde un único nodo al resto forman una estructura de
+ árbol.
+\end_layout
+
+\end_inset
+
+.
+ Si solo necesitamos el coste, podemos omitir del algoritmo la obtención
+ del camino.
+\end_layout
+
+\begin_layout Standard
+Esta implementación ejecuta 
+\begin_inset Formula $n-1$
+\end_inset
+
+ veces un código que busca un mínimo de entre 
+\begin_inset Formula $n$
+\end_inset
+
+ valores y actualiza hasta 
+\begin_inset Formula $n$
+\end_inset
+
+ candidatos, luego en total el algoritmo se ejecuta en 
+\begin_inset Formula $O(|V|^{2})$
+\end_inset
+
+.
+ Otra versión con listas de adyacencia consigue llegar a 
+\begin_inset Formula $O(|E|\log|V|)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Para los caminos mínimos entre todos los pares, aplicamos el 
+\series bold
+algoritmo de 
+\color pink
+Floyd
+\series default
+\color inherit
+:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ coste: 
+\series bold
+array
+\series default
+ [1..n, 1..n] 
+\series bold
+de
+\series default
+ 
+\begin_inset Formula $\mathsf{real}\cup\{+\infty\}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+paso: 
+\series bold
+array
+\series default
+ [1..n, 1..n] 
+\series bold
+de
+\series default
+ [1..n]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+coste 
+\begin_inset Formula $:=$
+\end_inset
+
+ C
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ k 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para
+\series default
+ j 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ coste[i, k] 
+\begin_inset Formula $+$
+\end_inset
+
+ coste[k, j] 
+\begin_inset Formula $<$
+\end_inset
+
+ coste[i, j] 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+coste[i, j] 
+\begin_inset Formula $:=$
+\end_inset
+
+ coste[i, k] 
+\begin_inset Formula $+$
+\end_inset
+
+ coste[k, j]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+paso[i, j] 
+\begin_inset Formula $:=$
+\end_inset
+
+ k
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Este algoritmo 
+\begin_inset Formula $O(n^{3})$
+\end_inset
+
+ funciona hallando, en cada iteración del bucle externo, los caminos mínimos
+ pasando por un máximo de 
+\begin_inset Formula $k$
+\end_inset
+
+ vértices.
+ El camino de un vértice 
+\family sans
+a
+\family default
+ a otro 
+\family sans
+b
+\family default
+ distintos se obtiene como el camino mínimo de 
+\family sans
+a
+\family default
+ a 
+\family sans
+paso[a, b]
+\family default
+ y aquí a 
+\family sans
+b
+\family default
+.
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+algoritmo de Warshall
+\series default
+ permite obtener el 
+\series bold
+cierre transitivo
+\series default
+ de un grafo, una matriz de booleanos 
+\begin_inset Formula $(a_{ij}:=\text{existe un camino de \ensuremath{i} a \ensuremath{j}})$
+\end_inset
+
+, y es similar al de Floyd pero cambiando la condición dentro de los bucles
+ por 
+\family sans
+A[i, j] 
+\begin_inset Formula $:=$
+\end_inset
+
+ A[i, j] 
+\series bold
+o
+\series default
+ (A[i, k] 
+\series bold
+y
+\series default
+ A[k, j])
+\family default
+.
+\end_layout
+
+\begin_layout Section
+Componentes fuertemente conexos
+\end_layout
+
+\begin_layout Standard
+Para hallarlos, usamos el 
+\series bold
+algoritmo de Tarjan
+\series default
+:
+\end_layout
+
+\begin_layout Enumerate
+Hacer búsqueda en profundidad del grafo numerando los vértices.
+\end_layout
+
+\begin_layout Enumerate
+Construir el grafo invertido: 
+\begin_inset Formula $(V,E)\mapsto(V,\{(b,a)\}_{(a,b)\in E})$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Hacer búsqueda en profundidad del grafo invertido, empezando en el nodo
+ con mayor número en el paso 1.
+ Mientras queden nodos por visitar, seguir con el nodo no visitado de mayor
+ número.
+\end_layout
+
+\begin_layout Enumerate
+Cada árbol del bosque resultante del paso 3 es un componente fuertemente
+ conexo.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ componentes: Conjunto[Conjunto[entero]]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+tiempo: entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+número: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+enlace: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+pila: Pila[[1..n]]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+apilado: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ tarjan(u: [1..n])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+número[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ tiempo; enlace[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ tiempo
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+tiempo 
+\begin_inset Formula $:=$
+\end_inset
+
+ tiempo 
+\begin_inset Formula $+$
+\end_inset
+
+ 1
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+pila.insertar(u); apilado[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyacente a u 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ número[v] 
+\begin_inset Formula $=$
+\end_inset
+
+ 0 
+\series bold
+entonces
+\series default
+ tarjan(v)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ apilado[v] 
+\series bold
+entonces
+\series default
+ enlace[u] 
+\begin_inset Formula $=$
+\end_inset
+
+ mín(enlace[u], enlace[v])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ enlace[u] 
+\begin_inset Formula $=$
+\end_inset
+
+ visitado[u] 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+s: Conjunto[entero]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+repetir
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+v 
+\begin_inset Formula $:=$
+\end_inset
+
+ pila.tope; pila.sacar; apilado[v] 
+\begin_inset Formula $:=$
+\end_inset
+
+ falso
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+s.inserta(v)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+mientras
+\series default
+ u 
+\begin_inset Formula $\neq$
+\end_inset
+
+ v
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+componentes.inserta(s)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer
+\series default
+ 
+\series bold
+si
+\series default
+ número[i] 
+\begin_inset Formula $=$
+\end_inset
+
+ 0 
+\series bold
+entonces
+\series default
+ conectar(i)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Tras ejecutar el algoritmo, 
+\family sans
+componentes
+\family default
+ es el conjunto de componentes conexos del grafo.
+ Llamamos 
+\series bold
+grafo reducido
+\series default
+ 
+\begin_inset Formula $G_{R}:=(V_{R},E_{R})$
+\end_inset
+
+ de 
+\begin_inset Formula $G:=(V,E)$
+\end_inset
+
+ al grafo dirigido acíclico dado por 
+\begin_inset Formula $V_{R}:=\{\text{componentes fuertemente conexos de \ensuremath{G}}\}$
+\end_inset
+
+ y 
+\begin_inset Formula $E_{R}:=\{(A,B)\in V_{R}:\exists a\in A,b\in B:(a,b)\in E\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Los grafos dirigidos acíclicos sirven, por ejemplo, para representar órdenes
+ parciales.
+ El 
+\series bold
+recorrido en orden topológico
+\series default
+ de un GDA es aquel en que un vértice solo se visita tras visitar todos
+ los nodos adyacentes a él.
+ La 
+\series bold
+numeración en orden topológico
+\series default
+ consiste en numerar los nodos de un GDA de forma que, si 
+\begin_inset Formula $a$
+\end_inset
+
+ es adyacente a 
+\begin_inset Formula $b$
+\end_inset
+
+, el número asignado a 
+\begin_inset Formula $a$
+\end_inset
+
+ es menor que el asignado a 
+\begin_inset Formula $b$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ orden: Pila[[1..n]]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+visitado: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ numerar(u: [1..n])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+visitado[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyacente a u 
+\series bold
+hacer si no 
+\series default
+visitado[v] 
+\series bold
+entonces
+\series default
+ numerar(v)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+orden.insertar(u)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer si no
+\series default
+ visitado[i] 
+\series bold
+entonces
+\series default
+ numerar(i)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Esto guarda un orden topológico en la pila 
+\family sans
+orden
+\family default
+ de forma que el elemento en la cima es el primero, el siguiente el segundo,
+ etc.
+\end_layout
+
+\begin_layout Section
+Grafos eulerianos
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+punto de articulación
+\series default
+ de un grafo no dirigido es un vértice que, al eliminarlo del grafo (junto
+ a las aristas incidentes) se divide un componente conexo en dos o más.
+ Un grafo no dirigido es 
+\series bold
+biconexo
+\series default
+ si no tiene puntos de articulación.
+ Un 
+\series bold
+componente biconexo
+\series default
+ de un grafo es un subgrafo biconexo de este que no es subgrafo de otro
+ subgrafo biconexo.
+\end_layout
+
+\begin_layout Standard
+Un grafo tiene 
+\series bold
+conectividad
+\series default
+ 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+ si es necesario eliminar 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos para que el grafo no sea conexo, por lo que un grafo es biconexo
+ si tiene conectividad 2 o más.
+ El siguiente algoritmo busca puntos de articulación:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ tiempo: entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+raíz: entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+hijosRaíz: entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+número: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+enlace: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+padre: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+articulación: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ puntosArticulación(u: [1..n])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+número[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ tiempo; enlace[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ tiempo
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+tiempo 
+\begin_inset Formula $:=$
+\end_inset
+
+ tiempo 
+\begin_inset Formula $+$
+\end_inset
+
+ 1
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyacente a u 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ número[v] 
+\begin_inset Formula $=$
+\end_inset
+
+ 0 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+padre[v] 
+\begin_inset Formula $:=$
+\end_inset
+
+ u
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ u 
+\begin_inset Formula $=$
+\end_inset
+
+ raíz 
+\series bold
+entonces 
+\series default
+hijosRaíz 
+\begin_inset Formula $:=$
+\end_inset
+
+ hijosRaíz 
+\begin_inset Formula $+$
+\end_inset
+
+ 1
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+puntosArticulación(v)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ enlace[v] 
+\begin_inset Formula $\geq$
+\end_inset
+
+ número[u] 
+\series bold
+entonces
+\series default
+ articulación[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ verdadero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+enlace[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ mín(enlace[u], enlace[v])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+sino si
+\series default
+ v 
+\begin_inset Formula $\neq$
+\end_inset
+
+ padre(u) 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+enlace[u] 
+\begin_inset Formula $:=$
+\end_inset
+
+ mín(enlace[u], número[v])
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+para
+\series default
+ i 
+\begin_inset Formula $:=$
+\end_inset
+
+ 1 
+\series bold
+hasta
+\series default
+ n 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ número[i] 
+\begin_inset Formula $=$
+\end_inset
+
+ 0 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+raíz 
+\begin_inset Formula $:=$
+\end_inset
+
+ i; hijosRaíz 
+\begin_inset Formula $:=$
+\end_inset
+
+ 0; puntosArticulación(i)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+articulación[raíz] 
+\begin_inset Formula $:=$
+\end_inset
+
+ hijosRaíz 
+\begin_inset Formula $>$
+\end_inset
+
+ 1
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+camino de Euler
+\series default
+ es aquel que visita todas las aristas exactamente una vez.
+ Si además es un ciclo, se llama 
+\series bold
+circuito de Euler
+\series default
+.
+ Un grafo no dirigido tiene un circuito de Euler si y sólo si todos los
+ nodos tienen grado par y, tras eliminar los de grado 0, es conexo.
+ El siguiente algoritmo busca un ciclo de Euler, supuesto que exista, a
+ partir del vértice 1, supuesto que cada arista 
+\family sans
+(u, v)
+\family default
+ tiene una marca 
+\family sans
+disponible(u, v)
+\family default
+ que inicialmente está establecida a verdadero.
+ Insertar un elemento en un iterador lo inserta antes del elemento al que
+ apunta y devuelve un iterador al elemento insertado.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Box Boxed
+position "t"
+hor_pos "c"
+has_inner_box 1
+inner_pos "t"
+use_parbox 0
+use_makebox 0
+width "100col%"
+special "none"
+height "1in"
+height_special "totalheight"
+thickness "0.4pt"
+separation "3pt"
+shadowsize "4pt"
+framecolor "black"
+backgroundcolor "none"
+status open
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+var
+\series default
+ ciclo: Lista[entero]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+visitado: 
+\series bold
+array
+\series default
+ [1..n] 
+\series bold
+de
+\series default
+ booleano
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+v: entero
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+j: Iterador[Lista[entero]]
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\series bold
+operación
+\series default
+ circuito(i: Iterador[Lista[entero]], u: entero)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+para cada
+\series default
+ nodo v adyacente a u 
+\series bold
+hacer
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\series bold
+si
+\series default
+ disponible(u, v) 
+\series bold
+entonces
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+disponible(u, v) 
+\begin_inset Formula $:=$
+\end_inset
+
+ falso; disponible(v, u) 
+\begin_inset Formula $:=$
+\end_inset
+
+ falso
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+
+\begin_inset space \qquad{}
+\end_inset
+
+tour(i.insertar(u), v)
+\end_layout
+
+\begin_layout Plain Layout
+
+\family sans
+circuito(iterar(ciclo), 1)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+La idea es partir de un vértice, tomar una arista no visitada, añadirla
+ al ciclo y repetir el proceso partiendo de este nuevo vértice.
+\end_layout
+
+\begin_layout Section
+Otros problemas
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Flujo máximo
+\series default
+: Los nodos representan puntos de una red, las aristas son canales de comunicaci
+ón entre ellos y los pesos de estas son el caudal máximo que puede circular.
+ El problema es hallar el flujo (caudal) máximo que puede haber desde un
+ cierto nodo (origen) a otro (destino), con las restricciones de que la
+ suma del flujo que entra a cada nodo interior (no origen ni destino) debe
+ ser igual a la que sale y el flujo en cada arista no puede superar el máximo.
+\begin_inset Newline newline
+\end_inset
+
+Un posible algoritmo es encontrar un camino del origen al destino, sumar
+ al flujo el mínimo caudal de las aristas que lo forman, restar dicho flujo
+ de estas aristas y repetir hasta que no haya caminos con peso no nulo,
+ si bien esto no garantiza solución óptima.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Ciclo hamiltoniano
+\series default
+ o 
+\series bold
+de Hamilton
+\series default
+: Es un ciclo simple que visita todos los nodos.
+ Determinar si existe en un grafo es un problema NP-completo, y en la práctica
+ se usan 
+\series bold
+heurísticas
+\series default
+, soluciones aproximadas que pueden o no funcionar.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Problema del viajero
+\series default
+ o 
+\series bold
+del viajante
+\series default
+: Dado un grafo no dirigido, completo y con pesos, encontrar el ciclo de
+ menor coste que pase por todos los nodos.
+ También es NP-completo, y podemos usar heurísticas, técnicas probabilísticas,
+ algoritmos genéticos, etc.
+ para obtener aproximaciones.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Coloración de grafos
+\series default
+: Asignar un color o etiqueta a cada nodo de forma que dos nodos unidos
+ por una arista no tengan el mismo color, usando un mínimo número de colores.
+ Es NP-completo.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Isomorfismo
+\series default
+: Dos grafos 
+\begin_inset Formula $G:=(V,E)$
+\end_inset
+
+ y 
+\begin_inset Formula $G':=(V',E')$
+\end_inset
+
+ son 
+\series bold
+isomorfos
+\series default
+ si existe una biyección 
+\begin_inset Formula $\sigma:V\rightarrow V'$
+\end_inset
+
+ tal que 
+\begin_inset Formula $(v,w)\in E\iff(\sigma(v),\sigma(w))\in E'$
+\end_inset
+
+.
+ Determinar si existe es NP-completo.
+\end_layout
+
+\end_body
+\end_document