Multiejes: Un grafo admite multiejes, cuando es válido tener más de un eje entre el mismo par de nodos. En un grafo dirigido, para que se consideren multiejes, ambos deben apuntar en la misma dirección (por ejemplo, si hubiera dos ejes desde $u$ hacia $v$).

Camino: Hay dos definiciones posibles de camino en un grafo, prácticamente equivalentes:

• Como secuencia de nodos: Un camino en un grafo $G$ es una secuencia de nodos, $v_0$, $v_1$, $\cdots$, $v_k$, con $k \geq 0$, de manera tal que siempre se cumple que $(v_i, v_{i+1})$ es una arista del grafo, con $0 \leq i < k$. El entero $k$ es la longitud del camino, que coincide con la cantidad de aristas utilizadas. Cuando $k=0$, tenemos un camino trivial, que comienza y termina en el mismo nodo, sin moverse.
• Como secuencia de aristas: Un camino en un grafo $G$ consta de un nodo inicial $v_0$, y una secuencia de aristas, $e_1$,$e_2$, $\cdots$, $e_k$, con $k \geq 0$, de manera tal que cada arista comience donde terminó la anterior (y la primera debe comenzar en $v_0$). Como antes, $k$ se llama la longitud del camino, y corresponde exactamente a la cantidad de aristas usadas. En este caso, el camino trivial de la definición anterior sería un caso especial, que se correspondería con una secuencia de aristas vacía (por eso longitud 0).

Las dos definiciones anteriores de camino son casi totalmente equivalentes, aunque en grafos con multiejes pueden generar pequeñas diferencias: caminos distintos como secuencia de aristas, podrían corresponderse a exactamente la misma secuencia de nodos. Por lo tanto, si un problema pidiera contar la cantidad de caminos, y son válidos los multiejes, se debe tener mucho cuidado de saber si el problema pide contar secuencias de nodos o ejes, ya que se obtendrán números diferentes.

Camino simple: Un camino se dice simple, cuando no pasa dos veces por el mismo nodo. Una observación importante es que un camino simple tampoco repite aristas: si repitiera aristas, automáticamente tendría que repetir los nodos involucrados en esa arista.

Camino mínimo: Se dice que un camino entre dos nodos es mínimo, si no existe ningún otro camino con el mismo origen y destino, pero de menor longitud.

Distancia: Se define la distancia entre $u$ y $v$, que generalmente se escribe $d(u,v)$, como la longitud de un camino mínimo desde $u$ hasta $v$. Notar que en un grafo dirigido, puede ser $d(u,v) \neq d(v,u)$. Generalmente, cuando no existe ningún camino de $u$ hasta $v$, se define $d(u,v) = +\infty$.

Ciclo: Un ciclo es un camino, pero en el cual el vértice inicial coincide con el vértice final. El camino trivial se puede considerar también un ciclo trivial, de longitud 0, que comienza y termina en el mismo nodo sin moverse. Notar que así, todos los grafos tienen ciclos, aunque sea los triviales. E incluso ocurre que todo grafo no dirigido con al menos una arista tiene ciclos no triviales: si la arista une $u$ con $v$, la secuencia $(u,v,u)$ es un ciclo de longitud 2. Por esta razón, muchas veces cuando se habla de “ciclos”, en realidad se quiere decir “ciclos simples” (ver definición siguiente), pero no siempre es así, sino que muchas veces uno sí se refiere a estos ciclos “no simples”. Es necesario entonces estar atento al contexto para hacer esta distinción (por ejemplo, cuando se dice “un bosque es un grafo sin ciclos”, se entiende que se está diciendo “sin ciclos simples”, porque sino no tendría sentido la definición).

Ciclo simple: Un ciclo simple es un ciclo no trivial, que no repite ningún nodo ni ninguna arista, excepto el nodo inicial $v_0=v_k$, que se repite únicamente al completar el ciclo, y no antes. Notar que a diferencia de lo que pasaba con caminos, es posible formar un ciclo que no repita nodos, pero sí aristas: solamente ocurre con los ciclos de longitud 2, en un grafo no dirigido, es decir los de la forma $(u,v,u)$. Estos no se consideran ciclos simples. En otras palabras, un ciclo simple tiene longitud por lo menos 3.

Subgrafo: Un subgrafo $H$ de un grafo $G$ (que generalmente se escribe $H \subseteq G$), es un nuevo grafo, tal que $V(H) \subseteq V(G)$, y $E(H) \subseteq E(G)$. Es decir, $H$ tiene algunos de los vértices de $G$, y algunas de las aristas de $G$ (posiblemente todas, posiblemente ninguna), y sigue siendo un grafo (no vale dejar aristas si no dejamos también sus nodos extremos).

Grafo conexo: Un grafo es conexo, cuando para cualquier par de vértices del grafo, existe un camino que va de uno a otro.

Componente conexa: Una componente conexa de un grafo, es un subgrafo conexo maximal. Es decir, un subgrafo de $G$, que sea conexo, y que si le agregamos cualquier otra cosa de $G$, ya deja de ser conexo. Si lo imaginamos en un dibujo, es cada una de las “partes” o “pedazos” en que $G$ está dividido.