Definicion de Grafos

En matematica o ciencias de la computacion un grafo o grafica es el principal objeto de estudio de la teoria de los grafos .

Informalmente un grafo es un conjunto de objetos llamados vertices o nodos unidos por enlaces llamados aristas o arcos , que permiten representar  relaciones binarias entre elementos de un conjunto.

Tipicamente un grafo se representa graficamente como un conjunto de puntos unidos por lineas.

Desde un punto de vista practico , los grafos permiten estudiar las interrelaciones entre unidades que interactuan unas con otras

Definición de dígrafo: 

Un grafo orientado o grafo dirigido G (abreviadamente digrafo) consiste en un conjunto no vacío de elementos V, llamados vértices o nodos y un multiconjunto E de pares ordenados de V, llamados arcos o aristas.

• Denotemos al digrafo por D = <V,E>
• Si r y w son vértices de D, entonces un arco rw  se dice que esta orientado o dirigido de r a w o que une a r y w.
•  Denotemos por V(D) y E(D) (en la bibliografía sobre grafos puede encontrarse sencillamente V y E, nosotros adoptaremos las dos y las aplicaremos cuando sea más clara una notación que otra ) a los conjuntos de vértices y aristas del grafo D respectivamente si estos no se mencionan explícitamente.

Definición de digrafo simple: 

Si un digrafo no tiene lazos ni arcos múltiples diremos que es un digrafo simple.

Definición de grafo subyacente: 

Sea D un digrafo. El grafo subyacente de D es el grafo que se obtiene reemplazando cada arco (orientado) de D por una arista no orientada. 

Definición de arcos múltiples:

 Los arcos que unen el mismo par de vértices que tienen la misma dirección se llaman múltiples.

• El arco que une a un vértice con el mismo se denomina lazo.
• Un digrafo sin lazos ni arcos múltiples se dice que es simple.

Definición de subgrafo:

 Considere el digrafo D = <V, E>. Un subgrafo de D es un digrafo cuyos vértices son todos elementos de V y cuyos arcos son todos elementos de E.

Definición  de vértices adyacentes:

 Sean v y w vértices de un digrafo. Diremos que w es adyacente a v si existe un arco  e desde v hasta w que los une. Además si e está dirigido de v a w diremos que e es incidente desde v e incidente desde w.

Definición de grado exterior e interior: 

Sea D un digrafo sin lazos y sea v un vértice de D. El grado exterior de v es el número de arcos incidentes desde v y lo denotaremos por ext deg(v). El grado interior de v es número de arcos incidentes a v y lo denotaremos por indeg(v).

• En caso de que el digrafo tenga lazos, cada lazo aporta uno a grado interior y uno al grado exterior del vértice correspondiente.
• Un vértice v es aislado si extdeg(v) = indeg(v) = 0.

Definición de digrafos isomorfos: 

Dos digrafos    y  son isomorfos y denotaremos , si existen bisecciones    y   :   y  , tales que para toda arista  .