Anexo: Tipo de Grafos

Tipos de Grafos

Los grafos en primer lugar se pueden clasificar en:

Dirigidos y no Dirigidos: En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que representan dos arcos diferentes. En un grafo no dirigido el par de vértices que representa un arco no está ordenado.

Tipos de Grafos

1. Grafos Simples: Un grafo es simple si a lo más existe 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. Un grafo que no es simple se denomina multígrafo.
2. Grafo Completo: Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices.
3. Grafo Regular: Aquel con el mismo grado en todos los vértices.
4. Grafo Bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto.
5. Grafo Nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislado.
6. Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
7. Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
8. Grafo conexo: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro.
9. Digrafo (o Grafo Dirigido): A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas,
10. Grafo Trivial: En teoría de grafos, un grafo trivial es un grafo con 0 aristas, y 0 ó 1 vértices.
11. Grafo Plano: Es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano).
12. Grafo Rueda: Es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo. 
13. Grafos Ponderados: Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Este número representa un peso para el recorrido a través de la arista.
14. Pseudografo: Es un conjunto de pares no ordenados de elementos. Es decir, un pseudografo es un grafo no dirigido que acepta bucles entre sus nodos.

Elementos y Propiedades de un Grafo

Elementos

Nodo: Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él.

Aristas:Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si coinciden en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

Cruce: Son dos aristas que cruzan en un punto. 

Vértices: Son los puntos o nodos con los que esta conformado un grafo.

Propiedades

• Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
• Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
• Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
• Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Grafos: Concepto

Grafo 

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. Son objeto de estudio de la teoría de grafos.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas). Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas). 

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales. En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas.

La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.