Esdd en c

Unidad 5.- Grafos y árboles

GRAFOS. INTRODUCCIÓN El “gráfico” tiene varios sentidos en matemáticas. Hemos usado el término “gráfica” en el sentido de una relación o de una función. En muchas partes de la ciencia de las computadoras y de la informática aparecen los grafos, especialmente los grafos de árbol, y los grafos dirigidos. Los diagramas de flujo, por ejemplo, son grafos dirigidos.GRAFOS Y MULTIGRADOS. Un grafo consta de dos cosas: Un conjunto N cuyos elementos se llaman nodos, puntos o vértices. Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos, aristas o arcos. Denotaremos 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} Representaremos de una manera natural losgrafos por diagramas en el plano. O sea, cada nodo v de N se representa por un punto (o pequeño círculo) y cada segmento s = {v1, v2} se representa por una curva que conecta sus terminales v1 y v2. EJEMPLO. La figura 1.1 representa el 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 su diagramaen lugar de hacer una lista explicita de sus nodos y segmentos. La figura 1.2 no es un grafo sino un multigrafo. La razón es que s4 y s5 son segmentos múltiples, o sea segmentos que conectan las mismas terminales, y s6 es un lazo, o sea, un segmento cuyas terminales son el mismo nodo. La definición de grafo no permite ni segmentos múltiples o multisegmentos, ni lazos. En otras palabras, podemosdefinir un grafo como un multigrafo sin multisegmentos ni lazos.
s6
A D A

s1 s2 s3

D

s4 s1 s5 s3

s4
B

s2 Figura 1.1

C

B

C

s5 Figura 1.2
1

Ing. Miguel Ángel Durán Jacobo

Unidad 5.- Grafos y árboles

A s2

s1 s3

Lazo

D

Segmento, arco, arista

s4 B
Nodo, punto, vértice

C s5
Segmento múltiple o multisegmento

Figura 1.3

GRADO DE UN NODO Siv es una terminal de un segmento s, decimos que s es incidente en v. El grado de v, escrito gr(v), es igual al numero de segmentos que inciden en v. (Un nodo de grado cero, o sea un nodo que no pertenece a ningún segmento, se llama nodo aislado) Teorema 1.- La suma de los grados de los nodos de un grafo es igual al doble del número de segmentos. EJEMPLO Observemos que en la figura 1.1 se tienenpor cada vértice, los grados siguientes: gr(A) = 2, gr(B) = 3, gr(C) = 3, gr(D) = 2 La suma de los grados es 10, que, como dice el Teorema 1, es el doble 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. Ahora veamos que en la figura 1.2 se tienen por cada vértice, los grados siguientes: gr(A) = 2,gr(B) = 3, gr(C) = 3, gr(D) = 4 Como podremos notar el grado de D no es 2, sino 4, ya que el lazo se cuenta 2 veces para el grado de su nodo. Y la suma de los grados del nodo es 12, y una vez más se comprueba el Teorema 1, donde el grado total corresponde al doble de sus segmentos.
Ing. Miguel Ángel Durán Jacobo 2

Unidad 5.- Grafos y árboles

VALENCIA La valencia es la suma de los grados delos nodos. De la figura 1.1 A 2 B 3 C 3 D 2 Val 10 De la figura 1.2 A B C D Val 2 3 3 4 12

Tipo de grafos.

Grafos simples: Se dice que es grafo simple cuando no hay más de una arista entre un par de nodos (no más de de una arista dirigida en el caso de gráficas dirigidas). Ejemplos

a

Ing. Miguel Ángel Durán Jacobo

3

Unidad 5.- Grafos y árboles

Grafos bipartitos: Se dice que esun grafo bipartito G cuando un conjunto de nodos N se puede particionar en dos subconjuntos P y Q tales que, cada segmento de G, conecta un nodo de P con un nodo Q. Ejemplos:

P

Q

P

Q

P

Q

Un grafo bipartito completo, es cuando cada nodo de P está conectado con cada nodo de Q. En los ejemplos anteriores, todos son grafos bipartitos completos. Grafos Completos: Un grafo...