1.1. Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un sentido definido, a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.
2. Multigrafo
2.1. Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos.
3. Grafo simple
3.1. Un grafo es simple si a lo sumo 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.
4. Grado de un vértice
4.1. El grado de un vértice en un grafo es el número de aristas incidentes a él.
5. Grafo
5.1. Representación simbólica de los elementos constituidos de un sistema o conjunto, mediante esquemas gráficos.
6. Vertice
6.1. Un vértice de corte es un vértice que al removerlo desconecta al grafo restante.
7. Arista
7.1. Una arista corresponde a una relación entre dos vértices de un grafo.
8. Vértice Adyacente
8.1. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une.
9. Bucle
9.1. Un bucle o loop es una arista que conecta un vértice consigo mismo.
10. Matriz de Adyacencia
10.1. La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.
11. Matriz de incidencia
11.1. La matriz de incidencia es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representar relaciones binarias.
12. Camino
12.1. Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).
13. Ciclo
13.1. Un Grafo ciclo o simplemente ciclo 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.
14. Ciclo Euleriano
14.1. Un camino euleriano es un camino que pasa por cada arista una y solo una vez.
15. Ciclo Hamiltoniano
15.1. Un camino hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez.
16. Arbol
16.1. Un grafo conectado que contiene circuitos no simples se llama árbol.
17. Árbol de expansión
17.1. Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.
18. Relación binaria
18.1. Sean A y B dos conjuntos. Una relación (binaria) R de A en B es un subconjunto de A × B. Sean A y B dos conjuntos. Una relación (binaria) R de A en B es un subconjunto de A × B.
19. Digráfica
19.1. Para dibujar la digráfica de una relación en un conjunto X, primero dibujamos puntos o vértices para representar los elementos de X.
20. Matriz de una relación
20.1. Sea R una relación en un conjunto finito A. La misma puede representarse matricialmente por: siendo n=|A| definida por. Relación de orden entre matrices booleanas.
21. Propiedades de una relación
21.1. Una relación reflexiva o refleja es una relación binaria R sobre un conjunto A, de manera que todo elemento de A está relacionado consigo mismo. Es decir, . En tal caso, se dice que R cumple con la propiedad de reflexividad.
21.2. Una relación binaria R sobre un conjunto A, es simétrica cuando se da que si un elemento está relacionado con otro mediante R, entonces ese otro también está relacionado con él, a través de la misma "R". Es lo mismo tener (a,b) que tener (b,a).
21.3. Una relación binaria sobre un conjunto es transitiva cuando se cumple: siempre que un elemento se relaciona con otro y este último con un tercero, entonces el primero se relaciona con el tercero. Esto es: Dado el conjunto A y una relación R, esta relación es transitiva si: a R b y b R c se cumple a R c.
21.4. Una relación binaria sobre un conjunto es antisimétrica cuando se da que si dos elementos de se relacionan entre sí mediante , entonces estos elementos son iguales. Es decir, Para todo a, b de A, si se cumple que a está relacionado con b y b está relacionado con a, entonces a es igual a b.
22. Relación de equivalencia
22.1. Relación de equivalencia sobre un conjunto, permite establecer una relación entre los elementos del conjunto que comparten cierta característica o propiedad. Esto permite reagrupar dichos elementos en clases de equivalencia, es decir, «paquetes» de elementos similares.
23. Cerradura transitiva
23.1. La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original.
