GRAFOS

grafos

generalidades

• son estructuras de datos.
• representan relaciones entre elementos,objetos,nodos, las representaciones son no jerarquices
• se aplican en varias áreas del conocimiento aplicadas, química, geografía, ingeniería industrial, eléctrica, modela miento de redes (alcantarillado, transporte, computadores)
• no hay restricciones para formar grafos
• grafo esta formado por.

                       G(V,A)  V: conjunto de vértices

                                     A:conjunto de aristas, que representan las relaciones

grafo no dirigido

   v(1,3,5,7,9)

  A((1,3),(3,5),(5,7),(7,9),(9,1))

grafo dirigido

Dirección y camino preestablecido

factor de peso

Arcos con peso

camino

Trayectoria de un punto a otro

longitud de caminos A-E-B-F-A

A-A

Camino de mínimo peso

Donde si hay camino existe una longitud del camino

             camino 1-2=50

             camino 1-3-5=35

             camino 1-3-4-2=100

             camino 1-5-4-2=40

             camino 1-4-2=120

Adyacente

existe adyacencia entre 2 nodos si están unidos por un arco 

clases de adyacencia

A-B    B-A

A-C    C-A

A hacia B   A es adyacente hacia B

                                                                             

 A desde C    C es adyacente de A

                                                                              

D desde B    D es adyacente de B

Insidencia G vertices

Insidie si uno de sus puntos llega a ese vértice

arco incide en ambos nodos

El arco c inside en b

componente conectados separadamente

grafo fuerte mente conectado

Desde cualquier vértice se llega  a los demás caminos 

débilmente conectado

no se puede llegar desde cualquier vértice a los demás

Grafo eulariano

si partiendo  de cualquier vértice podemos recorrer todos los arcos llegando de nuevo al vértice origen, se puede pasar por vértices cuantas veces sea necesario, los arcos se pueden recorrer solamente una vez.

ADCAEDBEFGBA

Grafo hamiltoniano

Partiendo de cualquier vértice podemos recorrerlos todos sin repetir ninguno finalmente podemos llegar al vértice original ,los arcos se pueden recorrer una o mas veces 

ABEADBCDE

grado de un grafo

Es el numero de arcos que inciden  en ese vertice

Grado en A 2

Grado en F 4

         digrafo                                         vértice              grado de entrada              grado de salida
                              
                                                              A                                 2                                 0
                                                              B                                 2                                 0
                                                              C                                 1                                 3
                                                              D                                 0                                 2
                                                              E                                 2                                 1
                                                           

                                                                                                                            

grafo regular

Es regular si todos los vértices tienen los mismos grados

  Arco cíclico

un arco es cíclico si parte de un vértice y llega al mismo vértice

multigrafo

Donde dos vértices se unen por mas de un arco

grafo completo

Si cada vértice tiene n grado igual a n-1 donde n es el numero de vertices que componen el grafo

Matriz de adyacencia 

se genera a partir de la incidencia de cada uno de los arcos respecto a los nodos 

Lista de adyacencia

Es la representacion de todas las aristas o arcos de un grafo