Grafos

Unidad III. Grafos Teoría de grafos 2-2010

Definiciones, representaciones, tipos de grafos y árboles UNEFA-Núcleo Mérida

Grafo  Un grafo G  es un  par  G=(V , E) donde  V es un conjunto  finito  de  elementos  llamados vértices o nodos  y  E un conjunto  de pares no ordenados de vértices  que se denominan aristas o arcos. Propiedades •El número de vértices de un grafo G, es el orden del grafo. • El número de aristas de un grafo G, es su tamaño. • Dos aristas son independientes si no tienen vértices en común. • Si una arista relaciona dos vértices (u,v) se dicen que u y v son vértices  adyacentes. • Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una  arista donde el nodo inicial y el nodo final coinciden. Ejemplo:  Para   el   siguiente   grafo,   determine   el   número  de   vértices   y   aristas;   escriba  además, dos vértices adyacentes y dos independientes.

Figura 1: Grafo con 5 vértices y 8 aristas

• • • •

Número de vértices = 5 Número de aristas = 8 Los vértices u y v son vértices adyacentes. Los vértices u y w son vértices independientes.

Grado de un vértice en un grafo  Se denomina  grado de un vértice v de un grafo no dirigido G al número de  aristas que inciden en v, y se designará g(v) (un lazo en v contribuye de manera  doble al grado de v).  Grado de un vértice en un digrafo En un grafo dirigido, el grado de salida es el número de aristas que salen de él, y  el grado de entrada es el número de aristas que entran en él. A un vértice de  grado 0 se le denomina vértice aislado. A un vértice de grado 1 se le denomina  vértice terminal o extremo.Incidencia de un Grafo Si (u, v) es una arista de un grafo dirigido, decimos que incide desde o sale de  el vértice u, que será su vértice inicial, y que incide hacia o entra en el vértice  v, que será su vértice final. Si se trata de un grafo no dirigido, decimos que (u,v)  simplemente incide en los vértices u y v, que serán sus vértices extremos.

Unidad III. Grafos Teoría de grafos 2-2010Definiciones, representaciones, tipos de grafos y árboles UNEFA-Núcleo Mérida

Representaciones de los Grafos  Existen diversas maneras de representar un grafo. Las más destacadas por su uso  son las siguientes: 1.­ Representación Gráfica  Consiste en un gráfico en que los vértices se representan mediante puntos. En  función del tipo de grafo que se tenga, ocurre:­ Los vértices se unen mediante segmentos si el grafo es no orientado. ­ Los vértices se unen mediante flechas indicando el vértice origen y final si el  grafo es orientado. Este tipo de representación es adecuada para la interpretación y resolución de  problemas en grafos pequeños o medianos. Ejemplos:

                  Figura 2: Grafo no dirigido 

                Figura 3:Grafo dirigido

2.­ Representación relacionalSe basa en la aplicación de representación en pares ordenados de la relación que  compone el grafo. 

  Figura 4:Grafo dirigido para el ejemplo de representación en forma de relación.

R={(v7,v6),(v7,v1),(v1,v2),(v6,v2),(v2,v5),(v2,v3),(v3,v4),(v5,v4)} 3.­ Representación Matricial 3.1.­ Matriz de Adyacencia: la matriz de adyacencia asociada al grafo G = (V ,E) es la matriz M=(mij) de orden pxp y definida en función del tipo de grafo que se  tenga. Si el grafo es no dirigido se tiene:   

Unidad III. Grafos Teoría de grafos 2-2010

Definiciones, representaciones, tipos de grafos y árboles UNEFA-Núcleo Mérida

                                                                                                                               1 si Vi Vj  Є E (Si Vi Vj se relacionan)                                  mij =                                                        0 si Vi Vj  no pertenece E (Si Vi Vj no se relacionan) Si el grafo es dirigido se tiene:                                                                                                                          1 si Vi Vj  Є E y la orientación de tal arista es Vi  → Vj  ...