Teoria de Grafos: Matemáticas Discretas: Teoría de grafos

Teoría de grafos

*Conceptos básicos:

Un grafo es un conjunto de vértices o nodos unidos por aristas o arcos.

La palabra grafo proviene del griego y su significado etimológico es "trazar".

La teoría de grafos o teoría de las graficas, estudia las propiedades de los grafos que son estructuras de dos partes llamadas “Conjunto de vértices” (nodos o puntos) y “Conjunto de aristas” (líneas o lados que bien pueden ser orientados o no) .

Es un tratado que usa diferentes conceptos de diversas áreas como probabilidad, combinatoria, aritmética, etc.

*Componentes de un grafo

Aristas:

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de dirección se denota indistintamente {a,b} o {b,a}, siendo "a" y "b" los vértices que unen.

Si {a,b} es una arista, entonces a los vértices "a" y "b" se les llama sus extremos

Arista Adyacente: Dos aristas son adyacentes si convergen en el mismo vértice.

Arista paralela: Dos aristas son paralelas si el vértice inicias y el final son el mismo.

Arista cíclica: Es la arista que parte de un vértice para entrar en el mismo.

Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que está conformado un grafo. Se dice que un vértice es `par' o `impar' según lo sea su grado (El grado de un vértice es el número de aristas de las que es extremo).

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.

*Clasificación de grafos

Los grafos se pueden clasificar en dos grupos los "dirigidos" y los "no dirigidos".

En un grafo "no dirigido" el par de vértices que representa un arco

(el arco es una relación matemática que conecta dos vértices) no esta ordenado, por lo tanto, las vértices {v1, v2} y {v2,v1} representan un mismo arco.

En un grafo "dirigido" cada arco esta representado por un par ordenado de vértices, de forma que representan dos arcos diferentes.

Ejemplos

G1 = (V1, A1)

V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

G2 = (V2, A2)

V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}

G3 = (V3, A3)

V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }

Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

*Principales tipos de grafos

Grafo regular: Es aquel con el mismo grado (el grado o valencia es el número de aristas incidentes en el) en todos los vértices, si ese grado es "b" se llamara "b-regular".

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias (en un grafo los vértices son adyacentes si están unidos mediante una arista) entre vértices pertenecientes al mismo conjunto.

Grafo completo: Es aquel con una arista entre cada par de vértices. Un grafo completo con "n" vértices se llama "Kn".

Grafo nulo: El grafo nulo es cundo los vértices que lo componen no están conectados (son vértices aislados).

Grafo nulo

Grafo Isomorfo: Los grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno) entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafo Isomorfo

Grafo platónico: Son los grafos formados por los vértices y aristas de los cinco "solidos regulares" o "solidos platónicos" como el tetraedro, el cubo, el octaedro, el dodecaedro, y el icosaedro.

Grafo platónico

*Representación de grafos

Hay tres maneras de representas un grafo en un programa, y es mediante:

-Listas

-Matrices

-Matrices dispersas

Representación mediante listas:

Lista de incidencia: Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.

Lista de adyacencia: Cada vértice tiene una lista de vértices los cuales con adyacentes a el. Esto causa redundancia en un grafo no dirigido (debido a que "a" esta presente en la lista de adyacencia de "b" y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

Lista de grados: También conocida como "Secuencia de grados" o "Sucesión grafica de un grafo no dirigido" es una secuencia de números, que corresponde a los grados de los vértices del grafo.

Representación mediante matrices:

Matriz de adyacencia: El grafo esta representado por una matriz cuadrada "M" de tamaño

n^2

donde "n" es el numero de vértices. Si hay una arista entre un vértice "x" y un vértice "y" entonces el elemento

m_{x, y}

es "1" de lo contrario es "0".

Matriz de adyacencia

Matriz de incidencia: El grado esta representado por una matriz de aristas por vértices, donde {vértice, arista} contiene la información de la arista ( "1" conectado, "0" no conectado).

Matriz de incidencia

Matriz dispersa: Las matrices dispersas contienen tanta información como las matrices de adyacencia, pero, en principio no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, solo representan aquellos enlaces que existen en el grafo.

*Árboles

Es un tipo de grafo que no contiene ciclos, es decir, es un grafo acíclico pero a su vez conexo.

Bosque de árboles

Los bosques de árboles son un caso similar a los árboles, son acíclico, pero no son conexos.

Bosques de árboles

*Aplicaciones

Con la teoría de grafos se pueden resolver diversos problemas como, por ejemplo, la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utilizan para diferentes áreas en todas las ingenierías, un ejemplo seria, el dibujo computacional.

La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red.