Teoría de gráficas

1. Arista

1.1. Pares no ordenados de E

1.2. Se representa por líneas.

1.3. Incide en 2 vértices.

2. Vértices adyacentes

2.1. Son los vértices que son extremos de una arista.

3. Bucle

3.1. Arista en donde sus extremos coinciden.

4. Matriz de incidencia

4.1. Es una matriz cuyas filas están indizadas por los vértices del grafo y cuyas columnas están indizadas por las aristas, con un 1 en la celda para la fila i y columna j cuando el vértice i y la arista j son incidentes, y un 0 de lo contrario

5. Grafo simple

5.1. Grafo sin bucles

6. Digrafo

7. Ciclo

7.1. Cadena en la que no se repite ninguna arista, ni vértice a excepción de la inicial y final.

8. Ciclo hamiltoniano

8.1. Camino que cubre todos los vértices de un grafo exactamente una vez.

9. Árbol de expansión

9.1. Es un subgrafo que es un árbol que incluye todos los vértices del grafo.

10. Propiedades de una relación

10.1. Reflexiva

10.2. Simétrica

10.3. Transitiva

10.4. Asimétrica

11. Cerradura transitiva de una relación

11.1. Consiste en la relación más pequeña en X que contiene R y es transitiva.

12. Digráfica de una relación

12.1. En una relacíon transitiva, siempre que hay aristas de x a y y de y a z, hay una arista de x a z.

13. Gráfica

13.1. Pareja de conjuntos (V,E) donde:

13.1.1. V es distinto de vacío

13.1.2. E es un conjunto de elementos pares de V

14. Vértice

14.1. Elemento de V

14.2. También se llama "nodo"

14.3. Se representa por puntos.

14.4. Es el extremo de una arista.

15. Matriz de adyacencia

15.1. Es una matriz de nxn que representa a un digrafo, donde cada valor representa el número de aristas.

16. Grado de un vértice

16.1. Número de aristas incidentes en v.

16.2. Cuando la arista es un bucle, contribuye dos unidades al valor del grado.

16.3. La suma de los grados de un grafo es igual al doble del número de aristas.

17. Multigrafo

17.1. Grafo que permite adyacencias múltiples.

18. Camino

18.1. Cadena en la que no se repiten ni vértices ni aristas.

19. Ciclo euleriano

19.1. Es un camino cerrado que usa cada arista exactamente una vez.

20. Árbol

20.1. Grafo no dirigido que es conecto y acíclico.

20.2. Grafo dirigido en el que existe un único camino de un vértice al resto de los vértices.

21. Relación binaria

21.1. Es el subconjunto del producto cartesiano X x Y.

22. Matriz de una relación

22.1. Es una matriz nxn que representa la correspondencia entre dos conjuntos A y B.

23. Relación de equivalencia

23.1. Relación binaria que es reflexiva, simétrica y transitiva.

24. Cadena

24.1. Toda sucesión finita alterna de vértices y aristas.