: Ordenar bien, completar con otras definiciones.

Un grafo consta de nodos o vértices (son sinónimos). Algunos pares de nodos están conectados entre sí por ejes, arcos o aristas (también son términos sinónimos en teoría de grafos). Se nota $V$ a los vértices y $E$ a los ejes.

Grafo no dirigido: Un grafo en el cual la única característica de las aristas es qué nodos unen, sin importar “la dirección”: $A-B$ o $B-A$ es exactamente la misma arista en un grafo no dirigido. Generalmente, si se habla de grafo sin aclarar, se está hablando normalmente de un grafo no dirigido.

Grafo dirigido: Es un grafo en el cual importa la dirección en la cual apuntan las aristas. Es decir, $A-B$ y $B-A$ son aristas totalmente diferentes, ya que una sale de $A$ y llega a $B$, mientras que la otra sale de $B$ y llega hasta $A$.

Loop, autoeje o rulo: Es un eje que tiene ambos extremos iguales: en el dibujo, es un “rulo” sobre un cierto nodo. Pueden estar tanto en un grafo dirigido, como en un grafo no dirigido.

Multiejes: En un grafo no dirigido, cuando hay más de un eje entre el mismo par de nodos, se dice que estos son multiejes (y se dice que el grafo tiene multiejes, o a veces se dice que es un multigrafo). En el caso de un grafo dirigido, para que haya verdaderamente multiejes deben existir varios ejes entre el mismo par de nodos, y en la misma dirección. Es decir, 2 ejes $A-B$ y $B-A$ generalmente no se consideran multiejes, ya que no son “equivalentes” esas aristas.

Grafo simple: Un grafo no dirigido, sin autoejes ni multiejes.

Grado de un nodo: Es la cantidad de aristas que tienen al nodo como extremo. Si el grafo es dirigido, se habla en su lugar de “grado de entrada” (que cuenta la cantidad de ejes que entran al nodo) y “grado de salida” (que cuentan la cantidad de ejes que salen del nodo). En un grafo dirigido con autoejes, estos suman uno tanto al grado de entrada como al grado de salid del nodo (porque “salen y entran” al mismo). Similarmente, en un grafo no dirigido con autoejes, la convención más usual es que un autoeje se cuenta “2 veces” para definir el grado de un nodo (porque lo toca “dos veces”, una en cada extremo).

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$.

Desigualdad triangular: Es una desigualdad matemáticamente válida para la distancia en grafos (y para cualquier función que se comporte razonablemente como una “distancia”). Siempre vale que: $d(u,w) \leq d(u,v) + d(v,w)$. Esto es porque, si tomamos un camino mínimo de $u$ hasta $v$, y un camino mínimo de $v$ hasta $w$, y los “pegamos” uno a continuación del otro, se obtiene un camino que en total va desde $u$ hasta $w$, que mide en total $d(u,v) + d(v,w)$. Como $d(u,w)$ es lo que mide el mejor de todos los posibles caminos desde $u$ hasta $w$, no puede nunca ser mayor que este camino particular que hemos construido.

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.