La historia y Conceptos básicos de grafos

1. Vértices

1.1. Puntos conectados por dos o más aristas

2. Aristas

2.1. Se usan para conectar dos vértices del grafo

3. Grafo dirigido

3.1. Un graf en el que la arista tiene dirección

4. Grafo conexo

4.1. En el existe un camino entre cada par de vértices

5. Caminos y circuitos de Euler

5.1. Camino de Euler

5.1.1. Recorre cada arista sin repeticiones y no vuelve al vértice inicial.

5.2. Circuito de Euler

5.2.1. Recorre cada arista sin repeticiones, por ser un circuito, debe comenzar y terminar en el mismo vértice.

6. Matriz de adyacencia

6.1. Método donde el grafo se almacena en forma de matriz de dos dimensiones compuesta por filas y columnas que indican vértices. Una matriz de adyacencia de forma de ceros y unos.

7. Aplicaciones

7.1. Representar flujo de control en computadoras

7.2. Mapas para encontrar la ruta más corta

7.3. Medios de transporte para encontrar el camino más corto

7.4. Circuitos electrónicos para representar los puntos del circuito como vértices y los cables como aristas

7.5. Redes sociales donde los usuarios actúan como nodos y la conexión entre ellos como aristas

7.6. Juegos de acertijos como los laberintos

8. Historia

8.1. La idea de los grafos fue introducida en el año 1736 por el matemático suizo Leonhard Euler.

8.2. Su solución al problema del puente de Königsberg dio origen a la teoría de grafos.

8.3. El grafo lo integraban un conjunto de puntos llamados vértices conectados por líneas conocidas como aristas.

9. Grafo

9.1. Estructura de datos no lineal, que consta de vértices conectados por aristas. Formalmente, un gráfico se denota como un par G (V, E). Donde V representa los vértices y E representa las aristas.

10. Grafo no dirigido

10.1. Grafo en el que las aristas no tienen ninguna dirección

11. Grafo no conexo

11.1. En el que al menos un vértice no es accesible desde otro vértice.

12. Caminos y circuitos Hamiltonianos

12.1. Circuito hamiltoniano

12.1.1. Visita cada vértice una vez sin repeticiones, debe comenzar y terminar en el mismo vértice.

12.2. Camino hamiltoniano

12.2.1. También visita cada vértice una vez sin repeticiones, sin comenzar y terminar en el mismo vértice.