Tipos de grafos

TIPOS DE GRAFOS

GRAFO SIMPLE: o simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.

MULTIGRAFO: o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos. Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

PSEUDOGRAFO: es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Formalmente, un multígrafo G es un par ordenado G:=(V, E) donde:

• V es un conjunto de vértices o nodos

• E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

GRAFO DIRIGIDO: Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha

TERMINOLOGIA O PROPIEDADES

ETIQUETADO: Los multigrafos y multidigrafos pueden etiquetarse de manera análoga a un grafo tradicional. Sin embargo, sólo existe consenso con respecto a la terminología para los multidigrafos.

Un multidigrafo etiquetado G es un grafo etiquetado con arcos etiquetados. Formalmente, es una 8-tupla donde:

• V es un conjunto de nodos y A un multiconjunto de arcos.

• y son alfabetos finitos para las etiquetas de nodos y arcos.

• y son dos funciones que indican la fuente y objetivo de los nodos de un arco.

• y son dos funciones que asocian cada nodo y arco con una etiqueta.

ADYACENCIA: En un grafo, los vértices son adyacentes si están unidos mediante una arista.

GRADO DE UN VERTICE: El grado o valencia de un vértice es el número de aristas incidentes en él. Para un grafo con bucles, éstos son contados por dos. En el ejemplo, los vértices 1 y 3 tienen grado 2; los vértices 2, 4 y 5, grado 3; y el vértice 6, grado 1.En un dígrafo, podemos distinguir el grado saliente (el número de aristas que dejan el vértice) y el grado entrante (el número de aristas que entran en un vértice). El grado de un vértice sería la suma de ambos números.

PONDERACION: Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel en que todas las aristas del camino son diferentes. Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último.

La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple

...