Grafos

Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).


Un grafo G es un par ordenado G = (V,E), donde:
•V es un conjunto de vértices o nodos, y
•E es un conjunto de aristas o arcos, que relacionan estos nodos.

Dentro de esta teoría se encuentran varios tipos de grafos pero en este texto nombraremos los mas básicos.

Grafo no dirigido

Está conformado por un conjunto de aristas las cuales no cuentan con una dirección específica.

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V, E) donde:
• V ≠ Ø
•

es un conjunto de pares no ordenados de elementos de V.

Grafo dirigido

Es el que posee una dirección específica entre vértices.
Un grafo dirigido o dígrafo es un grafo G = (V,E) donde:
• V ≠ Ø
•

es un conjunto de pares ordenados de elementos de .

Dada una arista (a, b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.

Grafos Simples

Un grafo es simple si sólo 1 arista QUE une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple

Karla Garcia