1.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.
2. Camino
2.1. Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).
3. Ciclo
3.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.
4. Ciclo Euleriano
4.1. Un camino euleriano es un camino que pasa por cada arista una y solo una vez.
5. Ciclo Hamiltoniano
5.1. Un camino hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez.
6. Árbol de expansión
6.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.
7. Digráfica
7.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.
8. Propiedades de una relación
8.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.
8.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).
8.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.
8.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.
9. Cerradura transitiva
9.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.
10. Digrafo
10.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.
11. Multigrafo
11.1. Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos.
12. Grafo simple
12.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.
13. Grado de un vértice
13.1. El grado de un vértice en un grafo es el número de aristas incidentes a él.
14. Grafo
14.1. Representación simbólica de los elementos constituidos de un sistema o conjunto, mediante esquemas gráficos.
15. Vertice
15.1. Un vértice de corte es un vértice que al removerlo desconecta al grafo restante.
16. Arista
16.1. Una arista corresponde a una relación entre dos vértices de un grafo.
17. Vértice Adyacente
17.1. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une.
18. Bucle
18.1. Un bucle o loop es una arista que conecta un vértice consigo mismo.
19. Matriz de Adyacencia
19.1. La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.
20. Arbol
20.1. Un grafo conectado que contiene circuitos no simples se llama árbol.
21. Relación binaria
21.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.
22. Matriz de una relación
22.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.
23. Relación de equivalencia
23.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.
