aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--graf/n.lyx14
-rw-r--r--graf/n5.lyx2106
2 files changed, 2120 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..4ae5cf7
--- /dev/null
+++ b/graf/n5.lyx
@@ -0,0 +1,2106 @@
+#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
+\begin_preamble
+\usepackage{amssymb}
+\end_preamble
+\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=(V,E)$
+\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, el mínimo número de conjuntos independientes en que se puede
+ particionar
+\begin_inset Formula $V$
+\end_inset
+
+.
+ Ejemplos: Dado un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\chi(K_{n})=n$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+En adelante
+\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)=0$
+\end_inset
+
+ si y sólo si
+\begin_inset Formula $G$
+\end_inset
+
+ es vacío.
+\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
+\begin_inset Formula $\chi(G)=0$
+\end_inset
+
+, en particular existe
+\begin_inset Formula $f:V\to\emptyset$
+\end_inset
+
+ y
+\begin_inset Formula $V=\emptyset$
+\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
+
+Si
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+,
+\begin_inset Formula $E=\emptyset$
+\end_inset
+
+ y
+\begin_inset Formula $f:V\to\emptyset$
+\end_inset
+
+ es una 0-coloración.
+\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 Formula $\chi(G)=2$
+\end_inset
+
+ si y sólo si
+\begin_inset Formula $G$
+\end_inset
+
+ es bipartito con algún eje.
+\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
+
+La partición
+\begin_inset Formula $\{f^{-1}(0),f^{-1}(1)\}$
+\end_inset
+
+ de
+\begin_inset Formula $V$
+\end_inset
+
+ cumple que eje une dos vértices en el mismo conjunto y por tanto todos
+ unen un vértice de uno con uno del otro.
+ Hay algún eje porque si no lo hubiera sería
+\begin_inset Formula $\chi(G)=1$
+\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
+
+Sea
+\begin_inset Formula $(A,B)$
+\end_inset
+
+ la partición, definimos
+\begin_inset Formula $f(v):=0$
+\end_inset
+
+ para
+\begin_inset Formula $v\in A$
+\end_inset
+
+ y
+\begin_inset Formula $f(v):=1$
+\end_inset
+
+ para
+\begin_inset Formula $v\in B$
+\end_inset
+
+.
+ Entonces
+\begin_inset Formula $f$
+\end_inset
+
+ es una 2-coloración de
+\begin_inset Formula $G$
+\end_inset
+
+, y como hay algún eje,
+\begin_inset Formula $\chi(G)>1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Todo árbol no trivial es bipartito.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Se tiene
+\begin_inset Formula $|V|\geq2$
+\end_inset
+
+ y, sea
+\begin_inset Formula $n(v)$
+\end_inset
+
+ el nivel de un
+\begin_inset Formula $v\in V$
+\end_inset
+
+,
+\begin_inset Formula $f:V\to\{0,1\}$
+\end_inset
+
+ dada por
+\begin_inset Formula $f(v):=[n(v)]_{2}$
+\end_inset
+
+ es una coloración de
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Como
+\begin_inset Formula $G$
+\end_inset
+
+ tiene ejes,
+\begin_inset Formula $\chi(G)>1$
+\end_inset
+
+ y
+\begin_inset Formula $\chi(G)=2$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Sea
+\begin_inset Formula $C_{n}$
+\end_inset
+
+ el anillo o
+\series bold
+ciclo
+\series default
+ de tamaño
+\begin_inset Formula $n$
+\end_inset
+
+,
+\begin_inset Formula
+\[
+\chi(C_{n})=\begin{cases}
+2, & n\text{ par};\\
+3, & n\text{ impar}.
+\end{cases}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Como
+\begin_inset Formula $C_{n}:=(V:=\{0,\dots,n-1\},\{\{i,[i+1]_{n}\}\}_{i\in V})$
+\end_inset
+
+ tiene ejes,
+\begin_inset Formula $\chi(C_{n})\geq2$
+\end_inset
+
+.
+ Para
+\begin_inset Formula $n$
+\end_inset
+
+ par, tomamos
+\begin_inset Formula $f(i)=[i]_{2}$
+\end_inset
+
+.
+ Para
+\begin_inset Formula $n$
+\end_inset
+
+ impar, si
+\begin_inset Formula $C_{n}$
+\end_inset
+
+ fuera bipartito, sea
+\begin_inset Formula $V_{0}$
+\end_inset
+
+ el elemento que contiene al 0 y
+\begin_inset Formula $V_{1}$
+\end_inset
+
+ el que contiene al 1, necesariamente
+\begin_inset Formula $V_{0}\neq V_{1}$
+\end_inset
+
+ y, por inducción, el que contiene a
+\begin_inset Formula $i$
+\end_inset
+
+ es
+\begin_inset Formula $V_{[i]_{2}}$
+\end_inset
+
+, pero entonces
+\begin_inset Formula $0,n-1\in V_{0}\#$
+\end_inset
+
+, con lo que
+\begin_inset Formula $C_{n}$
+\end_inset
+
+ no es bipartito y
+\begin_inset Formula $\chi(C_{n})>2$
+\end_inset
+
+, y tomamos
+\begin_inset Formula $f(i):=[i]_{2}$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,n-1\}$
+\end_inset
+
+ y
+\begin_inset Formula $f(0):=2$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $H$
+\end_inset
+
+ es un subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\chi(H)\leq\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Si
+\begin_inset Formula $f$
+\end_inset
+
+ es una
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G$
+\end_inset
+
+, también es una
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $H$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $K_{q}$
+\end_inset
+
+ es subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)\geq q$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Formula $q=\chi(K_{q})\leq\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $v\in V$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G-v)\in\{\chi(G),\chi(G)-1\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Sean
+\begin_inset Formula $k:=\chi(G-v)$
+\end_inset
+
+ y
+\begin_inset Formula $f:V\to\{1,\dots,k\}$
+\end_inset
+
+ una
+\begin_inset Formula $k$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G-v$
+\end_inset
+
+,
+\begin_inset Formula $k\leq\chi(G)$
+\end_inset
+
+, y como
+\begin_inset Formula $g:V\to\{1,\dots,k+1\}$
+\end_inset
+
+ dada por
+\begin_inset Formula $g(i):=f(i)$
+\end_inset
+
+ para
+\begin_inset Formula $i\neq v$
+\end_inset
+
+ y
+\begin_inset Formula $g(v):=k+1$
+\end_inset
+
+ es una
+\begin_inset Formula $(k+1)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)\leq k+1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $e\in E$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G-e)\in\{\chi(G),\chi(G)-1\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Sea
+\begin_inset Formula $e=:(u,v)$
+\end_inset
+
+, como
+\begin_inset Formula $G-v$
+\end_inset
+
+ es un subgrafo de
+\begin_inset Formula $G-e$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)-1\leq\chi(G-v)\leq\chi(G-e)\leq\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+El coloreado de grafos se puede aplicar a problemas que traten de distribuir
+ productos con ciertas relaciones de incompatibilidad, como en el coloreado
+ de mapas, los sudokus.
+ la asignación de frecuencias en torres de telecomunicaciones, la organización
+ de horarios o la distribución de productos peligrosos en un almacén.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Grafo $G=(V=
+\backslash
+{1,
+\backslash
+dots,n
+\backslash
+},E)$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Coloración $f$ de $G$ que intenta usar pocos colores.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lPara{$i
+\backslash
+gets1$
+\backslash
+KwA $n$}{$f_i
+\backslash
+gets
+\backslash
+min(
+\backslash
+mathbb N
+\backslash
+setminus
+\backslash
+{f_j
+\backslash
+}_{j
+\backslash
+in N(i),j<i})$}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:color"
+
+\end_inset
+
+Algoritmo heurístico para coloreado de grafos.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Podemos colorear un grafo con el algoritmo
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:color"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+, aunque este no garantiza una coloración óptima.
+ Todo grafo
+\begin_inset Formula $G$
+\end_inset
+
+ cumple
+\begin_inset Formula $\chi(G)\leq\Delta_{G}+1$
+\end_inset
+
+, pues el algoritmo siempre elige el menor color de todos salvo un conjunto
+ de tamaño máximo
+\begin_inset Formula $\Delta_{G}$
+\end_inset
+
+.
+ Así, parece preferible al aplicar el algoritmo ordenar los nodos en orden
+ decreciente de sus grados.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de Brooks:
+\series default
+ Si un grafo conexo
+\begin_inset Formula $G$
+\end_inset
+
+ no es completo ni un ciclo de longitud impar, entonces
+\begin_inset Formula $\chi(G)\leq\Delta_{G}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Grafos críticos
+\end_layout
+
+\begin_layout Standard
+Un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ es
+\series bold
+crítico
+\series default
+ o
+\series bold
+
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+-crítico
+\series default
+ si todo subgrafo estricto
+\begin_inset Formula $H$
+\end_inset
+
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ cumple
+\begin_inset Formula $\chi(H)<\chi(G)$
+\end_inset
+
+,
+\series bold
+crítico por ejes
+\series default
+ si para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+ es
+\begin_inset Formula $\chi(G-e)<\chi(G)$
+\end_inset
+
+ y
+\series bold
+crítico por vértices
+\series default
+ si para todo
+\begin_inset Formula $v\in V$
+\end_inset
+
+ es
+\begin_inset Formula $\chi(G-v)<\chi(G)$
+\end_inset
+
+.
+
+\end_layout
+
+\begin_layout Standard
+Entonces:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico si y sólo si es crítico por ejes y por vértices.
+\end_layout
+
+\begin_layout Enumerate
+Si
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico por ejes y no tiene nodos aislados, es crítico por vértices.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Para
+\begin_inset Formula $v\in V$
+\end_inset
+
+,
+\begin_inset Formula $v$
+\end_inset
+
+ es adyacente a algún
+\begin_inset Formula $e\in E$
+\end_inset
+
+ y
+\begin_inset Formula $G-v$
+\end_inset
+
+ es un subgrafo de
+\begin_inset Formula $G-e$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico por ejes si y sólo si
+\begin_inset Formula $\chi(G-e)=\chi(G)-1$
+\end_inset
+
+ para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Formula $\chi(G-e)\in\{\chi(G),\chi(G)-1\}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $|V|\geq2$
+\end_inset
+
+,
+\begin_inset Formula $G$
+\end_inset
+
+ tiene un subgrafo crítico
+\begin_inset Formula $H$
+\end_inset
+
+ tal que
+\begin_inset Formula $\chi(G)=\chi(H)$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Si todos los vértices de
+\begin_inset Formula $G$
+\end_inset
+
+ son aislados,
+\begin_inset Formula $\chi(G)=1$
+\end_inset
+
+ y tomamos un subgrafo unipuntual, que es crítico.
+ En otro caso, sea
+\begin_inset Formula $G_{0}$
+\end_inset
+
+ el subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+ generado por sus vértices no aislados, claramente
+\begin_inset Formula $G_{0}$
+\end_inset
+
+ tiene orden al menos 2 y
+\begin_inset Formula $\chi(G_{0})=\chi(G)$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $G_{0}$
+\end_inset
+
+ es crítico, tomamos
+\begin_inset Formula $G_{0}$
+\end_inset
+
+, y de lo contrario existe
+\begin_inset Formula $e_{1}\in E$
+\end_inset
+
+ con
+\begin_inset Formula $\chi(H_{0}:=G_{0}-e_{1})=\chi(G_{0})$
+\end_inset
+
+.
+ Si todos los vértices de
+\begin_inset Formula $H_{0}$
+\end_inset
+
+ son aislados,
+\begin_inset Formula $\chi(H_{0})=\chi(G)=1$
+\end_inset
+
+ y tomamos un subgrafo unipuntual, y de lo contrario llamamos
+\begin_inset Formula $G_{1}$
+\end_inset
+
+ al subgrafo de
+\begin_inset Formula $H_{0}$
+\end_inset
+
+ generado por sus vértices no aislados y repetimos.
+ Como
+\begin_inset Formula $E$
+\end_inset
+
+ es finito, en algún momento se llega a un subgrafo crítico.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+Como
+\series bold
+teorema
+\series default
+, si
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico,
+\begin_inset Formula $\chi(G)\leq\delta_{G}+1$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Sea
+\begin_inset Formula $k:=\chi(G)$
+\end_inset
+
+ y supongamos
+\begin_inset Formula $k>\delta_{G}+1$
+\end_inset
+
+, con lo que
+\begin_inset Formula $\delta_{G}\leq k-2$
+\end_inset
+
+.
+ Sea
+\begin_inset Formula $v\in V$
+\end_inset
+
+ con
+\begin_inset Formula $o(v)=\delta_{G}$
+\end_inset
+
+, debe ser
+\begin_inset Formula $\chi(G-v)=\chi(G)-1$
+\end_inset
+
+, pero en una coloración de
+\begin_inset Formula $G-v$
+\end_inset
+
+, como
+\begin_inset Formula $v$
+\end_inset
+
+ es de menor grado, se usan a lo sumo
+\begin_inset Formula $\delta_{G}\leq k-2$
+\end_inset
+
+ colores para los vértices adyacentes a
+\begin_inset Formula $v$
+\end_inset
+
+ en
+\begin_inset Formula $G$
+\end_inset
+
+, luego hay un color que no se ha utilizado y, pintando
+\begin_inset Formula $v$
+\end_inset
+
+ de ese color, tenemos una
+\begin_inset Formula $(k-1)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Polinomio cromático
+\end_layout
+
+\begin_layout Standard
+Dados un grafo
+\begin_inset Formula $G$
+\end_inset
+
+ y
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+, llamamos
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ al número de
+\begin_inset Formula $k$
+\end_inset
+
+-coloraciones de
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Así:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $p(G,k)=0$
+\end_inset
+
+ para todo
+\begin_inset Formula $k<\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $p(K_{n},k)=k(k-1)\cdots(k-n+1)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Sea
+\begin_inset Formula $P_{n}$
+\end_inset
+
+ la malla unidimensional o
+\series bold
+cadena
+\series default
+ de
+\begin_inset Formula $n$
+\end_inset
+
+ nodos,
+\begin_inset Formula $p(P_{n},k)=k(k-1)^{n-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Si
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+,
+\begin_inset Formula $u,v\in E$
+\end_inset
+
+ y
+\begin_inset Formula $e:=(u,v)$
+\end_inset
+
+, llamamos
+\begin_inset Formula $G+e:=(V,E\cup\{e\})$
+\end_inset
+
+, y si
+\begin_inset Formula $e\in E$
+\end_inset
+
+ llamamos
+\series bold
+grafo contraído
+\series default
+ a
+\begin_inset Formula
+\[
+G\circ e:=((V\setminus\{u,v\})\amalg\{*\},E_{V\setminus\{u,v\}}\cup(\{(*,i)\}_{(u,i)\in E}\cup\{(*,i)\}_{(v,i)\in E})\setminus\{u,v\}).
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de reducción:
+\series default
+ Sean
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ un grafo y
+\begin_inset Formula $e\notin E^{\complement}$
+\end_inset
+
+, entonces
+\begin_inset Formula $p(G;k)=p(G+e;k)+p(G\circ e;k)$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Sea
+\begin_inset Formula $(u,v):=e$
+\end_inset
+
+, las coloraciones
+\begin_inset Formula $f$
+\end_inset
+
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ con
+\begin_inset Formula $f(u)=f(v)$
+\end_inset
+
+ son precisamente las de
+\begin_inset Formula $G\circ e$
+\end_inset
+
+ haciendo
+\begin_inset Formula $f(*):=f(u)=f(v)$
+\end_inset
+
+, y las coloraciones
+\begin_inset Formula $f$
+\end_inset
+
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ con
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ son precisamente las de
+\begin_inset Formula $G+e$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Así, dados un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ y un
+\begin_inset Formula $e\in E$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)=p(G-e;k)-p(G\circ e;k)$
+\end_inset
+
+, pues
+\begin_inset Formula $G=(G-e)+e$
+\end_inset
+
+ y
+\begin_inset Formula $G\circ e=(G-e)\circ e$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Newpage pagebreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+polinomio cromático
+\series default
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ es
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ respecto a
+\begin_inset Formula $k$
+\end_inset
+
+, y si
+\begin_inset Formula $G$
+\end_inset
+
+ tiene grado
+\begin_inset Formula $n\geq1$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ es un polinomio de grado
+\begin_inset Formula $n$
+\end_inset
+
+ en que el coeficiente de grado
+\begin_inset Formula $n$
+\end_inset
+
+ es 1, el término independiente es 0 y los coeficientes de los términos
+ intermedios son enteros y se alternan en signo.
+
+\series bold
+Demostración:
+\series default
+ Sean
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+,
+\begin_inset Formula $n=|V|$
+\end_inset
+
+ y
+\begin_inset Formula $m=|E|$
+\end_inset
+
+, y hacemos inducción sobre
+\begin_inset Formula $(n,m)$
+\end_inset
+
+ (el orden lexicográfico es un buen orden en
+\begin_inset Formula $\mathbb{N}^{*}\times\mathbb{N}$
+\end_inset
+
+).
+ Para
+\begin_inset Formula $m=0$
+\end_inset
+
+, todos los puntos son aislados y
+\begin_inset Formula $p(G;k)=k^{n}$
+\end_inset
+
+, y para
+\begin_inset Formula $n=1$
+\end_inset
+
+ es
+\begin_inset Formula $m=0$
+\end_inset
+
+.
+ Sean ahora
+\begin_inset Formula $n>1$
+\end_inset
+
+ y
+\begin_inset Formula $m>0$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)=p(G-e;k)-p(G\circ e;k)$
+\end_inset
+
+, pero
+\begin_inset Formula $G-e$
+\end_inset
+
+ tiene un eje menos y
+\begin_inset Formula $G\circ e$
+\end_inset
+
+ tiene un nodo menos, luego ambos cumplen la hipótesis y como
+\begin_inset Formula $p(G-e;k)$
+\end_inset
+
+ tiene orden
+\begin_inset Formula $n$
+\end_inset
+
+ y
+\begin_inset Formula $p(G\circ e;k)$
+\end_inset
+
+ tiene orden
+\begin_inset Formula $n-1$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ cumple la hipótesis.
+\end_layout
+
+\begin_layout Section
+Planaridad
+\end_layout
+
+\begin_layout Standard
+Un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ es
+\series bold
+planar
+\series default
+ si existen
+\begin_inset Formula $f:V\to\mathbb{R}^{2}$
+\end_inset
+
+ inyectiva y
+\begin_inset Formula $g:E\to[0,1]\to\mathbb{R}^{2}$
+\end_inset
+
+ tales que, para
+\begin_inset Formula $e:=(u,v)\in E$
+\end_inset
+
+,
+\begin_inset Formula $g(e)$
+\end_inset
+
+ es una curva regular simple que une
+\begin_inset Formula $f(u)$
+\end_inset
+
+ y
+\begin_inset Formula $f(v)$
+\end_inset
+
+, no pasa por ningún vértice en
+\begin_inset Formula $(0,1)$
+\end_inset
+
+ y no corta a
+\begin_inset Formula $g(e')$
+\end_inset
+
+ para ningún otro
+\begin_inset Formula $e'\in E$
+\end_inset
+
+ en
+\begin_inset Formula $(0,1)$
+\end_inset
+
+.
+ En tal caso
+\begin_inset Formula $(V,E,f,g)$
+\end_inset
+
+ es un
+\series bold
+grafo plano
+\series default
+ o
+\series bold
+grafo embutido
+\series default
+, con imagen
+\begin_inset Formula $f(V)\cup\bigcup_{e\in E}g(e)([0,1])$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Una
+\series bold
+estrella
+\series default
+ es un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ donde existe un
+\begin_inset Formula $v\in V$
+\end_inset
+
+ con
+\begin_inset Formula $v\in e$
+\end_inset
+
+ para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+.
+ Toda estrella es planar.
+ En efecto, sea
+\begin_inset Formula $G=(\{v_{0},\dots,v_{n}\},E)$
+\end_inset
+
+ la estrella y
+\begin_inset Formula $v_{0}\in e$
+\end_inset
+
+ para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+, llamamos
+\begin_inset Formula $f(v_{0}):=0$
+\end_inset
+
+,
+\begin_inset Formula $f(v_{i}):=(\cos i/n,\sin i/n)$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,n\}$
+\end_inset
+
+ y
+\begin_inset Formula $g(v_{0},v_{i})(t):=tv_{i}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Sea
+\begin_inset Formula $(V,E,f,g)$
+\end_inset
+
+ un grafo plano con imagen
+\begin_inset Formula $I$
+\end_inset
+
+, llamamos
+\series bold
+caras
+\series default
+ a las componentes conexas de
+\begin_inset Formula $\mathbb{R}^{2}\setminus I$
+\end_inset
+
+ y
+\series bold
+cara externa
+\series default
+ a la no acotada, que es única por ser
+\begin_inset Formula $I$
+\end_inset
+
+ compacto y por tanto acotado.
+
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+contorno
+\series default
+ de una cara es la imagen de un subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+, que existe, cuya imagen con las mismas
+\begin_inset Formula $f$
+\end_inset
+
+ y
+\begin_inset Formula $g$
+\end_inset
+
+ es la frontera de la cara.
+ Los ejes y vértices de dicho subgrafo son
+\series bold
+incidentes
+\series default
+ a la cara.
+ Un puente es incidente a una sola cara, y un eje no de corte es incidente
+ a 2 caras.
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+grado
+\series default
+ de una cara
+\begin_inset Formula $F$
+\end_inset
+
+,
+\begin_inset Formula $d(F)$
+\end_inset
+
+, es el número de ejes incidentes a ella, contando los puentes dos veces.
+ Así, si
+\begin_inset Formula $F$
+\end_inset
+
+ es el conjunto de caras del grafo,
+\begin_inset Formula $\sum_{f\in F}d(f)=2|E|$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $|V|\geq3$
+\end_inset
+
+,
+\begin_inset Formula $d(f)\geq3$
+\end_inset
+
+ para todo
+\begin_inset Formula $f\in F$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Identidad de Euler:
+\series default
+ Si
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo plano conexo con
+\begin_inset Formula $n$
+\end_inset
+
+ vértices,
+\begin_inset Formula $m$
+\end_inset
+
+ ejes y
+\begin_inset Formula $c$
+\end_inset
+
+ caras,
+\begin_inset Formula $n-m+c=2$
+\end_inset
+
+, y en particular todos los grafos planos de un mismo grafo planar conexo
+ tienen el mismo número de caras.
+
+\series bold
+Demostración:
+\series default
+ Si
+\begin_inset Formula $c=1$
+\end_inset
+
+,
+\begin_inset Formula $G$
+\end_inset
+
+ no tiene ciclos y, al ser conexo, es un árbol, luego
+\begin_inset Formula $m=n-1$
+\end_inset
+
+ y
+\begin_inset Formula $n-m+c=2$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $c\geq2$
+\end_inset
+
+, supuesto esto probado para
+\begin_inset Formula $c-1$
+\end_inset
+
+ caras, sean
+\begin_inset Formula $C$
+\end_inset
+
+ un ciclo de
+\begin_inset Formula $G$
+\end_inset
+
+ y
+\begin_inset Formula $e$
+\end_inset
+
+ un eje de
+\begin_inset Formula $C$
+\end_inset
+
+,
+\begin_inset Formula $e$
+\end_inset
+
+ no es un puente, luego es incidente a 2 caras y se puede ver que
+\begin_inset Formula $G-e$
+\end_inset
+
+ tiene
+\begin_inset Formula $c-1$
+\end_inset
+
+ caras y es conexo, de modo que por hipótesis
+\begin_inset Formula $n-(m-1)+(c-1)=2$
+\end_inset
+
+ y
+\begin_inset Formula $n-m+c=2$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+En un grafo plano con al menos 3 nodos, toda cara tiene al menos 3 ejes
+ incidentes.
+ Entonces, si
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo planar conexo con
+\begin_inset Formula $n\geq3$
+\end_inset
+
+ vértices y
+\begin_inset Formula $m$
+\end_inset
+
+ nodos,
+\begin_inset Formula $m\leq3n-6$
+\end_inset
+
+, y si además
+\begin_inset Formula $G$
+\end_inset
+
+ no contiene a
+\begin_inset Formula $K_{3}$
+\end_inset
+
+,
+\begin_inset Formula $m\leq2n-4$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Sean
+\begin_inset Formula $F$
+\end_inset
+
+ el conjunto de las caras de un grafo plano arbitrario de
+\begin_inset Formula $G$
+\end_inset
+
+ y
+\begin_inset Formula $c:=|F|$
+\end_inset
+
+, como toda
+\begin_inset Formula $f\in F$
+\end_inset
+
+ cumple
+\begin_inset Formula $d(f)\geq3$
+\end_inset
+
+,
+\begin_inset Formula $3c\leq\sum_{f\in F}d(f)=2m$
+\end_inset
+
+, y como
+\begin_inset Formula $c=2-n+m$
+\end_inset
+
+, tenemos
+\begin_inset Formula $6-3n+3m\leq2m$
+\end_inset
+
+ y
+\begin_inset Formula $m\leq3n-6$
+\end_inset
+
+.
+ Si una cara
+\begin_inset Formula $f$
+\end_inset
+
+ cumple
+\begin_inset Formula $d(f)=3$
+\end_inset
+
+, se puede ver que el único grafo con 3 ejes contando doblemente los puentes
+ es
+\begin_inset Formula $K_{3}$
+\end_inset
+
+, por lo que si
+\begin_inset Formula $G$
+\end_inset
+
+ no contiene a
+\begin_inset Formula $K_{3}$
+\end_inset
+
+,
+\begin_inset Formula $d(f)\geq4$
+\end_inset
+
+,
+\begin_inset Formula $4c=8-4n+4m\leq2m$
+\end_inset
+
+ y
+\begin_inset Formula $2m\leq4n-8$
+\end_inset
+
+, por lo que
+\begin_inset Formula $m\leq2n-4$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Por ejemplo, el
+\series bold
+grafo de Petersen
+\series default
+,
+\begin_inset Formula $(\{a_{i},b_{i}\}_{i=0}^{4},\{(a_{i},b_{i}),(a_{i},a_{[i+1]_{5}}),(b_{i},b_{[i+2]_{5}})\}_{i=0}^{4})$
+\end_inset
+
+, no es un grafo planar, pues tiene 5 nodos y 15 ejes, y
+\begin_inset Formula $15>9=3\cdot5-6$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Sea
+\begin_inset Formula $F$
+\end_inset
+
+ una cara de un grafo plano con
+\begin_inset Formula $d(F)\geq4$
+\end_inset
+
+, el grafo tiene dos vértices no adyacentes en
+\begin_inset Formula $F$
+\end_inset
+
+.
+ Entonces, si
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo planar maximal con al menos 3 nodos, toda cara
+\begin_inset Formula $F$
+\end_inset
+
+ de todo grafo plano de
+\begin_inset Formula $G$
+\end_inset
+
+ cumple
+\begin_inset Formula $d(F)=3$
+\end_inset
+
+.
+ Como
+\series bold
+teorema
+\series default
+, todo grafo planar maximal con
+\begin_inset Formula $n$
+\end_inset
+
+ nodos tiene exactamente
+\begin_inset Formula $3n-6$
+\end_inset
+
+ ejes.
+\end_layout
+
+\begin_layout Standard
+Dado un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+, una
+\series bold
+subdivisión de un eje
+\series default
+
+\begin_inset Formula $e=(u,v)\in E$
+\end_inset
+
+ es el grafo
+\begin_inset Formula $(V\amalg\{*\},E\setminus e\cup(u,*)\cup(*,v))$
+\end_inset
+
+, y una
+\series bold
+subdivisión
+\series default
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ es el resultado de realizar subdivisiones sucesivas sobre
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de Kuratowski:
+\series default
+ Un grafo es planar si y sólo si no contiene como subgrafo ninguna subdivisión
+ de
+\begin_inset Formula $K_{5}$
+\end_inset
+
+ ni de
+\begin_inset Formula $K_{3,3}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de los 4 colores:
+\series default
+ Todo grafo planar es 4-coloreable.
+\end_layout
+
+\end_body
+\end_document
generated by cgit v1.2.3 (git 2.46.0) at 2025-10-27 21:16:58 +0000