Redes

Capitulo 2: TEORÍA DE GRAFOS

INTRODUCCIÓN
La Teoría de Grafos es parte de Matemáticas Discreta que es una asignatura del plan de estudios de Ingeniería en Informática, que tiene un marcado enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo. El contenido referido a esta temática se plantea como respuesta a una variada serie de problemas de la «vida real»(diseño de bloques, flujo de redes, diseño de circuitos, transporte de viajeros, asignaciones horarias o de tareas, programación, etc.), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional. El tratamiento que se pretendedar a la asignatura es práctico pues, aparte de la resolución de ejemplos y ejercicios que tiene que desarrollar sobre el papel, se debe dedicar una buena parte de tiempo a realizar prácticas en el computador para resolver algún problema en lo posible concreto (extraído de un caso real).

G1 es un grafo no simple, pues consta de dos lados paralelos e2 y e3 y dos lazos e1 y e4, pues e2 = (V1,V2), e3 = (V1, V2) y e1 es un lazo, pues e1 = (V1, V1)
GRAFOS
Existen varios tipos de grafos:
a) Un GRAFO NO DIRIGIDO G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asocia con un par no ordenado de vértices. Entonces se puede decir que si existe una arista e entre un par de vértices v y w, esta puede ser igual a: e = ( v, w) oe = ( w, v)

Un grafo esta formado de vértices y aristas (lados), por lo tanto G = {V, E}
Los vértices del grafo G son: V_1, V_2, V_3, V_4 entonces V = {V_1, V_2, V_3, V_4}
Las aristas del grafo son: e_1, e_2, e_3, e_4 entonces E = {e_1, e_2, e_3, e_4}
Entonces podemos decir que G = {{V_1, V_2, V_3, V_4}, {e_1, e_2, e_3, e_4}}
Como el grafo G no tiene lazos ni lados paralelos entonceses un grafo simple.
Otro ejemplo de grafo no dirigido es el siguiente:

El grafo no dirigido permite que diferentes aristas se asocien con el mismo par de vértices. Como podemos apreciar todas las aristas que se asocien con el mismo par de vértices se denomina aristas paralelas, para el gráfico serian e1 y e2 pues convergen en los vértices (V1, V2). Denominamos lazo a aquella arista queinciden en un mismo vértice para la grafica sería e3, debido a que incide en el vértice V2; e3 = (V2, V2). Un vértice como V4 que no incide en ninguna arista se llama vértice aislado.
Un grafo que contiene lazos y aristas paralelas se llama grafo no simple.
b) Un GRAFO DIRIGIDO G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asociacon un par ordenado de vértices. Si hay una única arista e asociada con el par ordenado (v, w) de vértices, se escribe e = (v, w), que denota una arista de v a w. En la grafica dirigida sus aristas dirigidas se indican por flechas.

La arista e_3 se asocia con el par ordenado de vértices (V_4,V_3) debido a que tiene como vértice origen a V_4 y vértice destino a V_3, y se denota por: e_3 ={V_4, V_3}. No se puede decir que: e_3 = {V_3, V_4} porque la dirección de la arista e_3 no es esa.
c) Un GRAFO PONDERADO G es aquel en donde se muestran los pesos de cada una de sus aristas. Peso es el valor asignado a cada arista. En un grafo ponderado la longitud de una ruta es la suma de los pesos de las aristas en la ruta.

Ejercicio
Complete el cuadro, con la longitud de las diferentesrutas del grafo G expuesto arriba.

d) GRAFO COMPLETO sobre n vértices, denotada por Kn, es la gráfica simple con n vértices en la que hay una arista entre cada par de vértices distintos.

G de K_4 y tiene solo una arista entre cada par de vértices.
e) GRAFO DE SIMILITUD se refiere a un grafo que tiende a agrupar objetos semejantes en clases, con base en las propiedades de los objetos. En...