Clase PAP 2017 Melanie https://git.exactas.uba.ar/ltaravilse/pap-alumnos/blob/master/clases/clase03-grafos/grafos.pdf

Un grafo es un conjunto de objetos, llamados vértices o nodos, unidos mediantes líneas llamadas aristas. Se los usa para representar muchas cosas, por ejemplo en arquitectura, los nodos pueden representar habitaciones o espacios, y las aristas pueden significar que los espacios unidos comparten una pared.

También se los usa para analizar redes, donde los nodos son computadores y una arista representa que las computadoras que une están conectadas.

Se los usa para entender y analizar muchíisimas cosas en la vida real, y hay muchos problemas de programación que ilustran situaciones posiblemente reales para los cuales usaremos grafos.

Los grafos sirven para representar relaciones entre distintas “cosas”. Esas “cosas”, nuestros nodos, pueden ser cualquier cosa, comidas, personas, ciudades... y hasta puede haber algunos nodos que representen un tipo de cosa, y otros nodos que representen otro tipo, por ejemplo nodos que representen personas, y otros que representen comidas, y que la relación sea “a la persona $A$ le gusta la comida $B$”. Las relaciones las representamos con aristas. Hay veces que además de saber que dos nodos están relacionados, nos importa cómo. Las aristas pueden tener un número que indique su distancia por ejemplo, indicando qué tan lejos están esos nodos. También podrían estar orientadas, es decir que no sea sólo una línea, sino una flecha. Esto podría indicar por ejemplo que desde la esquina $A$ se puede llegar a la $B$ a través de una arista, que sería la calle, pero si es de una sola mano no podemos ir a través de ella de $B$ a $A$, entonces indicamos ese tipo de relación con una flecha.

Estos son algunos ejemplos de grafos:

La definición formal dice que un grafo $G$ es un par ordenado $(V, E)$ donde $V$ es un conjunto de nodos, y $E$ es un conjunto de aristas o arcos que unen esos nodos.

Algo muy importante es cómo guardar un grafo en la computadora. En una hoja es fácil, lo dibujamos y listo. Pero y en la compu?

Existen varias maneras de guardar la información de un grafo en la computadora. Las que vamos a ver a continuación son las más populares:

La matriz de adyacencia es una matriz de $n$ x $n$, donde $n$ es la cantidad de nodos, que en la posición $j$ de la fila $i$, guarda la información de la arista que conecta al nodo $i$ con el nodo $j$. Es importante notar que deberemos saber cuál es el nodo $i$, y cuál el nodo $j$, es decir, debemos asignar números a nuestros nodos para manejarlos mejor.

Entonces, si las aristas del grafo no tienen información, y lo importante es si la arista existe (si el nodo $i$ está unido al $j$), podemos guardar un $1$ si la arista existe, y un $0$. Por ejemplo así:

Si las aristas tuvieran longitud supongamos positiva, en vez de unos y ceros, podríamos guardar el valor de la longitud cuando la arista exista, y un $0$ si no existe. Si las aristas pueden tomar por ejemplo cualquier valor entre $-1000$ y $1000$, basta con asignar por ejemplo el número $1001$ cuando la arista no existe, y así con un $if$ saber si existe o no (dependiendo de si vale $1001$ o no).

Se implementa con un vector de 2 dimensiones, $vector< vector<int> > matriz(n, vector<int>(n))$ que en matriz[i][j] hay un $1$ si el nodo $i$ está unido al $j$, y un $0$ si no (en el primer caso). También podría ser de $boolean$ en vez de $int$ y guardar true/false.

Ventaja: Permite saber si hay o no (o cuánto mide) una arista entre dos nodos en $O(1)$. Desventaja: La complejidad espacial y temporal para almacenar la matriz es $O(n^2)$.

Para cada nodo, vamos a guardar una lista con los nodos unidos a él. Si las aristas tuvieran longitud, podemos guardar en vez de los números de nodos, pares de enteros, que indiquen el nodo unido y la longitud de la arista que los une.

Se implementa también como un vector de 2 dimensiones, $vector< vector<int> > grafo(n)$, que en el vector $grafo[i]$ están todos los nodos que están unidos al nodo $i$ a través de aristas.

Ventaja importante: La complejidad especial es $O(n+m)$! Tenemos $n$ listas, pero en ellas aparecen exactamente todos los nodos entre los cuales hay aristas. Con la matriz de adyacencia también guardábamos información si no había arista, ahora si no hay arista simplemente no aparecen en la lista. Desventaja: Saber si exista una arista entre $i$ y $j$ implica recorrer toda la lista de $i$ y ver si está $j$, cuya complejidad es $O(n)$.

Porque lo que más vamos a querer hacer es recorrer un grafo, entonces más que saber si existe una arista entre dos, querríamos “movernos a través de ella”, y para eso, desde un nodo, queremos encontrar todas las aristas con un extremo en él, entonces mirar todos los nodos (matriz de adyacencia) es más caro que mirar únicamente los que sabemos que está unidos a él. Para ver más sobre recorrer grafos y problemas típicos, pueden ver las técnicas típicas que son BFS y DFS.

Una situación típica que involucra fuertemente teoría de grafos es la que se conoce como “a ver si podés dibujar la figura sin levantar el lápiz ni pasar dos veces por la misma línea”. Alguien te da por ejemplo alguna de estas figuras:

Lo que podemos plantear es un grafo en el cual los segmentos rectos son aristas, y sus extremos son nodos.

Entonces, ¿qué tiene que pasar para que podamos dibujar la figura sin levantar el lápiz? Pensemos que empezamos en uno de nuestros nodos. Entonces vamos a ir recorriendo arista por arista, yendo siempre a nodos adyacentes, hasta pasar por todas. Ahora, si el nodo en el que empezamos terminamos, qué significa? Significa que desde ahí, empezamos “saliendo” y terminamos “entrando”. Quizás en el medio volvimos a pasar por este nodo, pero si volvimos a pasar, necesariamente fue entrando y saliendo, ya que al no poder levantar el lápiz, no podemos entrar y después recorrer una arista que no contenga al nodo. Entonces, básicamente, recorrimos tantas arista desde el nodo, como hacia él. Lo que podemos deducir de acá, es que la cantidad de aristas que tienen al nodo inicial como extremo, debe ser par. Y qué pasa con todos los otros nodos? Bueno, al no empezar ni terminar en ellos, también entramos y salimos la misma cantidad de veces, por lo que también son extremos de una cantidad par de aristas.

Si en cambio, no terminamos en el mismo nodo con el que empezamos, entonces ambos nodos de inicio y final, deben ser extremos de una cantidad impar de aristas.

Y estas son las únicas dos situaciones posibles, ya que si no empezamos desde un nodo sino desde el medio de una arista, y vamos desde ahí hacia un nodo, luego vamos a tener que hacer la otra parte de la arista y obviamente si podemos, podemos también empezar desde uno de estos nodos y terminar el mismo con el mismo camino.

Entonces, sabemos que es condición necesaria que haya $2$ ó $0$ nodos que estén en una cantidad impar de aristas. Puede verse, pensando en esto de “salir” y “entrar” del nodo que es una condición necesaria. Esto de “a cuántas aristas pertenece un nodo” se llama el grado de un nodo, y puede verse junto con otras definiciones acá.

Entonces, si vamos a tener un grafo de $n$ nodos, numerados del $0$ al $n-1$, y $m$ aristas, que nos las darán con dos enteros $u$, $V$ representando a los nodos que une cada arista, podemos chequear los grafos y si la figura puede dibujarse sin levantar el lápiz con este código:

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
 
    int n, m;
    cin>>n>>m;
    vector< vector<int> > grafo(n);
    for(int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }
    int impares=0;
    for(int i=0; i<n; i++){
        if(grafo[i].size()%2==1){
            impares++;
        }
    }
    if(impares==0 || impares==2){
        cout<<"Se puede dibujar"<<endl;
    }else{
        cout<<"No se puede dibujar"<<endl;
    }
}