Grafos y multigrafos

UNIDAD 5: GRAFOS Y MULTIGRAFOS.

INTRODUCCION

El termino “grafico” tiene varios sentidos en matemáticas. Hemos usado el término “grafica” en el sentido de una relación o una función. En el presente trabajo introduciré la palabra “grafo” con un sentido muy especial.

En muchas partes de la ciencia de los computadores y de la informática aparecen los grafos, especialmente los grafos de árboly los grafos dirigidos.

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:

Un conjunto V de puntos llamados vértices o nodos.

“Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos estánrelacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos”.

GRAFOS Y MULTIGRAFOS

Un grafo consta de dos cosas:

a) Un conjunto N cuyos elementos se llaman nodos, vértices o puntos.

b) Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos o aristas.

Denotamos un grafopor G(N, S) cuando queremos destacar las dos partes de G.

Los nodos u y v se llaman adyacentes si hay un segmento {u, v}.

Representamos de una manera natural los grafos por diagramas en el plano. O sea, cada nodo u de N se representa por un punto (o pequeño circulo) y cada segmento s= {[pic] } se representa por una curva que conecta sus terminales [pic].

Ejemplos:

a) La figura (a)representa el grafo G con cuatro vértices, A, B, C, y D, y cinco segmentos [pic]= {A, B}, [pic]= {B, C}, [pic] = {C, D}, [pic] = {A, C}, [pic]= {B, D}. Usualmente denotamos un grafo dibujando su diagrama en lugar de hacer una lista explicita de sus nodos y segmentos.

b) La figura (b) no es un grafo sino un multígrafo. La razón es que [pic] y [pic]son segmentos múltiples, o sea segmentosque conectan las mismas terminales, y [pic] es un lazo, o sea, un segmento cuyas terminales son el mismo nodo. La definición de grafo no permite ni segmentos múltiples ni lazos. En otras palabras, podemos definir un grafo como un multígrafo sin segmentos múltiples ni lazos. A no ser que se diga otra cosa, los multígrafos considerados serán finitos. Observe que un grafo con un número finito denodos automáticamente debe tener un número finito de segmentos y por lo tanto debe ser finito.

TIPOS DE GRAFOS

Existen dos tipos de grafos los no dirigidos y los dirigidos.

• No dirigido: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas.

• Dirigido: Si las aristas tienen asociadauna dirección (las aristas (x, y) y (y, x) no son equivalentes) diremos que el grafo es dirigido

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido. Por el contrario, la red de carreteras de un país representa en general un grafo no dirigido, puesto que una misma carretera puede ser recorrida en ambossentidos.

DIRIGIDO NO DIRIGIDO

TIPOS ESPECIALES DE GRAFOS

a) Un grafo regular de grado n si todos sus vértices tienen grado n.
Grafos regulares de grado 2

Grafos regulares de grado 3

b) Un grafo completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices

c) Un ciclo siV = {v1, v2,. . . vn}, n __ 3, y E = {(v1, v2), (v2, v3), .. , (vn, v1)} . Se denota por Cn al ciclo de n vértices

[pic]

d) Una rueda si V = {v0, v1, v2, . . . vn} , n n _ 3 , y E = {(v1, v2), (v2, v3), . . . , (vn, v1), {(v1, v0), (v2, v0), . . . , (vn, v0) } . Se denota por Wn a la rueda de n+1 vértices.

e) Un cubo si sus vértices y aristas están relacionados como los de...