Download V. Grafos

V. Grafos
Módulo 5
Definiciones y ejemplos.
DEF. Sea V un conjunto finito no vacío, y sea
El par (V, E) es llamada entonces grafo dirigido en V, donde
V es el conjunto de vértices o nodos y E es su conjunto de
arcos dirigidos. Denotamos a dicho grafo como G = (V, E).
Si se desconoce la dirección de los arcos tenemos también
que G = (V, E). Pero, en este caso, E es un conjunto de
pares no ordenados de elementos de V, y a G se le
denomina grafo no dirigido.
Módulo 5
Grafo dirigido
e
b
a
c
d
V = {a, b, c, d, e}
E = {(a,a), (a,b), (a,d), (b,c)}
El arco (b,c) es incidente con los vértices b y c.
El nodo b es adyacente a c.
El nodo c es adyacente de b.
El nodo b es el origen de (b,c).
El nodo c es el vértice terminal.
El nodo e es un vértice aislado.
(a,a) es el ejemplo de un lazo.
Módulo 5
DEF. Sean x, y un par de vértices no necesariamente
diferentes en el grafo no dirigido G = (V, E). Un camino x-y
en G es una secuencia finita alternante libre de lazos:
x = x0, e1, x1, e2, x2, e3, …, en-1, xn-1, en, xn = y
de vértices y arcos de G, iniciando en el vértice x y
terminando en el vértice y e involucrando los n arcos
e ={e1, e2,, e3, …, en-1, en}.
La longitud de este camino es n: el número de arcos en el
camino.
Si n = 0, no hay arcos, x = y, y tenemos un camino trivial.
Cualquier camino x-y donde x = y y n > 1 se llama camino
cerrado. De otra manera es un camino abierto.
Si el grafo es no dirigido, el camino x-y es igual al camino yx.
Módulo 5
DEF. Consideremos cualquier camino x-y en un grafo no
dirigido G = (V, E).
a) Si ningún arco en el camino x-y se repite, entonces el
camino es una pista x-y. Una pista cerrada x-x es llamada
circuito.
b) Si ningún vértice del camino x-y se presenta más de una
vez, entonces el camino es llamado via x-y. Si x = y, se
emplea el término ciclo para describir dicha via cerrada.
Módulo 5
TEOREMA.
Sea G = (V, E) un grafo no dirigido, con
Si existe una via en G de a a b, entonces, existe una pista
en G de a a b.
Módulo 5
DEF. Sea G = (V, E) un grafo no dirigido. Lo llamamos G
conectado si existe una via entre dos vértices distintos de G.
Un grafo que no está conectado es llamado grafo
desconectado.
Un grafo no dirigido G = (V, E) está desconectado si y solo si V
puede particionarse en al menos dos subconjunto V1 y V2 tal
que no existe un arco en E de la forma {x, y} donde
Un grafo está conectado si y solo si tiene un solo componente.
Módulo 5
DEF. Para cualquier grafo G = (V, E), el número de
componentes de G está denotado por k(G).
Ejemplo:
k(G) = 1
k(G) = 2
Grafos conectados
Grafos desconectados
Módulo 5
DEF. Sea V un conjunto finito no vacío. Se dice que el par
(V, E) determina un multigrafo G con el conjunto de vértices
V y el conjunto de arcos E, si para algunos
existen dos o más arcos en E de la forma:
a) (x, y) para un multigrafo dirigido.
b) {x, y} para un multigrafo no dirigido.
En cualquier caso, se escribe G = (V, E) para designar el
multigrafo, al igual que con los grafos.
Módulo 5
Subgrafos complementos e isomorfismos.
DEF. Si G = (V, E) es un grafo, entonces G1 = (V1, E1) es
llamado subgrafo si
y
donde cada arco
de E1 es incidente con dos vértices de V1.
DEF. Dado un grafo dirigido o no dirigido G = (V, E), sea
G1 = (V1, E1) un subgrafo de G. Si V1 = V, entonces G1 es
llamado subgrafo confinante de G.
Módulo 5
DEF. Sea G = (V, E) un grafo dirigido o no dirigido. Si
el subgrafo de G inducido por U es el
subgrafo cuyo conjunto de vértices es U y el cual contiene
todos los arcos (posibles) de G de la forma:
a) (x, y) para
si G es dirigido.
b) {x, y} para
si G es no dirigido.
Denotamos a este subgrafo por
.
Un subgrafo G1 del grafo G = (V, E) es llamado subgrafo
inducido si existe
donde
Módulo 5
DEF. Sea v un vértice en un grafo G = (V, E) dirigido o no
dirigido. El subgrafo de G denotado G – v tiene el conjunto de
vértices V1 = V – {v} y el conjunto de arcos
donde E1 contiene todos los arcos de E excepto los que son
incidentes en el vértice v.
Por lo tanto G – v es el subgrafo de G inducido por V1.
Similarmente, sea e un arco del grafo G = (V, E) dirigido o no
dirigido. El subgrafo G – e = {V1, E1} tiene al conjunto de
arcos E1 = E – {e} y el conjunto de vértices no cambia, esto
es V1 = V.
Módulo 5
DEF. Sea V el conjunto de n vértices. El grafo completo en V,
denotado Kn, es un grafo no dirigido libre de lazos, donde
, a ≠ b, existe un arco {a, b}.
DEF. Sea G un grafo no dirigido libre de lazos con n vértices.
El complemento de G, denotado G’, es el subgrafo de Kn que
consiste de los n vértices de G y todos los arcos que no están
en G. (Si G = Kn, G’ es un grafo con n vértices y sin arcos. Este
grafo es llamado grafo nulo)
Módulo 5
DEF. Sea G1 = (V1, E1) y G2 = (V2, E2) dos grafos no dirigidos.
Una función f: V1 → V2 es llamada un isomorfismo de grafos si:
a) f es uno a uno y es suprayectiva.
b)
si y solo si
Cuando dicha función existe, G1 y G2 son llamados grafos
isomorfos.
Módulo 5
Pistas y circuitos de Euler.
DEF. Sea G un grafo o multigrafo no dirigido. Para cada
vértice v de G, el grado de v, deg (v), es el número de arcos
en G que son incidentes con v. Aquí un lazo en un vértice v
es considerado como dos arcos incidentes en v.
Módulo 5
TEOREMA. Si G = (V, E) es un grafo o multigrafo no dirigido,
entonces
COROLARIO. Para cualquier grafo o multigrafo no dirigido, el
número de vértices de grado impar debe ser par.
Un grafo o multigrafo no dirigido donde cada vértice tiene el
mismo grado es llamado grafo regular.
Si deg(v) = k,
el grafo es llamado k-regular.
Módulo 5
DEF. Sea G= (V, E) un grafo o multigrafo no dirigido sin
vértices aislados. Entonces G se dice que tiene un circuito de
Euler si existe un circuito (no repite arco) en G que pasa por
cada arco del grafo exactamente una vez.
Si existe una pista abierta (no repite arco) de a a b en G y
esta pista pasa por cada arco de G exactamente una vez, la
pista se dice que es una pista de Euler.
Módulo 5
TEOREMA. Sea G = (V, E) un grafo o multigrafo no dirigido sin
vértices aislados. Entonces G tiene un circuito de Euler si y
solo si G está conectado y todos los vértices de G tiene grado
par.
COROLARIO. Si G es un grafo o multigrafo no dirigido sin
vértices aislados, entonces podemos construir una pista de
Euler en G si y solo si G está conectado y tiene exactamente
dos vértice de grado impar.
Módulo 5
DEF. Sea G = (V, E) un grafo o multigrafo dirigido. Para cada v
que pertenece a V:
a) El grado de entrada de v es el número de arcos en G que
inciden en v y esto se denota id(v).
b) El grado de salida de v es el número de arcos en G que son
incidentes de v y esto se denota od(v).
Si el grafo o multigrafo dirigido tiene uno o más lazos, cada
lazo en un vértice dado v contribuye en una unida para cada id
(v) o od(v).
Módulo 5
TEOREMA. Sea G = (V, E) un grafo o multigrafo dirigido sin
vértices aislados. El grafo G tiene un circuito de Euler dirigido
si y solo si G está conectado e id(v) = od(v) para todo v que
pertecene a V.
Grafos planos.
Módulo 5
DEF. Un grafo o multigrafo G es llamado plano si G puede
dibujarse en el plano con sus arcos intersectando sólo a los
vértices de G. Dicho dibujo es llamado instancia de G en el
plano.
DEF. Un grafo G = (V, E) es llamado bipartito si
con
y todo arco de G es de la forma {a, b} con
y
. Si cada vértice en V1 está unido con todo vértice en
V2 tenemos un grafo bipartito completo. En este caso
|V1| = m, |V2| = n, el grafo es denotado Km,n.
Módulo 5
DEF. Sea G = (V, E) un grafo no dirigido libre de lazos donde E
≠ Ø. Una subdivisión elemental de G resulta cuando un arco e
= {u, w} es removido de G y entonces se agregan los arcos {u,
v}, {v, w} se agregan a G – e, donde
Los grafos no dirigidos libres de lazos G1 y G2 se llaman
homeomórficos si son isomórficos o si ambos pueden
obtenerse de un mismo grafo no dirigido libre de lazos G a
través de una serie de subdivisiones elementarias.
Módulo 5
TEOREMA. Sea G = (V, E) un grafo plano conectado o
multigrafo con |V| = v y |E| = e. Sea r el número de regiones
en el plano determinado por una instancia plana de G; una de
estas regiones tiene un área infinita y es llamada región
infinita. Entonces v – e + r = 2.
COROLARIO. Sea G = (V, E) un grafo plano conectado libre
de lazos con |V| = v y |E| = e > 2, y r regiones. Entonces
3r ≤ 2e y e ≤ 3v – 6.
Módulo 5
Vías y ciclos de Hamilton.
DEF. Si G = (V, E) es un grafo o multigrafo con |V| ≥ 3, se dice
que G es un ciclo de Hamilton si existe un ciclo (no repite
nodo) en G que contiene a todo vértice de V. Una vía de
Hamilton es una vía, y no un ciclo, en G que contiene cada
vértice.
Módulo 5
TEOREMA. Sea G = (V, E) un grafo libre de lazos con
|V| = n ≥ 2. Si deg(x) + deg(y) ≥ n – 1,
entonces G tiene una via de Hamilton.
COROLARIO. Sea G = (V, E) un grafo libre de lazos con n ≥ 2
vértices. Si deg(v) ≥ (n-1)/2,
. Entonces G tiene una via
de Hamilton.
Módulo 5
TEOREMA. Sea G = (V, E) un grafo no dirigido libre de lazos
con |V| = n ≥ 3. Si deg(x) + deg(y) ≥ n ,
no adyacentes,
entonces G tiene un ciclo de Hamilton.
COROLARIO. Sea G = (V, E) un grafo no dirigido libre de
lazos con |V| = n ≥ 3, y si deg(v) ≥ n/2,
. Entonces G
tiene un ciclo de Hamilton.
COROLARIO. Sea G = (V, E) un grafo no dirigido libre de
lazos con |V| = n ≥ 3, y si |E| ≥ C(n-1, 2) + 2, entonces G tiene
un ciclo de Hamilton.
VI. Árboles
1. Introducción a los árboles.
DEF. Un árbol es un grafo no dirigido, conectado y sin
ciclos. Un árbol necesariamente es un grafo simple.
DEF. Un grafo sin ciclos, no conectado se denomina
bosque y tiene la propiedad de que cada uno de sus
componentes (conectado) es un árbol.
Módulo 6
TEOREMA. Un grafo no dirigido es un árbol si y solo si hay
un camino único entre cada par de nodos.
DEF. Un árbol con raíz es un árbol en el que uno de sus
nodos ha sido designado como la raíz y todos los arcos
están orientados de modo que se alejan de la raíz.
Módulo 6
DEF. Un árbol con raíz se llama árbol m-ario si todos los
vértices internos tienen, a lo sumo, m hijos. El árbol se
llama m-ario completo si todo vértice interno tiene
exactamente m hijos. Un árbol m-ario con m = 2 se llama
árbol binario.
DEF. Un árbol m-ario exhaustivo es un árbol m-ario
completo que tiene todas las hojas al mismo nivel.
Árboles como modelos.
Hidrocarburos saturados y árboles.
Representación de organizaciones.
Sistemas de ficheros en computadoras.
Procesadores en paralelo conectados en árbol.
Módulo 6
2. Propiedades de los árboles.
TEOREMA. Un árbol de n nodos tiene n-1 arcos.
TEOREMA. Un árbol m-ario completo con i vértices
internos tiene n = mi + 1 nodos.
Módulo 6
TEOREMA. Un árbol m-ario completo con
a) n nodos tiene i = (n - 1)/m nodos internos y
l = [(m - 1)n + 1]/m hojas.
b) i nodos internos tiene n = mi + 1 nodos y
l = (m - 1)i + 1 hojas.
c) l hojas tiene n = (ml - 1)/(m - 1) nodos e
i = (l - 1)/(m - 1) nodos internos.
Módulo 6
TEOREMA. Un árbol m-ario de altura h tiene, a lo sumo, mh
hojas.
COROLARIO. Si un árbol m-ario de altura h tiene l hojas,
entonces
. Si un árbol m-ario es completo y
equilibrado entonces
Supongamos que alguien comienza una cadena de cartas. A cada persona que
recibe una de esa cartas se le pide que la envie a otras cuatro. Algunas personas
lo hacen, pero otras no. ¿Cuántas personas han leido la carta, incluyendo a la
primera persona, si nadie recibe más de una carta y si la cadena finaliza después
de que 100 personas que han visto la carta no hayan enviado ninguna?
¿Cuántas personas en enviaron la carta?
Calcular el nivel de cada nodo en el árbol
raíz mostrado. ¿Cuál es su altura?