Teoria De Grafos

UNIDAD ACADEMICA DE CIENCIAS DE LA INGENIERIA Y APLICADAS
CARRERA: INGENIERÍA EN INFORMÁTICA Y SISTEMAS
COMPUTACIONALES
NOMBRE: PATRICIA ALAJO
NIVEL: 4to SISTEMAS “A”
DOCENTE: ING. JAIME CAJAS
ASIGNATURA: MATEMÁTICAS DISCRETAS

OBJETIVO GENERAL:

Profundizar el conocimiento en la teoría de grafos con el objeto de adquirir cierto grado de especialización en la misma con el fin de reafirmar lostemas que vamos a estudiar.

MARCO TEÓRICO:

TEORIA DE GRAFOS
En matemáticas y en ciencias de la 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). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no.Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Diagrama de un grafo con 6 vértices y 7 aristas.

GRAFO
Un grafo es una pareja de conjuntos, donde es el conjunto de vértices, y es el conjunto de aristas, este último es un conjunto de pares de la forma tal que . Para simplificar, notaremos la arista como .
En teoría de grafos,sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

EJEMPLOS:

Los ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama), grafos matemáticos que representan lasrelaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad.(Véase la figura 1).En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).

Si las aristas tienen asociada una dirección(las aristas (x,y) y (y,x) no son equivalentes) diremos que elgrafo es dirigido,en otro caso ((x,y)=(y,x)) diremos que el grafo es no dirigido.

Dado un grafo G=(V,A),diremos que G'=(V,A') con es un grafo parcial de G y un subgrafo de G es todo grafo G'=(V',A') con y donde A' será el conjunto de todas aquellas aristas que unían en el grafo G dos vértices que están en V'. Se Podrían combinar ambas definiciones dando lugar a lo que llamaremos subgrafo parcial.Donde A' está construido de la siguiente forma: si e1,e2 pertenece a A son adyacentes --> (e1,e2)pertenece a A' con e1,e2 pertenece a V'.En definitiva, para construir un grafo dual se cambian vértices por aristas y viceversa.

DIGRAFOS
Dígrafo: pseudografo dirigido que tiene a lo sumo:
• Un bucle por vértice
• Entre vértices distintos dos aristas con distintas orientaciones
Camino dirigidov1, v2, …, vn (n≥1) distintos / vivi+1 ∈ A
Ciclo dirigido v1, v2, …, vn (n≥2) distintos salvo v1 = vn / vivi+1 ∈ A

Orden inducido por un digrafo acíclico
u ≤ v (u es anterior o igual a v) si existe un camino dirigido de u a v
Es relación de orden (reflexiva, antisimétrica, transitiva)

Un orden topológico representa una secuenciación de las tareas modernizadas mediante el dígrafo

EJEMPLO:
Dado unconjunto de tareas {T1, …, Tn}, una planificación es una colección de listas disjuntas y no vacias cuya “unión” es el conjunto inicial. Una planificación de K listas representa un reparto de tareas entre K equipos.
MULTIGRAFOS
Definición:
Sea G = (V, E) un grafo dirigido, donde V es un conjunto y E es un multiconjunto de pares ordenados de V V. G es llamado un multigrafo dirigido ygeométricamente puede representarse como un conjunto de vértices V y un conjunto de flechas E entre los vértices, donde no existe restricción en el numero de flechas de un vértice a otro.

Multígrafo Dirigido
Ahora consideremos una representación gráfica de un mapa de carreteras en el cual una arista entre dos ciudades corresponde a un carril en una autopista entre las dos ciudades. Como a menudo hay...