GRAFOS
El término grafo proveniente de la antigua Grecia puede ser traducido como dibujo o
imagen. Existen diferentes tipos de grafos que podemos utilizar para nuestros proyectos
digitales. Sus características permiten un sinfín de posibilidades en análisis y soluciones de
datos.
HISTORIA
EN 1936, EL MATEMÁTICO LEONHARD EULER ESCRIBIÓ UN ARTÍCULO
ANALIZANDO EL PROBLEMA DEL PUENTE DE KÖNIGSBERG, LA CUAL
SE BASABA EN RECORRER LA CIUDAD ATRAVESANDO CADA UNO DE
LOS PUENTES DE LA CIUDAD Y VOLVER AL PUNTO DE PARTIDA. LA
CONCLUSIÓN PARA ÉSTA TEORÍA DE GRAFOS ERA QUE DEBÍA PASARSE
AL MENOS DOS VECES POR ALGUNO DE LOS PUNTOS PARA HACER EL
RECORRIDO DESEADO, ESTO DIO INICIO A LA TEORÍA DE POS GRAFOS.
¿QUÉ ES UN GRAFO?
Conjunto de puntos o vértices unidos por líneas o aristas que nos permite representar
interrelaciones entre elementos que interactúan unos con otros. Los grafos permiten
estudiar las relaciones que existen entre unidades que interactúan con otras.
DEFINICIÓN
UN PAR ORDENADO COMPUESTO POR VÉRTICES (V) Y ARISTAS “E”, DONDE EN LA GRAN MAYORÍA DE LOS CASOS LOS
VÉRTICES SON DE CUANTIFICACIÓN FINITA. EXISTE TAMBIÉN EL CONCEPTO DE GRADO QUE SE CORRESPONDE AL
NÚMERO DE ARCOS AL QUE PERTENECEN DE FORMA EXTERNA Y EN CUANTO A LAS ARISTAS TAMBIÉN CONSEGUIMOS
EL CONCEPTO DE BUCLE QUE NO ES MÁS QUE UNA ARISTA RELACIONADA DE DIVERSAS FORMAS CON EL MISMO NODO.
TIPOS DE GRAFOS
1. GRAFOS DIRIGIDOS: TAMBIÉN CONOCIDO COMO DÍGRAFO: GRAFOS CUYAS ARISTAS
SON TODAS DIRIGIDAS. LAS ARISTAS DEPENDIENDO DE SU SALIDA O INGRESO
RECIBEN LA CALIFICACIÓN DE ENTRANTE O SALIENTE, LA CONDICIÓN COMÚN, ES
QUE SIEMPRE TIENEN UN DESTINO HACIA UN NODO.
2. GRAFO NO DIRIGIDO: LOS GRAFOS NO DIRIGIDOS SON
AQUELLOS QUE CONSTAN UN CONJUNTO DE VÉRTICES QUE
ESTÁN CONECTADOS A UN CONJUNTO DE ARISTAS DE FORMA NO
DIRECCIONAL, ES DECIR GRAFO CUYAS ARISTAS SON TODAS NO
DIRIGIDAS.
• GRAFOS MIXTOS: POSEEN ARISTAS DIRIGIDAS Y NO DIRIGIDAS.
Tipo de Grafo Mixto: Tiene aristas dirigidas y no dirigidas
Vértices:
{a,b,c,d,e}
Aristas:
a={b,c,d}, b={e}, c={a,d,e},
d={a,c}, e={d},
Vértices Adyacentes:
a= {b,c,d}, b={e}, c={a,d,e}, d={a,c}, e={d}
• COMO YA HEMOS PODIDO OBSERVAR LOS GRAFOS SON UN MUNDO POR SÍ
SOLO. CONTIENEN UN CONJUNTO DE CARACTERÍSTICAS Y DINÁMICAS
OPERATIVAS QUE LOS CONVIERTEN EN UNA COMBINACIÓN INTERESANTE DE
DATOS E INFORMACIÓN DE MUCHA UTILIDAD PARA EL MUNDO
EMPRESARIAL.
RELACIONES BINARIAS
Llamamos relación binaria a la relación R existente entre dos elementos a y b, de dos conjuntos A y B
respectivamente. Indicando que el elemento a está relacionado con b. Esta relación
Se puede denotar de diversas formas:
1- Como pares ordenados (a, b).
2- Indicando que aRb.
3- Como una mezcla entra los dos anteriores R(a,b).
EJEMPLO: SEA EL CONJUNTO A={EL CONJUNTO DE LOS NÚMEROS NATURALES}, UNA RELACIÓN BINARIA DEL
CONJUNTO DE A SOBRE SÍ MISMO PUEDE SER, R= SER MÚLTIPLO DE.
DE TAL FORMA QUE, POR EJEMPLO 4 ESTÁ RELACIONADO CON 2 (ES DECIR, 4 ES UN MÚLTIPLO DE 2), POR TANTO
ESCRIBIMOS 4R2 O (4,2).
EN EL CASO DE NO ESTAR RELACIONADOS ESCRIBIREMOS A NO ESTÁ RELACIONADO CON B TACHANDO LA R.
UN EJEMPLO DE DOS ELEMENTOS QUE NO ESTÁN RELACIONADOS CON ESTA RELACIÓN SON 3 Y 5.
OBSERVACIÓN: EL CONJUNTO R(AXB) DE TODOS LOS ELEMENTOS QUE ESTÁN RELACIONADOS ES UN SUBCONJUNTO
DEL PRODUCTO CARTESIANO AXB.
FORMAS DE REPRESENTACIÓN
A)EL DIAGRAMA CARTESIANO: REPRESENTAREMOS LOS EJES CARTESIANOS Y LOS ELEMENTOS DE
CADA CONJUNTO A TRAVÉS DE RELACIONES DE PUNTOS.
b) DIAGRAMA SAGITAL O FLECHAS: MEDIANTE DIAGRAMAS DE VENN, REGRESAMOS POS
ELEMENTOS DE CADA CONJUNTO DENTRO DEL CÍRCULO Y LAS RELACIONES A TRAVÉS DE
FLECHAS. EJEMPLO: REPRESENTAR LA SIGUIENTE RELACIÓN:
R(M)={(A,B), (B,C), (D,B)}
A) LO REPRESENTAREMOS EN PRIMER LUGAR UTILIZANDO EL DIAGRAMA CARTESIANO, EN
ESTE
CASO UTILIZANDO LA CUADRÍCULA:
B) UTILIZANDO EL DIAGRAMA SAGITAL, (LA PUNTA DE LA FLECHA INDICA LA DIRECCIÓN DE
LA RELACIÓN:
DOMINIO Y RANGO DE UNA RELACIÓN
DOMINIO ES EL CONJUNTO DE LAS PRIMERAS DE COORDENADAS O EL CONJUNTO DE
PARTIDA DE R.
RANGO: ES EL CONJUNTO DE LLEGADA DE R QUE ESTÁ RELACIONADAS.
Ejemplo 3
Sea A = {1, 2, 3, 4} y B = {4, 5, 6, 7, 8} y R la relación definida de A en B determinada por la
regla “y es el doble de x” o “y = 2x”, encontrar dominio y rango de la relación.
Solución
El total de pares ordenados que podemos formar, o producto cartesiano es:
A x B = {(1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6),
(3, 7), (3, 8), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8)}
Pero los pares que pertenecen a la relación R (y = 2x) son solo:
R = {(2, 4), (3, 6), (4, 8)}
En esta relación vemos que: “4 es el doble de 2”; esto es, “4 es la imagen de 2 bajo R”, dicho
de otro modo, “2 es preimagen de 4”.
Así, el dominio y rango son:
D = {2, 3, 4}
Rg = {4, 6, 8}
Según lo que vemos, ¿Qué relación hay entre el Dominio y el conjunto de partida?
En el Dominio falta el elemento 1 del conjunto de partida, por lo tanto el Dominio es un
subconjunto de A.
Otra pregunta: ¿Todo elemento del conjunto de llegada es elemento del rango?
La respuesta es no, pues en el rango faltan el 5 y el 7.
