1.1. es un vértice que está conectado a v mediante una arista. La vecindad de un vértice v en un grafo G es el subgrafo inducido de G que está formado por todos los vértices adyacentes y todas las aristas que conectan dichos vértices.
2. Camino /Ciclo Euleriano
2.1. Es un camino que incluye todos los lados - y por lo tanto todos los vértices - de un grafo dado, una y solo una vez.
3. Camino /Ciclo Hamiltoniano
3.1. Una gráfica G es Hamiltoniana si existe un ciclo que contiene a todos los vértices de G. Un ciclo que contiene a todos los vértices de la gráfica se le conoce como ciclo Hamiltoniano.
4. Árbol
4.1. Gráfica convexa sin ciclos
5. Árbol de Expansión
5.1. Se define 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.
6. Relación Binaria
6.1. Es larelación R existente entre dos elementos a y b, de dos conjuntos A y B respectivamente. Indicando que el elemento a está relacionado con b. Esta relación se puede denotar de diversas formas: 1- Como pares ordenados (a, b). 2- Indicando que aRb. 3- Como una mezcla entra los dos anteriores R(a,b). Al conjunto de todos los elementos relacionados mediante la relación R en un conjunto lo denotamos como R(M)
7. Digráfica de una Relación
7.1. Consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tales que cada arista e ∈ E está asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vértices, se escribe e = (v, w), que denota una arista de v a w.
8. Matriz de una Relación
8.1. Una matriz es un arreglo rectangular que representa la correspondencia, es decir la relación, que es R de A y B. Se representan los renglones con elementos de A y las columnas que etiquetan los elementos de B.
9. Propiedades de una relación: reflexiva, simétrica, transitiva, antisimétrica
9.1. Reflexiva: se da cuando cada elemento está relacionado consigo mismo y se escribe como a R a para todo a que pertenece al conjunto. Sea R una relación binaria definida en un conjunto A por lo que R es una relación reflexiva si aRa para cada a ϵ A. Si A = {a, b, c, d}. Una relación es reflexiva si contiene los subconjunto de {<a, a>, <b,b>, <c,c>, <d,d>} Simétrica:En una relación simétrica para todo par de elementos, sucede que el elemento a está relacionado con el elemento b, por lo que el elemento b está relacionado con el elemento a, es decir, existe una relación de tipo simétrica si aRb y bRa son a,b ϵ A. Si A = {a, b, c, d}. Una relación es simétrica si {<a, b>, <c,a>, <b,a>, <a,c>}. Transitiva: Se llama relación transitiva la que verifica si un elemento x está relacionado con el elemento y, además que el elemento y está relacionado con el elemento z, por lo que el elemento x está relacionado con el elemento z. entonces xRy aunado yRz implica xRz para x,y,z ϵ A. Si A = {x, y, z, d}. Una relación definida como: {<x,y>, <y,cz, <x,cz, <x,d>} Antisimétrica:
10. Gráfica (Grafo)
10.1. Estructura por un conjunto no vacío V=V(G) cuyos elementos son llamados vértices.
11. Vértice (Nodo)
11.1. Son los puntos con los que conecta cada linea.
12. Arista (Arco)
12.1. Es el conjunto de pares no ordenados de vértices. E = E (G)
13. Bucle
13.1. Arco o arista cuyos vértices coinciden. Representa una conexión directa de un vértice consigo mismo.
14. Matriz de Adyacencia
14.1. Se define la matriz de adyacencia A(D) de una digráfica D de orden n como una matriz de n ×n definida como A(D) = [ai j], donde: ai j =1 si vi vj ∈F(D), 0 en otro caso.
15. Matriz de Incidencia
15.1. Una digráfica D de orden n y tamaño m es una matriz B(D) de orden n ×m definida como B(D) = [bi j], donde bi j =−1 si la flecha ej sale desde el vértice vi, 1 si la flecha ej sale hacia el vértice vi, 0 en otro caso.
16. Grado de un Vértice
16.1. Se define como el número total de arcos que inciden de dicho vértice, y evalúa su grado de conexión con el resto de vértices.
17. Grafo Simple
17.1. Es la gráfica que no tiene lazos ni aristas paralelas.
18. Relación de Equivalencia
18.1. Las relaciones de equivalencia permiten agrupar los elementos con características en común en los conjuntos. Cumple sobre un conjunto relaciones de tipo reflexiva, simétrica y transitiva.
19. Cerradura transitiva de una relación
19.1. Sea R una relacion en AxA la cerradura transitiva de R es R ⊆ AxA tal que R es la relación mas pequeña que contiene a R y es simétrica.
20. Multigrafo
20.1. Es la gráfica con lazos y aristas paralelas.
21. Digrafo (Digráfica)
21.1. Digráfica D es una estructura formada por un conjunto de vértices llamado V (D) y un conjunto F(D) de pares ordenados de V (D) llamados flechas o arcos. Ejemplo: D con V (D) = {v1, v2, v3, v4, v5, v6} y F(D) = {v1v2, v1v5, v2v6, v3v1, v3v4, v4v2, v5v6, v6v5, v5v3, v6v4}.
22. Camino
22.1. Un camino es una sucesión de vértices (v1, v2,..., vl) con vi−1vi ∈ E(G) para todo i = 2, 3,...,l.
23. Ciclo (Circuito)
23.1. Un ciclo es un camino cerrado en el cual todos los vértices son distintos.
