Estructura de Datos
Grafos
Es un conjunto de puntos y un conjunto de líneas, cada una de las cuales une un punto con otro. Los puntos se llaman nodos o vértices de un grafo y las líneas se llaman aristas o arcos.
Un grafo consta de un conjunto de nodos(o vértices) y un conjunto de arcos (o aristas). Cada arco de un grafo se especifica mediante un par de nodos. Denotemos al conjunto de nodos de un grafo dado G, por VG y al conjunto de aristas por AG
1. Sea una colección cuyos datos son: 2. Queremos modelar:
1) ciudades 1) rutas entre ciudades
2) aeropuertos 2) rutas aéreas
3) computadores de una red 3) envío d correo electrónico
4) puntos del plano de una ciudad 4) recorridos turísticos
Ejemplo: el grafo G
VG= {a, b, c, d}
AG= {1, 2, 3, 4, 5, 6, 7, 8}
Relación binaria entre los datos de la colección:
- Una relación R sobre un conjunto G se define como un conjunto de pares (a, b) / a, b є G
- Si (a, b) є R, se escribe “a R b” y denota que a está relacionado con b
Ejemplo: grafo cuyos vértices (G) se relacionan vía aristas (R)
G = {Ciud1, Ciud2, Ciud3, Ciud4, Ciud5}
R = {(Ciud2, Ciud3), (Ciud3, Ciud4), (Ciud3, Ciud5), (Ciud1, Ciud5), (Ciud1, Ciud3)}
El número de elementos de V G es llamado orden del grafo G. Un grafo nulo es un grafo con orden cero.
Una arista esta determinada por los nodos que conecta. Un grafo esta completamente definido por sus conjuntos de nodos y aristas. La arista 4, por ejemplo, conecta los nodos c y d y se dice que es de la forma (c,d).
Nótese que puede haber varias aristas conectando a dos nodos, por ejemplo, las aristas 5, 6, 7 todas de la forma (b, d). Algunos pares de nodos pueden estar desconectados, por ejemplo, no hay aristas de la forma (a, c) o (a, d). Algunas aristas pueden conectar un nodo a si mismo, por ejemplo, la arista 8 es de la forma (a, a), a estas aristas se llaman bucles.
VG= {a, b, c, d}
AG= {1, 2, 3, 4, 5, 6, 7, 8}
Grafos dirigidos (Dígrafos)
En grafos dirigidos se impone un sentido a los enlaces. Cada arista del grafo dirigido incluye una flecha para indicar la dirección.
La punta de cada flecha representa el segundo nodo del par ordenado de nodos que constituye un arco y la cola de la flecha representa el primer nodo del par, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. Los enlaces son entonces pares ordenados de nodos, con (a,b) ≠ (b,a), como en el ejemplo:
En este grafo hay un enlace en el nodo (c) que tiene su inicio y termino en el mismo, es un lazo (o rizo, bucle). También hay un enlace sin flecha: significa que el enlace se puede recorrer en cualquier sentido: es bidireccional, y corresponde a dos enlaces orientados.
G = (V, E), V = { a, b, c, d, e }, y E = { (a,c), (d,a), (a,e), (b,e), (c,a),(c,c), (d,b) }.
Del vértice d sólo salen enlaces: es una fuente (source). Al vértice e sólo entran enlaces: es un pozo (sink).
Grafos no dirigidos
En este el par de vértices que representa un arco no están ordenados. Cuando no importa la dirección de una arista, el grafo se denomina no dirigido, una aplicación de los grafos no dirigidos, es la red de computadoras de una empresa, en donde los vértices están representados en las terminales de los computadores y las aristas son el cableado o en su defecto la conexión inalámbrica.
En ese sentido la información de la red se da en ambos sentidos al enviar y recibir información de cada terminal.
En ese sentido la información de la red se da en ambos sentidos al enviar y recibir información de cada terminal.
Los arcos en el grafo no tienen una dirección particular, es decir, son bidireccionales.
Multigrafo
Es un grafo no orientado con múltiples aristas entre pares de nodos.
Un multigrafo G(V, E) consta de un conjunto V de vertices,un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Sedice que las aristas e1, e2 son aristas múltiples o paralelas si f(e1) = f(e2).
Pseudografo
Pseudografo o un multígrafo en un grafo añadiendo un vértice en medio de cada lazo o de algunas aristas múltiples. En las siguientes figuras, añadiendo vértices y uniéndolos mediante aristas, se han convertido el pseudografo y el multígrafo en grafos.
Adyacencia
En un grafo, los vertices son adyacentes si están unidos mediante una arista.
Sea G= (V, A) un Grafo. Si (u, v) є A, decimos que el vértice v es adyacente al vértice u.
Grafos ponderados o etiquetados.
En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así ungrafo valuado.
Formalmente, es un grafo con una función v: A → R+.
Formalmente, es un grafo con una función v: A → R+.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.
Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.
Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.
Grafo etiquetado
Grafos en los cuales se ha añadido un peso a las aristas o un etiquetado a los vértices
Un Grafo Etiquetado, es un grafo G = (V,E) sobre el que se define una función f: E → A, dónde A es un conjunto cuyas componentes se llaman Etiquetas.
NOTA: la función de etiquetado se puede definir también sobre V, el conjunto de Vértices
Un Grafo Ponderado, es un Grafo Etiquetado (sus Aristas) con números Reales (A ≡ ℜ)
Grafo nulo
Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados. No tiene vértices ni aristas, El grafo nulo es un caso particular de grafo vacío, para los cuales sólo es requisito que el conjunto de aristas sea vacío.
Grafo trivial
Aquel que tiene un vértice y ninguna arista.
Grafo simple
Aquel que no posee bucles o lazos. Un grafo simple es un grafo o digrafo que no tiene bucles, y que no es un multigrafo.
- No tiene ciclos, esto es, no existe una arista en AG de la forma (v, v), donde v esta en VG
- No hay más de un arista uniendo un par de nodos, esto es, no existe más de una arista en AG de la forma (v1, v2), para cualquier par de elementos v1y v2 en VG.
Grafo completo
Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista. 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, siendo el grafo completo de n vértices.
Grafo bipartito
Sea (W,X) una partición del conjunto de vértices V, es aquel donde cada arista tiene un vértice en W y otro en X.
Grafo bipartito completo
Sea (W,X) una partición del conjunto de vértices V, es aquel donde cada vértice en W es adyacente sólo a cada vértice en X, y viceversa.
Grafos planos
En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano)
Grafo rueda
Un grafo rueda (Wn), o simplemente rueda, es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo (n-1)
Grafos perfectos
Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos.
Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias.
Autores:
Jesus Nuñez 23.952.796
Ivan Del Pino 20.897.704
