Teoría de Grafos

Teoría de Grafos

Nombre: Oscar Vega González Matrícula: 13191205055 Grupo: 7VSC2

Concepto:

En matemáticas y en ciencias de computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas).

Historia

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos.

Estructuras de Datos

Estructura de lista

Existen diferentes formas de almacenar grafos en una computadora.

Lista de incidenciaLista de Adyacencia

Grafo

Un grafo es una pareja de conjuntos G=(V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, ese último es un conjunto de pares de la forma (u,v) tal que u,v E V.

Subgrafo

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G.

El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vertices de G.

Definición:

Sea G=(V,A). G'=(V',A') se dice subgrafo de G si:1- V' C V 2- A' C A 3- (V',A') es un grafo

G2 es un subgrafo de G

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas.

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice.

Ciclos y caminos hamiltonianos

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (exepto el vértice del que parte y al cual llega).

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).

Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada.

Ejemplo

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas de una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las artistas los corredores o puertas entre ellas).

Caracterización de grafos

Grafos simples:Un grafo es simple si a lo más existe una arista uniendo dos vértices cuales quiera.

Grafos conexos:Un grafo es conexo si cada par de vértices esta conectado por un camino; es decir, si para cualquier par de vértices (a,b), existe al menos un camino posible desde a hacia b.

Grafos completos

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices(a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente k, siendo kn el grafo completo de n vértices.

Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2 aristas. La representación gráfica de los Kn como los vértices de un polígono regular de cuenta de su peculiar estructura.

Grafos bipartios

Un grafo G es bipartito si puede expresarse como G= V1 U V2, A (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones: . V1 y V2 son disjuntos y no vacíos. .Cada arista de A une un vértice de V1 con uno de V2. .No existen aristas uniendo dos elementos de V1; análogamente para V2.

+ info

Operaciones en Grafos

Subdivisión elemental de una arista:

u e v se convierte en u e' w e'' v. Se reemplaza la arista e= u,v por dos aristas e'= u,w e''=w,v y un vértice w. Después de realizar esta operación, el grafo queda con un vértice y una arista más. Eliminación débil de un vértice: Si v E Vg y g(v) =2 (Sea v un vértice del grafo y de grado dos) eliminarlo débilmente significa reemplazarlo por una arista que une los vértices adyacentes a v. U e' w e'' v se convierte en u e v. Entonces e' y e'' desaparecen y aparece e=u,v.

Árboles

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n-1 aristas y hay n^n-2 árboles posibles.

Teorema de los cuatro colores

Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color?

Coloración de Grafos

Definición: Si G= V,E es un grafo no dirigido, una coloración propia de G de modo que si a,b es una arista en G entonces a y b tienen diferentes colores.

Grafos Planos

Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos.

Diámetro

En un grafo, la distancia entre dos vértices es el menor número de aristas de un recorrido entre ellos. El diámetro, en una figura como en un grafo, es la mayor distancia entre dos puntos de la misma.

Algoritmos importantes

.Algoritmo de búsqueda en anchura (BFS).Algoritmo de búsqueda en profundidad (DFS) .Algoritmo de búsqueda A*. .Algoritmo del vecino más cercano. .Ordenación topológica de un grafo .Algoritmo de cálculo de los componentes fuertemente conexos de un grafo .Algoritmo de Dijkstra .Algoritmo de Bellman-Ford .Algoritmo de Kruskal .Algoritmo de Floyd-Warshall

Aplicaciones

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura.

Investigadores relevantes en Teoría de grafos

.Leonhard Euler .Edsger Dijkstra .Paul Erdos .Frank Harary .Dénes König .Kazimierz Kuratowski .Gerhard Ringel .W.T Tuttle