Definiciones sobre grafos

FIXME: 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 o digrafo: 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$.

Grafo subyacente: El grafo subyacente de un grafo dirigido, es el grafo no dirigido que resulta de “ignorar” todas las direcciones de las aristas. Es decir, tiene los mismos nodos, y las mismas aristas, pero sin que importe ya la dirección (se borran las “flechas” del dibujo, cambiando a “rayas”).

Loop, bucle, 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). Se suele notar $d(v)$ al grado de $v$, $d^+(v)$ a su grado de salida de $v$, y $d^-(v)$ a su grado de entrada. A veces se define el grado neto de un nodo, como la diferencia $d^0(v) = d^+(v) - d^-(v)$. Si se estuviera trabajando con varios grafos al mismo tiempo, de manera tal que puede ser confuso en cuál se debe mirar el grado, se puede indicar debajo: Por ejemplo $d_G(v)$ sería el grado de $v$ en $G$, y $d^+_H(w)$ sería el grado de salida de $w$ en $H$.

Fuente o source: Es un nodo en un grafo dirigido al cual no entran aristas: Es decir, su grado de entrada es $d^-(s) = 0$.

Sumidero o sink: Es un nodo en un grafo dirigido del cual no salen aristas: Es decir, su grado de salida es $d^+(s) = 0$.

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

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.

Longitud de un camino: Se define la longitud de un camino como su cantidad de aristas. El camino “trivial”, que comienza y termina en un cierto nodo “sin moverse”, tiene longitud 0.

Grafo con pesos o Grafo pesado: Un grafo con pesos, es un grafo en el cual cada arista tiene asociado un número, que generalmente se llama el “peso” de la arista.

Peso de un camino: El peso de un camino es la suma de los pesos de las aristas que la componen.

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. En problemas sobre grafos con pesos, en lugar de la longitud (cantidad de aristas) se suele llamar camino mínimo a aquel que tenga menor peso. Cuál de las dos nociones de “mínimo” se utiliza depende del contexto.

Distancia: Se define la distancia entre $u$ y $v$, que generalmente se escribe $d(u,v)$, como la longitud de un camino mínimo (o el peso de un camino mínimo, si se trabaja con pesos en las aristas) 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 por conveniencia que $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. Notar que con la definición anterior de que los pares de nodos no alcanzables entre sí están a distancia infinita, se sigue respetando la desigualdad con estos nodos (con las reglas aritméticas de que $+\infty > x$ y $+\infty + x = +\infty - x = +\infty$ para cualquier número $x$).

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, porque quedarían “flotando”).

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 no dirigido, 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.

Grafo débilmente conexo: Un grafo dirigido se dice débilmente conexo, cuando el subyacente es conexo (es decir, si ignoramos las direcciones, todos los nodos están conectados en una sola componente).

Componente débilmente conexa: Una componente débilmente conexa de un grafo dirigido, es un subgrafo débilmente conexo maximal. Son exactamente lo mismo que las componentes conexas del grafo subyacente.

Grafo fuertemente conexo: Un grafo dirigido se dice fuertemente conexo, si para todo par de nodos $a,b \in V$, existe un camino desde $a$ hacia $b$. Es decir, se puede viajar desde cualquier nodo hasta cualquier otro, en ambas direcciones.

Componente fuertemente conexa: Una componente fuertemente conexa de un grafo dirigido, es un subgrafo fuertemente conexo maximal. No alcanza con mirar el subyacente, y su cálculo es más complicado que el de las componentes conexas o débilmente conexas.

Grafo traspuesto: El grafo traspuesto de un grafo dirigido $G$, que se suele notar $G^t$, es el grafo que se obtiene de $G$ invirtiendo el sentido de todas las aristas. Es decir, por cada arista $x \rightarrow y$ en $G$, se pone en $G^t$ una arista $y \rightarrow x$

Bosque: Un bosque es un grafo no dirigido, sin ciclos simples.

Árbol: Un bosque conexo. Notar que de esta definición y la anterior, cada componente conexa de un bosque es un árbol. Equivalentemente, un árbol es un grafo en el cual existe un único camino simple entre cada par de nodos. Notar que en un árbol no se puede hablar de “padres” ni de “hijos”, a menos que se fije una raíz (ver árbol con raíz).

Hoja: Es un nodo en un grafo no dirigido que tiene grado 1: $d(h) = 1$. Son especialmente importante en los árboles, ya que todo árbol no trivial tiene al menos dos hojas, y se puede “desarmar” todo el árbol “podando hojas” sucesivamente.

Árbol con raíz: Un árbol con raíz es un grafo dirigido, cuyo grafo subyacente es un árbol, y con una raíz distinguida, de manera tal que se cumpla una de las siguientes dos variantes:

Notar que si en un árbol se fija uno de sus nodos como raíz, existe una única manera de convertirlo en un árbol con raíz dirigido hacia la raíz. Y su grafo traspuesto será la única forma de conseguir un árbol con raíz dirigido hacia las hojas. Esto hace que las dos formas de ver el árbol con raíz sean equivalentes. En la versión dirigida hacia la raíz, el nodo destino de la única arista saliente de un nodo $u$ que no sea la raíz se llama el padre de $u$. Similarmente, se dice que $u$ es hijo de $v$, si $v$ es el padre de $u$. El padre de un nodo es el primer nodo en el único camino hacia la raíz, y la raíz es el único nodo sin padre (muchas veces se toma la convención de que la raíz es su propio padre, pues puede resultar muy conveniente a la hora de implementar).

Hoja en un árbol con raíz: En un árbol con raíz, se utiliza una definición de hoja diferente a la de un grafo no dirigido habitual: Una hoja es un nodo que no tiene hijos. Notar que en un árbol con un único nodo, la raíz es una hoja en este caso, aunque tenga grado 0. Por otro lado, si la raíz tiene un único hijo, entonces no se la considera una hoja, a pesar de tener grado 1.

Nodo interno: En un árbol (o en un árbol con raíz) se suelen llamar nodos internos o nodos interiores, a los nodos que no son hojas.

DAG o grafo dirigido acíclico: Un DAG (directed acyclic graph) o grafo dirigido acíclico, es un grafo dirigido sin ciclos. Notar que el grafo subyacente podría estar lleno de ciclos, es decir no tiene por qué ser un bosque.

Grafo dirigido transitivo: Un grafo dirigido se dice transitivo, si cada vez que hay una arista $A \rightarrow B$, y una arista $B \rightarrow C$, también se encuentra en el grafo una arista $A \rightarrow C$. Se denomina la clausura transitiva de un grafo dirigido $G$, al grafo que resulta de agregarle a $G$ las mínimas aristas posibles para que se vuelva transitivo. Equivalentemente, la clausura transitiva se obtiene con los mismos nodos, y poniendo un eje desde $x$ hasta $y$, si en el grafo $G$ existe un camino desde $x$ hasta $y$.