Vocabulario Teoría de Grafos

Enviado por mbalsells el Dom, 22/09/2019 - 18:07

Un grafo es un conjunto de vértices (o nodos) y un conjunto de aristas (o arcos) que los unen. Gráficamente, se suelen representar los vértices como puntos en el plano y las aristas como segmentos que los unen.

Grafo de ejemplo

 

Conceptos de grafos

Veamos una serie de conceptos que se emplean frecuentemente en el campo de teoría de grafos:

Decimos que dos nodos están conectados si podemos ir de uno a otro a través de arcos:

Grafo de ejemplo

Por ejemplo, el nodo 1 i el nodo 2 están conectados, pero el nodo 5 y el 4 no. Si todos los nodos están conectados hablamos de grafo conexo. Decimos que todos los nodos que están conectados entre sí forman una componente conexa así pues los nodos verdes forman una componente conexa y los nodos azules forman otra componente conexa. 

Grado de un nodo: Es el número de aristas conectadas al nodo.

Grafo dirigido: Grafo en el que los arcos tienen sentido. Si los arcos no tienen sentido hablamos de un grafo no dirigido

Grafo de ejemplo

Por ejemplo, este grafo es dirigido, mientras que los anteriores no lo eran. En el contexto de grafos dirigidos, decimos que un conjunto de vértices forman una componente fuertemente conexa si es posible ir de un nodo cualquiera del conjunto a cualquier otro, en el ejemplo cada una de las componentes conexas tiene asignada un color.

 

Grafo ponderado (o con pesos)Grafo en el que las aristas tienen un peso asociado

Grafo de ejemplo

 

Camino: Es un grafo en el que podemos nombrar a los nodos de modo que dos nodos están conectados si i solo si su diferencia es 1.

Grafo de ejemplo

Ciclo: Es un conjunto de nodos donde cada uno está conectado al siguiente y el ultimo al primero

Grafo de ejemplo

Grafo completo: Es un grafo en el todo par de vértices están conectados.

Grafo de ejemplo

Grafo bipartido: Grafo en el que podemos agrupar los vértices en dos clases, de modo que no haya arcos entre los vértices de una misma clase.

Grafo de ejemplo

Árbol: Grafo conexo y sin ciclos:

Grafo de ejemplo

A un conjunto se árboles se le llama bosque. En determinadas ocasiones podemos considerar que el árbol tiene un nodo principal, en este caso hablamos de árbol arraigado, en este tipo de árboles a los nodos adyacentes más lejanos de la raíz se les llama hijos, mientras que al nodo adyacente más cercano a la raíz se le llama padre, finalmente, a los nodos sin hijos se les llama hojas.

Grafo de ejemplo

Por ejemplo, en este grafo, si consideramos que el nodo 0 es la raíz del árbol, entonces 1 tiene dos hijos, el 4 y el 5 y su padre es el 0, en el mismo ejemplo los nodos verdes serían hojas. A los árboles en los que cada nodo tiene como mucho 2 hijos se les llama árbol binario.

Grafo generador: Grafo que resulta de extraer un cierto número de aristas (pueden ser 0) de un grafo.

Árbol generador: Grafo que resulta de extraer un cierto número de aristas (pueden ser 0) de un grafo, de modo que el grafo resultante sea un árbol.

 

Implementación

En el código, hay tres maneras habituales de representar un grafo:

  • Como conjunto de arcos, donde guardamos las parejas de vértices conectados. En caso que el grafo sea ponderado se guardan tuplas.

 

  • Como matriz de adyacencia, donde por cada par de vértices sabemos si hay un arco que los una o no. Si N es el tamaño del grafo, se guarda una tabla G[N][N] donde la entrada G[v][u] determina la información de la arista entre v y u. Habitualmente, G[v][u] valdrá 1 si existe un arco de v a u, y 0 en caso contrario. Sin embargo podemos modificarlo dependiendo del problema con el que trabajemos, por ejemplo, si queremos guardar un grafo con pesos positivos, la entrada G[i][j] valdrá el peso de la arista si existe, y -1 si no existe (podríamos usar cualquier otro número negativo o incluso asignarle un valor infinito según el problema).

 

  • Como lista de adyacencia. Guardaremos una lista G[N], donde cada entrada G[v] será una lista de los nodos adyacentes a v. En C++, podemos representarlo como vector<vector<int> > G. En caso de tener pesos, habrá que guardar también el peso de la arista, usando por ejemplo pair<int, int>. Otra opción sería tener un vector <vector <int> > W auxiliar de modo que si G[v][i] = u entonces W[v][i] es el peso del arco que va de v a u. Vea el código de las soluciones para encontrar más detalles sobre como usar esta estructura.

 

Por norma general, acostumbra a ser más eficiente usar la última estructura.  

Printer Friendly, PDF & Email

Etiquetas

Añadir nuevo comentario

HTML Restringido

  • Etiquetas HTML permitidas: <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol type start> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • Saltos automáticos de líneas y de párrafos.
1 + 1 =
Resuelva este simple problema matemático y escriba la solución; por ejemplo: Para 1+3, escriba 4.