• Author / Uploaded
• Brayan CCh

Citation preview

ÁLGEBRA

MAT 100

TEORÍA DE GRAFOS

Teoría de Grafos: Definición: Sea V un conjunto finito no vacío y sea E  V  V . El par (V , E) es un grafo (sobre V)

Ej.

Donde V: Conjunto de vértices o nodos E: Conjunto de aristas o arcos

a

V  {a,b,c} E  {(a,b),(a,c),(c,c)}

b

Se denota: G  (V , E) Grafo simple. o simplemente grafo es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Multígrafo. o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, dos nodos pueden estar conectados por más de una arista.

c

a

c

b

d

Multígrafo con múltiples aristas

Se llama orden del grafo G al número de vértices: V Grafo no dirigido: o grafo propiamente dicho, Cuando no importa la dirección de las aristas. Ejemplo: V  {a, b, c, d,e}

Grafo dirigido: o Dígrafo, Dada una arista (a, b), a es su nodo inicial y b su

E  {(a, b),(a, c),(b,c),(b, d),(c, d),(d,e)}

nodo final. Ejemplo: V  {a,b,c,d}

Donde se puede decir: (a, b)  (b, a) (par no

E  {(a,b),(a,c),(b,c),(c,d)}  Conjunto

ordenado)

de pares ordenados. c

a b

d

d

e

Grafo ponderado: Aquel que da el peso a las aristas de un G, en algún caso vértices. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.

Roger Miranda O.

c

a

b

c a

5

e

3

4 d

4 b

a

3

5 6

b

3 c 3 4

d

Página - 1 -

TEORÍA DE GRAFOS

b

ÁLGEBRA

e

c

a

f g

d Ejemplos: podrían ser. C. simple: a  e  a  d  c  e Ciclo: c  c  c  d  e  c Recorrido: a  g  a d c e d  g

Circuito: a  a  a  b  c  d  a c c  c d e  f e c

MAT 100

Camino: es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. (a e) Dos vértices pueden estar conectados por varios caminos. Camino simple es aquel que no repite vértices ni aristas en su recorrido. Ciclo: Camino simple cerrado (x x). Recorrido: Si no se repite ninguna arista en el camino x y. Un recorrido x x cerrado es un circuito

La Longitud de un camino es n, el número de aristas que usa dicho camino (Si n = 0, no existen aristas y el camino se denomina trivial). Si el camino vuelve a pasar por una arista, se contará las veces que la recorramos.

Así el camino: a  b  c  a  b  d es de longitud 5

Distancia entre vértices: Camino de longitud mínima entre dos vértices.

Un Bucle o lazo en es una arista que conecta al mismo vértice consigo mismo. Un grafo simple no puede tener bucles.

c

a b

e d

Resumen: Vértice(s) repetidos(s) Sí Sí Sí Sí No No

Página - 2 -

Arista(s) repetidas(s) Sí Sí No

Abierto Sí

Sí Sí Sí

No No No

Cerrado

Sí Sí

Nombre Camino Camino (cerrado) Recorrido Circuito Camino simple Ciclo

Roger Miranda O.

ÁLGEBRA

MAT 100

TEORÍA DE GRAFOS

4

3 2

Camino Euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez (puede repetir vértices).

5

7

1

6

8 9

10

Camino Hamiltoniano es el que recorre todos los vértices exactamente una vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

Grado

o

valencia:

grad(v)

Es

el

número de aristas incidentes a un vértice. Para un grafo con bucles, éstos son contados por dos. En un dígrafo, podemos distinguir el grado saliente (el número de aristas que dejan el vértice) y el grado entrante (el número de aristas que entran en un vértice). El grado de un vértice sería la suma de ambos números.

Por Ej:

a

c

b grad (a)  2 grad (b)  1 grad (c)  3 n

Teorema: En un grafo G  (V , E) se cumple que la sumatoria de los grados de los vértices es el doble del número de lados.

 grad(v )  2 E i

i 1

Para el Ej.:

grad(a)  grad(b)  grad(c)  2  3 6=6

Grafo Regular: Es un grafo donde cada vértice tiene el mismo grado. Un grafo regular con vértices de grado k es llamado grafo k-regular o grafo regular de grado k. Por ejemplo, con 6 vértices se pueden formar:

Grafo 0-regular Roger Miranda O.

Grafo 1-regular

Grafo 2-regular

Grafo 3-regular Página - 3 -

TEORÍA DE GRAFOS

ÁLGEBRA

MAT 100

En todo grafo k-regular se cumple: k V  2 E k  3 Por Ej. Para el grafo 3-regular:  ⟹ 3  6  2  9 ⟹ 18  18 V  6  E  9

Grafo completo: Es un grafo simple donde cada par de vértices está conectado n(n  1) por una arista. Un grafo completo de n vértices tiene aristas, y se nota 2 Kn . Es un grafo regular con todos sus vértices de grado n 1. Algunos ejemplos: K2; E  1

K3 ; E  3

K4;

K 6 ; E  15

E 6

Grafo complemento: o inverso de un grafo es un grafo G  (V , E)

G  (V , E ) con el mismo conjunto de vértices. Para obtener el complemento de un grafo, se deben completar todas las aristas faltantes para hacerlo completo, y quitar todas las aristas del grafo G original.

G

Grafo conexo: se dice conexo si, para cualquier par de vértices u y v en G, existe al menos un camino simple de u a v.

a

G

⟶

Grafo no conexo o disconexo a b

f

e

e

c

b

f

d

c d Subgrafos: Dado un grafo G1  (V1, E1) Un subgrafo es cualquier grafo

G2  (V2 , E2 ) tal que V2  V1  E2  E1 e

e

e

a

c

a

c

a

b

d

b

d

b

G1  (V1, E1) Página - 4 -

G2  (V2 , E2 )

G3  (V3 , E3 ) Roger Miranda O.

ÁLGEBRA

MAT 100

TEORÍA DE GRAFOS

Grafo bipartito: Es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos A y B, de manera que las aristas sólo pueden conectar vértices de un conjunto U con vértices delVotro. 





K m ,n

 





Árbol: es un grafo conexo simple acíclico en el que cualesquiera dos vértices están conectados por exactamente un camino. Bosque: es una unión disjunta de árboles Estrella: Sk es el grafo



BV

B



A













Y se cumple: Nº Vértices = m + n; Nº Aristas = mn. A U 



Grafo bipartito completo: es aquel grafo bipartito en el que todos los vértices de la partición A están conectados a todos los vértices de la partición B y viceversa. Si: | A |  m; | B |  n se denota como: K m ,n

Árbol

Bosque

Estrella S6

bipartito completo K 1,k Plano

Grafo Plano: es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce. Todo grafo plano puede ser dibujado sobre la esfera.

No plano

K5

⟶

K 3,3

K4

Todo grafo plano presenta regiones R:

R

R a a

b

R1

R2

a

R3

R2 R1

R4

R=1 R=1 R=2 R=4 Teorema: Sea G  (V , E) un grafo o multígrafo plano conexo y sea R el número de regiones formadas. Entonces se cumple la fórmula de Euler: V  E R 2 Roger Miranda O.

Página - 5 -

TEORÍA DE GRAFOS

R3

R2

R4  464  2

R8  4  10  8  2

d

b

22

22 Ej. De C 6 , se ve que es: • 2-regular • Euleriano • Hamiltoniano •V  E

Grafo Ciclo: o simplemente ciclo es un grafo que se asemeja a un polígono de n lados, se denota C n . El primer vértice aparece dos veces como principio y fin del camino. Matriz de Adyacencia: Matriz cuadrada que representa el número de aristas entre cada par de nodos. a b c d

c

a

d

a 0 b 1 c 0  d 0

b

Para un grafo dirigido. c a

d b

MAT 100

Ej.: en los siguientes grafos se pueden distinguir: V 4 V 4 a c E 6 E  10

R4

R1

ÁLGEBRA

1 1 0 0 1 0 0 0 1  0 0 1

Lista de Adyacencia: es una representación de todas las aristas partiendo de un vértice mediante una lista. Se parte anotando todos los vértices a • b • c b • a • c c • d d • d

a b c d

a 0 b 1 c 1  d 0

1 1 0 0 1 1 1 0 1  1 1 0

a b c d

Para un grafo no dirigido resulta una matriz simétrica c 0 2 0 1  2 0 3 0  d   0 3 0 0  a   b 1 0 0 2

b a a b

• • • •

e 4 a

c 3

6

4

b

Multígrafo, el bucle se cuenta por 2

3

5

c c b c

• • • •

d

0 6  0  0 0 

• •

d d

0 5 0 4 0 0 4 0 0 0 0 3  0 3 0 0 0 0 0 0

Grafo ponderado.

Subdivisión elemental: Resulta al eliminar una arista a  (u, v) y obtener u

Página - 6 -

e  (u, w) i  (w, v) a

v

⟹

u

e

w

i

v

Roger Miranda O.

ÁLGEBRA

MAT 100

TEORÍA DE GRAFOS

Homeomorfismo de grafos: Dos grafos G1 y G2 son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas. Todos los grafos ciclo de n vértices son homeomorfos entre sí. Por Ej. Partimos de: C 4, si se hace una subdivisión elemental se obtiene C 5 y nuevamente con una subdivisión elemental se logra C 6

C5 ⟹

homeomorfo ⟹ a C 6 ya que se

⟹

C4

es

C5

C6

obtuvieron de C 4

Isomorfismo de grafos: Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2. G1 G2 Isomorfismo entre G1 y G2 a

g

b

h

c

i

d

j

2

1 5

f (a)  1 f (b)  6

6

f (c)  8 f (d)  3

8

7

f (g)  5 3

4

f (h)  2 f (i )  4 f (j )  7

A pesar de su diferente aspecto, los dos grafos que se muestran son isomorfos. Debe verificarse grad(a)  grad(1)...grad(j )  grad(7) Y se debe mantener la adyacencia entre vértices, es decir, si existe un vértice entre c y h deberá existir entre 8 y 2. Y así sucesivamente. Ej.: Definamos las siguientes funciones:

m

n

r

s

g(m)  r

h(m)  s

g(n)  s

h(n)  r

g(p)  t

h(p)  u

g(q)  u

p

q

GA

Roger Miranda O.

t

GB

u

g es uno a uno (biyectiva) pero: m q es arista de GA y r u no lo es de GB ∴g no define un isomorfismo

h(q)  t En este caso se puede verificar la correspondencia de aristas. ∴h es isomorfismo de grafos

Página - 7 -