Inicio tema 5

2 files changed, 341 insertions, 0 deletions

diff --git a/graf/n.lyx b/graf/n.lyx
index 1c55080..2e3d8e1 100644
--- a/graf/n.lyx
+++ b/graf/n.lyx
@@ -257,5 +257,19 @@ filename "n4.lyx"
 
 \end_layout
 
+\begin_layout Chapter
+Coloración de grafos
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n5.lyx"
+
+\end_inset
+
+
+\end_layout
+
 \end_body
 \end_document
diff --git a/graf/n5.lyx b/graf/n5.lyx
new file mode 100644
index 0000000..d4c4f1b
--- /dev/null
+++ b/graf/n5.lyx
@@ -0,0 +1,327 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Dado un grafo 
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ y un conjunto 
+\begin_inset Formula $S$
+\end_inset
+
+ de 
+\series bold
+colores
+\series default
+, llamamos 
+\series bold
+coloración
+\series default
+ (
+\series bold
+propia por vértices
+\series default
+) de 
+\begin_inset Formula $G$
+\end_inset
+
+ a una función 
+\begin_inset Formula $f:V\to S$
+\end_inset
+
+ con 
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ para 
+\begin_inset Formula $(u,v)\in E$
+\end_inset
+
+.
+ Si 
+\begin_inset Formula $|S|=k$
+\end_inset
+
+, 
+\begin_inset Formula $f$
+\end_inset
+
+ es una 
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-coloración
+\series default
+, y 
+\begin_inset Formula $G$
+\end_inset
+
+ es 
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-coloreable
+\series default
+ si admite una 
+\begin_inset Formula $k$
+\end_inset
+
+-coloración.
+ Una 
+\begin_inset Formula $k$
+\end_inset
+
+-coloración 
+\begin_inset Formula $f$
+\end_inset
+
+ induce una partición de 
+\begin_inset Formula $V$
+\end_inset
+
+ en subconjuntos independientes, dados por 
+\begin_inset Formula $f^{-1}(c)$
+\end_inset
+
+ para 
+\begin_inset Formula $c\in S$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+número cromático
+\series default
+ de un grafo 
+\begin_inset Formula $G$
+\end_inset
+
+, 
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+, es el menor 
+\begin_inset Formula $k$
+\end_inset
+
+ tal que 
+\begin_inset Formula $G$
+\end_inset
+
+ es 
+\begin_inset Formula $k$
+\end_inset
+
+-coloreable.
+ Ejemplos:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\chi(K_{n})=n$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+En adelante el grafo a considerar será 
+\begin_inset Formula $(V,E)$
+\end_inset
+
+ y 
+\begin_inset Formula $f$
+\end_inset
+
+ será una coloración.
+ Entonces, en este caso, 
+\begin_inset Formula $f(i)\neq f(j)$
+\end_inset
+
+ para 
+\begin_inset Formula $i\neq j$
+\end_inset
+
+, luego 
+\begin_inset Formula $f$
+\end_inset
+
+ es inyectiva y su imagen tiene cardinal 
+\begin_inset Formula $|V|=n$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\chi(G)=1$
+\end_inset
+
+ si y sólo si 
+\begin_inset Formula $G$
+\end_inset
+
+ es no vacío y sin ejes.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si existiera 
+\begin_inset Formula $(u,v)\in E$
+\end_inset
+
+ sería 
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ y por tanto 
+\begin_inset Formula $|f(V)|\geq2\#$
+\end_inset
+
+, y si fuera 
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+ sería 
+\begin_inset Formula $|f(V)|=0\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Claramente 
+\begin_inset Formula $|f(V)|\geq1$
+\end_inset
+
+, pero podemos tomar todos los nodos del mismo color.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document