grafos



GRAFOS, GRAFOS DIRIGIDOS, MAQUINAS

14.1 Introducción

El termino “grafico” tiene varios sentidos en matemáticas. Hemos usado el término “grafica” en el sentido de una relación o de una función. En el presente capitulo introduciremos la palabra “grafo” con un sentido muy especial- al cual ya aludimos en la sección 6-13, cuando hablamos del grafo dirigido de una relación.
En muchaspartes de la ciencia de los computadores y de la informática aparecen los grafos, especialmente los grafos de árbol, y los grafos dirigidos. Los diagramas de flujo, por ejemplo discutidos en el capitulo 5, son grafos dirigidos. Este capitulo tratamos otros ejemplos. Terminamos el capitulo con la definición de una maquina de estado finito, de la cual el computador es un ejemplo.

14.2 Grafos yMultigrafos

Un grafos consta de 2 cosas:
(i) Un conjunto N cuyos elementos se llaman nodos, vértices o puntos.
(ii) Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos o aristas.
Denotamos un grafo por 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 grafospor diagrama en el plano. O sea, cada nodo v de N. se representa por un punto (o pequeño circulo) y cada segmento s= {v1, v2} se representa por una curva que conecta sus terminales v1 y v2
Ejemplo 14.1
(a) La figura 14-1 representa el grafo G con cuatro vértices, A, B, C Y D y cinco segmentos s1= {A, B}, s2= {B, C}, s3= {C, D}, s4= {A, C}, s5= {B, D}. Usualmente denotamos un grafo dibujando sudiagrama en lugar de hacer una lista explicita de sus nodos y segmentos.
(b) La figura 14-1(b) no es un grafo sino un multigrafos. La razón es que s4 y s5 son segmentos múltiples, o sea segmentos que conectan la mismas terminales, y s6 es un lazo, o sea un segmento cuyas terminales son el mismo nodo. La definición no permite ni segmentos múltiples ni lazos. En otras palabras, podemos definir ungrafo como un multigrado sin segmentos múltiples ni lazos. A no ser que se diga otra cosa, los multigrafos considerados en este libro serán finitos. Observe que un grafo con un número finito de nodos automáticamente debe tener un número finito de segmentos y por lo tanto debe ser finito.



Sean G(N, S) un grafo; N’ un subconjunto de N, Y S’ un subconjunto de S cuyas terminales pertenecenN’. Entonces G (N’, S’) es un grafo y se llama un subgrafo de G(N, S). Si S’ contiene todos los segmentos de S cuyas terminales están en N’, entonces G (N’, S’) se llama el subgrafo generado por N’.

14.3 Grado De Un Nodo

Si v es una Terminal de un segmento s, decimos que s es incidente en v. El grado de v, escrito gr (v), es igual al número de segmentos que coinciden en v. (Un nodo de gradocero, o sea un nodo que no pertenece a ningún segmento, se llama un nodo aislado.) Como cada segmento se cuenta dos veces al sumar los grados de los nodos de un grafo, tenemos el siguiente resultado sencillo pero importante.
Teorema 14.1: La suma de los grados de los nodos de un grafo al doble del número de segmento.

Ejemplo 14.2 En la figura 14.1(a)
gr(A)=2gr(B)=3 gr(C)=3 gr(D)=2

La suma de los grados es diez, que, como era se esperar, es el doble del número de segmentos. Se dice que un nodo es par o impar según que su grado sea par o impar. Así A y D son nodos pares, mientras que B y C son nodos impares.

El teorema 14.1 también es cierto para multigrafos si un lazo se cuenta dos veces para el grado de su Terminal. Así, en la figura14.1 (b), tenemos que gr(D)=4, ya que el segmento s6 se cuenta dos veces; así D es un nodo par.

14.4 Conexidad

Un camino en un multigrado consta de una sucesión alternada de nodos y segmentos de la forma v0, e1, v1, e2, v2……….. en-1, vn, en, vn
En donde cada segmento s¡ es incidente en v¡-1 y v1. el numero n de segmentos se llama la longitud del camino. Cuando no hay...