Introducción.
Son artefactos matemáticos que permiten expresar de
una forma visualmente muy sencilla y efectiva las relaciones que se dan entre
elementos de muy diversa índole. Un grafo simple está formado por dos
conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
‘‘Un conjunto de pares
de vértices que se llaman aristas o arcos y que indican qué nodos están
relacionados. De una manera más informal podemos decir que un grafo es un
conjunto de nodos con enlaces entre ellos, denominados aristas o arcos’’.
Tipos de grafos.
- Grafo simple. o simplemente grafo es
aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto
es equivalente a decir que una arista cualquiera es la única que une dos
vértices específicos. Es la definición estándar de un grafo.
- Multígrafo. Es
el que acepta más de una arista entre dos vértices. Estas aristas se
llaman múltiples o lazos (loops en inglés). Los grafos simples son una
subclase de esta categoría de grafos. También se les llama grafos
general.
- Pseudografo. Si incluye algún lazo.
- Grafo orientado, dirigido o dígrafo. Son
grafos en los cuales se ha añadido una orientación a las
aristas, representada gráficamente por una flecha.
- Grafo etiquetado. Grafos en los cuales se ha añadido un peso a
las aristas (número entero generalmente) o un etiquetado a
los vértices.
- Grafo aleatorio. Grafo cuyas aristas están asociadas a
una probabilidad.
- Hipergrafo.
Grafos en los cuales las aristas tienen más de dos extremos, es decir, las
aristas son incidentes a 3 o más vértices.
- Grafo infinito. Grafos con conjunto de vértices y aristas
de cardinal infinito.
Partes de un grafo
Un grafo (G) es un
diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).
Considérese el
siguiente grafo:
A partir de esta
figura se definen los siguientes elementos:
Vértices (nodos)
Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a,b,c,d}.
Lados (ramas o
aristas)
Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}.
Es el número de lados
que salen o entran a un vértice. En el grafo anterior las valencias de los vértices
son:
Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3
Hay que observar como
en el caso del vértice del lazo solo se considera una vez, entrada o salida
pero no ambos.
Lados paralelos
Son aquellas aristas que tienen relación con un mismo par de vértices.
Nodo.
En términos generales, un nodo es un espacio en el que confluyen parte de las conexiones de otros
espacios reales o abstractos que comparten sus mismas características y que a
su vez también son nodos. Todos se interrelacionan de una manera no jerárquica
y conforman lo que en términos sociológicos o matemáticos se llama red. El concepto de red puede definirse como
"conjunto de nodos interconectados. Un nodo es el punto en el que una
curva se interseca consigo misma. Lo que un nodo es concretamente, depende del
tipo de redes a que nos refiramos".
En informática, un nodo es un «punto de intersección o unión de varios elementos que
confluyen en el mismo lugar». Por ejemplo: en una red de ordenadores cada una
de las máquinas es un nodo, y si la red es Internet, cada servidor constituye
también un nodo.
En programación, concretamente
en estructuras de datos, un nodo es uno de los elementos de
una lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir
de esa referencia, será posible en teoría tener acceso a otros nodos de la
estructura. Los nodos son herramientas esenciales para uno de los procesadores
que lo componen.
Video:
Ramas y lazos.
Ramas.
Es un elemento o grupo de elementos que presenta
dos terminales. Algunas veces se denomina también lado. Únicamente
consideraremos que una agrupación de elementos de dos terminales A y B forma
una rama, cuando se conocen los parámetros y la relación que liga la tensión
entre A y B con la intensidad que pasa a través de esos terminales. En
particular, pueden considerarse constituyendo una rama aquellos elementos que
son del mismo tipo, y pueden reducirse a un solo elemento equivalente.
Lazo.
Es un conjunto de ramas que forman una línea
cerrada, de tal forma que si se elimina cualquier rama del lazo, el camino
queda abierto. Cuando un vértice esta unido consigo mismo.
Valencia.
Caminos.
Ramas paralelas.
Grafos simples, de
similaridad, bipartidos y completos.
Un grafo es simple si
a lo sumo existe una arista uniendo dos vértices cualesquiera. Esto es
equivalente a decir que una arista cualquiera es la única que une dos vértices
específicos. Un grafo que no es simple se
denomina multigrafo.
Grafos de similaridad.
Dos grafos son similares si tienen igual número de nodos o vértices y el
mismo número de aristas o lados.
Grafos bipartitos:
Se dice que es un grafo bipartito G cuando un
conjunto de nodos N se puede particionar en dos subconjuntos P y Q tales que,
cada segmento de G, conecta un nodo de P con un nodo Q.
Ejemplos
Grafos completos.
Un grafo completo
es cuando cada nodo esta conectado con otro nodo. Al grafo completo de n nodos
se le denota K.
Representación matricial de grafos.
Definiciones básicas
Un grafo G es un par (V,E) donde V
es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV
(conjunto de aristas).
Gráficamente representaremos los
vértices por puntos y las aristas por líneas que los unen.
Un vértice puede tener 0 o más
aristas, pero toda arista debe unir exactamente 2 vértices.
Llamaremos orden de un grafo a su
número de vértices, |V|.
Si |V| es finito se dice que el
grafo es finito. En este curso estudiaremos los grafos finitos, centrándonos
sobre todo en grafos no dirigidos. También supondremos, a no ser que se diga lo
contrario, que entre dos vértices hay, como mucho, una arista y que toda arista
une dos vértices distintos.
Aristas.
Si la arista carece de dirección
se denota indistintamente {a,b} o {b,a}, siendo a y b los vértices que une.
Si {a,b} es una arista, a los
vértices a y b se les llama sus extremos.
Vértices.
Dos vértices v, w se dice que son
adyacentes’ si {v,w}ÎA (o sea, si existe una arista
entre ellos)
Llamaremos grado de un vértice al
número de aristas de las que es extremo. Se dice que un vértice es ‘par’ o ‘impar’
según lo sea su grado.
Caminos.
Sean
x, y Î V,
se dice que hay un camino en G de x a y si existe una sucesión finita no vacía
de aristas {x,v1}, {v1,v2},…, {vn,y}. En este caso x e y se llaman los extremos del
camino.
- El número de aristas del camino se llama la longitud del camino.
- Si los vértices no se repiten el camino se dice propio o simple.
- Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
- Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
- Llamaremos ciclo a un circuito simple.
Un grafo o un dígrafo determina una relación en n
por lo que podemos representarlos mediante una matriz llamada de ADYACENCIA,
para esto, primero se ordenan los nodos y se forma la matriz.
1
|
2
|
3
|
4
|
|
1
|
0
|
1
|
0
|
0
|
2
|
0
|
0
|
1
|
1
|
3
|
0
|
0
|
0
|
0
|
4
|
0
|
0
|
1
|
0
|
Rama matriz de
adyacencia e incidencia.
Los grafos se
representan en memoria secuencial mediante matrices de adyacencia.
Una matriz de
adyacencia, es una matriz de dimensión n • n, en donde n es el número de
vértices que almacena valores booleanos, donde matriz M[i, j] es verdadero si y
solo si existe un arco que vaya del vértice i y al vértice j.
Caminos.
Se llama caminos a una secuencia de aristas (V1, V2, V3...VN) de la
manera que el vértice final de cada uno
sirve de vértice inicial al siguiente.
Camino en un grafo es una
sucesión de vértices y arcos.
·
Al número de arcos que atraviesa el camino se le
denomina Longitud del camino.
·
Camino de longitud 0 es aquel constituido
únicamente por un vértice.
·
Extremos del camino son los vértices inicial y
final.
·
Vértices interiores son aquellos situados entre los
extremos del camino.
Tipos de caminos:
El camino elemental o trayectoria: es un camino que pasa por una serie
de vértices una sola vez. Es decir, es
aquel que no pasa 2 veces por un mismo vértice, salvo, excepcionalmente, que el
vértice que se repite sea el inicial y el final.
Camino simple o sendero: es un camino que pasa por una serie de aristas una
sola vez. Todo camino elemental es un
camino simple, pero la inversa puede no
cumplirse.
Circuito o ciclos: es un camino cerrado, el vértice final coincide con
el vértice inicial. Un camino o un circuito se llaman hamiltoniano si pasa una sola vez por todos los
vértices del grafo, y se denomina euleriano si pasa una sola vez por todas las
aristas del grafo.
Camino cerrado: es
aquel cuyo vértice final coincide con el vértice inicial.
Ciclo: es un camino simple, elemental y cerrado, de
longitud positiva (n > 0) El ciclo más elemental es un bucle (también reciben el
nombre de lazo o rizo).
Isomorfismo.
Sean G1= (V1, E1) y G2= (V2 E2)
dos grafos no dirigidos. Una función ƒ: V1 →V2 es un isomorfismo de grafos si
(a)ƒes inyectiva y sobre y (b) para todos a, b ∈V1 {a, b} ∈ E1
si y sólo si {ƒ(a), ƒ(b)} ∈E2. Cuando existe tal función, G1 y G2 son grafos
isomorfos
La correspondencia de vértices de
un isomorfismo de grafos mantiene las adyacencias. Puesto que el hecho de que los pares de vértices sean
adyacentes o no es la única propiedad esencial de un grafo no dirigido, de esta
forma preservamos la estructura de los grafos.
Para los siguientes grafos la
función ƒ definida por:
ƒ(a) = w, ƒ(b) = x, ƒ(c) = y,
ƒ(d) = z
Da como resultado un isomorfismo.
De hecho, cualquier correspondencia uno a uno entre {a, b, c, d} y {w, x, y, z}
será un isomorfismo, ya que ambos grafos son completos. También esto será
cierto si cada uno de los grafos dados tiene solamente cuatro vértices
aislados.
Problemas
con grafos.
La teoría
de grafos, es una parte de las Matemáticas que comenzaron en clave de juego y
se han convertido en un instrumento fundamental de la Matemática Aplicada. Los
problemas de transporte, la combinatoria poliédrica, los problemas de
secuenciación de actividades usan de la Teoría de Grafos, para resolver muchos
de los problemas de estas áreas.
Decimos que un grafo es hamiltoniano si admite un recorrido hamiltoniano.
Un recorrido hamiltoniano es un camino cerrado, que pasa por cada uno de los
vértices del grafo, una sola vez. Ahora, por tanto, está permito recorrer
alguna arista más de una vez. Un grafo es conexo cuando es posible pasar de un
vértice cualquiera a otro vértice cualquiera, por arcos del grafo. No se conoce
ningún criterio que permita saber si un grafo conexo es o no hamiltoniano. Pero
algunos grafos sí que admiten demostraciones de que no son hamiltonianos.
¿Serías capaz de demostrar que este grafo no es hamiltoniano?
El siguiente grafo tiene un circuito hamiltoniano indicado por las líneas
más oscuras. Existe solamente otro circuito hamiltoniano
Arboles.
Los árboles representan las
estructuras no lineales y dinámicas de datos más importantes en computación.
Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución
de un programa. No lineales, puesto que a cada elemento del árbol pueden
seguirle varios elementos.
Los árboles pueden ser
construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos,
registros y conjuntos, mientras que las dinámicas están representadas por
listas. La definición de árbol es la siguiente: es una estructura jerárquica
aplicada sobre una colección de elementos u objetos llamados nodos; uno de los
cuales es conocido como raíz. Además se crea una relación o parentesco entre
los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor,
ancestro, etc.
Formalmente se define un árbol de
tipo T como una estructura homogénea que es la concatenación de un elemento de
tipo T junto con un número finito de árboles disjuntos, llamados subárboles.
Una forma particular de árbol puede ser la estructura vacía.
La figura
siguiente representa a un árbol general.
Se utiliza la recursión para
definir un árbol porque representa la forma más apropiada y porque además es
una característica inherente de los mismos.
La representación gráfica de un
árbol binario es la siguiente:
Los árboles tienen una gran variedad
de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas
matemáticas, para organizar adecuadamente la información, para construir un árbol
genealógico, en la toma de decisiones, para el análisis de circuitos eléctricos
y para numerar los capítulos y secciones de un libro.
A los árboles ordenados de grado
dos se les conocen como árboles binarios ya que cada nodo del árbol no tendrá
más de dos descendientes directos. Las aplicaciones de los árboles binarios son
muy variadas ya que se les puede utilizar para representar una estructura en la
cual es posible tomar decisiones con dos opciones en distintos puntos.
Propiedades de los árboles.
Las siguientes son las
características y propiedades más importantes de los árboles en general:
- Todo árbol que no es vacío, tiene un único nodo raíz.
- Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. en este caso es común utilizar la expresión X es hijo de Y.
- Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y en ese caso es común utilizar la expresión X es padre de Y.
- Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.
- Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
- Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
- Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.
- Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
- Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
A continuación se
presenta un ejemplo para clarificar estos conceptos.
Tipos de árboles.
En
ciencias de la computación, un árbol binario es una estructura de datos en la
cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden
tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo
tiene como referencia a null, es decir que no almacena ningún dato, entonces
este es llamado un nodo externo. En el caso contrario el hijo es llamado un
nodo interno. Usos comunes de los árboles binarios son los árboles binarios de
búsqueda, los montículos binarios y Codificación de Huffman.
Tipos de árboles binarios.
Un árbol binario es un árbol con raíz en el que
cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol
binario lleno en el que todas las hojas (vértices con cero hijos) están a la
misma profundidad (distancia desde la raíz, también llamada altura).
A
veces un árbol binario perfecto es denominado árbol binario completo. Otros
definen un árbol binario completo como un árbol binario lleno en el que todas
las hojas están a profundidad n o n-1, para alguna n.
Árbol binario de búsqueda auto-balanceable.
En
ciencias de la computación, un árbol binario de búsqueda auto-balanceable o
equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o
el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en
todo momento, automáticamente. Esto es importante, ya que muchas operaciones en
un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del
árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy
grandes en situaciones normales, como cuando las claves son insertadas en
orden. Mantener baja la altura se consigue habitualmente realizando
transformaciones en el árbol, como la rotación de árboles, en momentos clave.
Tiempos
para varias operaciones en términos del número de nodos en el árbol n:
Operación
Tiempo en cota superior asintótica
Búsqueda
O(log n)
Inserción
O(log n)
Eliminación
O(log n)
Iteración
en orden O(n)
Para
algunas implementaciones estos tiempos son el peor caso, mientras que para
otras están amortizados.
Estructuras
de datos populares que implementan este tipo de árbol:
Árbol
AVL
Árbol
rojo-negro
Árbol-B
En
las ciencias de la computación, los árboles-B o B-árboles son estructuras de
datos de árbol que se encuentran comúnmente en las implementaciones de bases de
datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las
inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un
árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un
árbol que satisface las siguientes propiedades:
1. Cada nodo tiene como máximo M hijos.
2.
Cada nodo (excepto raíz y
hojas) tiene como mínimo M/2 hijos.
3.
La raíz tiene al menos 2 hijos
si no es un nodo hoja.
4.
Todos los nodos hoja aparecen
al mismo nivel.
5. Un nodo no hoja con k hijos contiene k-1 elementos
almacenados.
Los
hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas
condiciones:
1. El primero tiene valor menor que r1.
2.
El segundo tiene valor mayor
que r1 y menor que r2, etc.
3. El último hijo tiene valor mayor que rm.
Árbol multicamino.
Los
árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol
usadas en computación.
Un
árbol multicamino posee un grado g mayor a dos, donde cada nodo de información
del árbol tiene un máximo de g hijos.
Sea
un árbol de m-caminos A, es un árbol m-caminos si y solo si:
A está vacío.
A está vacío.
Cada
nodo de A muestra la siguiente estructura:
[nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]nClaves
es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves
<= g-1 Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <=
i <= nClaves Clavei, son los valores de clave, pudiendo ser: 1 <= i <=
nClaves Clavei < g =" (V,A,j" g1 =" (V1," v1 ="
{1," a1 =" {(1," g2 =" (V2," v2 =" {1," a2
=" {(1," g3 =" (V3," v3 =" {1," a3 ="
{">, <2,>, <2,> }
Bosques.
Un bosque es un conjunto de
árboles o de otra manera podemos decir que un bosque es un grafo acíclico, de
dice que el grafo es acíclico si no se tiene ningún ciclo simple.
La figura muestra un bosque, el
cual está compuesto por tres árboles.
Un componente conexo es cada
árbol que conforma al bosque.
Sea G un grafo un árbol abarcador
de G es un grafo conexo que tienen los mismos vértices que G y no tiene ciclos.
Arboles generadores.
Un árbol T es un árbol generador
de un grafo G si T es un subgrafo de G que contiene todos los vértices de
G.
A esta característica general es
posible agregar ciertos teoremas de modo de detallar aún más el alcance de la
definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo
contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá
varios árboles generadores, como el del ejemplo 1 el cual tiene a lo menos dos
árboles generadores T1 yT2.
Algoritmos para hallar un árbol
generador, que se base en el teorema de que el grafo G debe ser conexo, pueden
ser los que se realizan a través de los métodos llamados buscar primero a lo
ancho, buscar primero a lo largo y el de regreso al nivel anterior.
Arboles Generadores Mínimales.
Un Árbol Generador Minimal es el
que resulta de la construcción en primer lugar de un Árbol generador, pero con
la característica de ser el de menos peso del grafo al cual genera.
Por ejemplo sea un
grafo ponderado (con peso) con cinco vértices. La idea es construir un subgrafo
que una a todos los puntos pero con el mínimo de peso (el peso se refiere al
valor que se le da a cada uno de los lados de un grafo). Este subgrafo debe
ser un árbol generador, ya que debe unir todos los vértices, debe ser conexo y
debe haber un único camino entre cada par de vértices, por lo tanto, lo que se
necesita es un árbol generador con el mínimo de peso, es a esto lo que se llama
árbol generador mínima.
Sea G un grafo con
peso. Un árbol generador mínima de G es un árbol generador de G con peso
mínimo.
Búsqueda.
Es un árbol binario T en el cual
se asocian ciertos datos con los vértices. Los datos están ordenados de modo
que, para cada vértice v en T, cada elemento de dato en el subárbol izquierdo
de v sea menor que el elemento de dato en v y cada elemento de dato en el
subárbol derecho de v es mayor que el elemento de dato en v.
Los arboles de búsqueda binaria
son útiles para localizar datos. Es decir, dado un elemento D, podemos
determinar con facilidad si D está en un árbol de búsqueda binaria y, de estar
presente, conocer su posición. Para determinar si un elemento de dato D está en
un árbol de búsqueda binaria, comenzaríamos en la raíz. Luego compararíamos de
manera sucesiva D con el elemento de dato del vértice en cuestión. Si D es
igual al elemento de dato del vértice en cuestión, hemos encontrado a D, por lo
cual habremos concluido. Si D es menor que el elemento de dato en el vértice en
cuestión v, nos movemos al hijo izquierdo de v y repetimos el proceso. Si D es
mayor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo
derecho de v y repetimos el proceso. Si en algún momento no existe un hijo al
cual moverse, podemos concluir que D no está en el árbol.
Recorridos de árboles y notaciones polacas de
expresiones.
El recorrido de árboles se
refiere al proceso de visitar de una manera sistemática, exactamente una vez,
cada nodo en una estructura de datos de árbol (examinando y/o actualizando los
datos en los nodos). Tales recorridos están clasificados por el orden en el
cual son visitados los nodos. Los siguientes algoritmos son descritos para un
árbol binario, pero también pueden ser generalizados a otros árboles.
La notación polaca, también
conocida como notación de prefijo o notación prefija, es una forma de notación
para la lógica, la aritmética y el álgebra. Su característica distintiva es que
coloca los operadores a la izquierda de sus operando. Si la aridad de los
operadores es fija, el resultado es una sintaxis que carece de paréntesis u
otros signos de agrupación, y todavía puede ser analizada sin ambigüedad. El
lógico polaco Jon Łukasiewicz inventó esta notación alrededor de 1920 para
simplificar la lógica proposicional.
Aplicaciones.
La lógica computacional es la
misma lógica matemática aplicada al contexto de las ciencias de la computación.
Su uso es fundamental a varios niveles: en los circuitos computacionales, en la
programación lógica y en el análisis y optimización (de recursos temporales y
espaciales) de algoritmos.
Circuitos computacionales.
El nivel menos abstracto dentro
de una computadora está constituido por circuitos electrónicos que responden a
diferentes señales eléctricas, siguiendo los patrones de la lógica booleana;
esto es, compuertas lógicas que devuelven un valor dependiendo de las entradas
que se le dan al sistema. Existen ocho compuertas lógicas básicas con las
cuales se pueden formar sistemas muy complejos: AND, OR, Inverter, Buffer,
NAND, NOR, XOR y XNOR.
Algoritmos.
En matemáticas, ciencias de la
computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit
algorithmus y éste a su vez del matemático persa Al Juarismi ) es un conjunto
preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que
permite realizar una actividad mediante pasos sucesivos que no generen dudas a
quien deba realizar dicha actividad.
No hay comentarios.:
Publicar un comentario