Conceptos de la teoría de gráficas o grafos

1. Grafo

1.1. Es un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos.

2. Vértice

2.1. Es el punto donde se encuentran dos o más semirrectas o segmentos que conforman un ángulo.

3. Arista

3.1. Segmento de recta que limita la cara, también conocida como lado, de una figura plana; en la Geometría sólida se le llama arista al segmento de línea, recta o curva, donde se encuentran dos caras.

4. Grafo dirigido

4.1. Es un tipo de grafo en el cual las aristas tienen un sentido definido.

5. Grafo no dirigido

5.1. Es un tipo de grafo en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.

6. Costo

6.1. Tanto a las aristas como a los vértices les puede ser asociada información, a esta información se le llama etiqueta, si la etiqueta que se asocia es un número se le llama peso, costo o longitud,

7. Camino

7.1. Secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente.

8. Grafo completo

8.1. Es un grafo simple donde cada par de vértices está conectado por una arista.

9. Grafo nulo

9.1. Es un grafo trivial que no tiene vértices ni aristas. En teoría de categorías, el grafo nulo es el objeto inicial de la categoría de los grafos.

10. Grafo ponderado

10.1. Asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas o vértices, o ambos, de un grafo.

11. Grafo regular

11.1. Es un grafo donde cada vértice tiene el mismo grado o valencia. Un grafo regular con vértices de grado k es llamado grafo k-regular o grafo regular de grado k.

12. Ciclo

12.1. Es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino.

13. Ciclo de Euler

13.1. Circuito que incluye todos los lados - y por lo tanto todos los vértices - de un grafo dado una y solo una vez.

13.2. Condiciones para saber si un grafo dado tiene un paseo o circuito de Euler. 1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices de valencia impar. 2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, demás de ser conexo. 3) Si G es un grafo no dirigido con vértices {v1, v2, ... , vn} y la suma (v1), (v2), ... , (vn) es par, entonces el grafo tiene un circuito de Euler. 4) Un grafo G tiene un camino de Euler de v w si y solo si v y w son los únicos vértices de valencia impar.

14. Ciclo de Hamilton

14.1. El grafo o polígrafo G tiene un ciclo (camino) de Hamilton si existe un ciclo (camino) que verifica: visita todos sus vértices cada vértice es visitado una única vez (en el caso de los ciclos, el vértice inicial es visitado de nuevo para cerrar el ciclo)