Matemáticas Discretas: noviembre 2019

Grafos

El origen de la palabra grafo es griego y su significado etimológico es "trazar". aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos 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 las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad, (ver la figura 1). En cada caso es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (nodos o vértices) con líneas conectándolos (arcos).

De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir,un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices. Por otro lado, debido a su generalidad y a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo.

Para facilitar el estudio de este tipo de dato, a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación, considerando que dicha teoría es compleja y amplia,aquí sólo se realizará una introducción a la misma, describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica, u estudio podría dividirse en dos grandes bloques; grafos dirigidos y grafos no dirigidos (pueden ser considerados un caso particular de los anteriores).

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido, por el contrario, la red de carreteras de un país representa en general un grafo no dirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos. No obstante, podemos dar unas definiciones generales para ambos tipos.

A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados.

Notación y conceptos

Un grafo G es un conjunto en el que hay definida una relación binaria,es decir, G=(V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y

A Í V x V es una relación binaria a cuyos elementos denominaremos arcos o aristas.

Dados x, y Î V, puede ocurrir que:

Ø (x, y) Î A, en cuyo caso diremos que x e y están unidos mediante un arco y,

Ø (x, y) Ï A, en cuyo caso diremos que no lo están.

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

Veamos algunos conceptos sobre grafos:

· Diremos que un grafo es completo si A=VxV,o sea,si para cualquier pareja de vértices existe una arista que los une(en ambos sentidos si el grafo es no dirigido).El número de aristas será:

Para grafos dirigidos:

Para grafos no dirigidos:

donde n=|V| .

· Un grafo dirigido es simétrico si para toda arista (x, y) Î A también aparece la arista (y, x) Î A y es antisimétrico si dada una arista (x, y) Î A implica que (y, x) Ï A.

· Tanto a las aristas como a los vértices les puede ser asociada información, a esta información se le llama etiqueta, si la etiqueta que se asocia es un número se le llama peso,costo o longitud, un grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o ponderado.

· El número de elementos de V se denomina orden del grafo, un grafo nulo es un grafo de orden cero.

· Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya de x a y ((x, y) Î A),a x se le denomina origen del arco y a y extremo del mismo, de igual forma se dirá que y es adyacente a x, en el caso de que el grafo sea no dirigido si x es adyacente (resp. incidente) a y entonces y también es adyacente (resp. incidente) a x.

· Se dice que dos arcos son adyacentes cuando tienen un vértice común que es a la vez origen de uno y extremo del otro.

· Se denomina camino (algunos autores lo llaman cadena si se trata de un grafo no dirigido)en un grafo dirigido a una sucesión de arcos adyacentes:
C={(v₁,v₂),(v₂,v₃),...,(v_n-1,v_n), v_i Î V}.

· La longitud del camino es el número de arcos que comprende y en el caso en el que el grafo sea ponderado se calculará como la suma de los pesos de las aristas que lo constituyen.

· Un camino se dice simple cuando todos sus arcos son distintos y se dice elemental cuando no utiliza un mismo vértice dos veces.Por tanto todo camino elemental es simple y el recíproco no es cierto.

· Un camino se dice Euleriano si es simple y además contiene a todos los arcos del grafo.

· Un circuito (o ciclo para grafos no dirigidos) es un camino en el que coinciden los vértices inicial y final, un circuito se dice simple cuando todos los arcos que lo forman son distintos y se dice elemental cuando todos los vértices por los que pasa son distintos. La longitud de un circuito es el número de arcos que lo componen. Un bucle es un circuito de longitud 1 (están permitidos los arcos de la forma (i,i) y notemos que un grafo antisimétrico carecería de ellos).

· Un circuito elemental que incluye a todos los vértices de un grafo lo llamaremos circuito Hamiltoniano.

· Un grafo se denomina simple si no tiene bucles y no existe más que un camino para unir dos nodos.

· Diremos que un grafo no dirigido es bipartido si el conjunto de sus vértices puede ser dividido en dos subconjuntos (disjuntos) de tal forma que cualquiera de las aristas que componen el grafo tiene cada uno de sus extremos en un subconjunto distinto, un grafo no dirigido será bipartido si y sólo si no contiene ciclos con un número de aristas par.

· Dado un grafo G=(V,A),diremos que G^'=(V,A^') con A^' Ì A es un grafo parcial de G y un subgrafo de G es todo grafo G^'=(V^',A^') con V^' Í V y A^' Í A 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 .

· Se denomina grado de entrada de un vértice x al número de arcos incidentes en él, se denota d_e(x).

· Se denomina grado de salida de un vértice x al número de arcos adyacentes a él, se denota d_s(x).

· Para grafos no dirigidos tanto el grado de entrada como el de salida coinciden y hablamos entonces de grado y lo notamos por d (x).

· A todo grafo no dirigido se puede asociar un grafo denominado dual construido de la siguiente forma:

G (V, A) ------> G^' (V^', A^')

donde A' está construido de la siguiente forma: si e₁,e₂ Î a A son adyacentes --> (e₁,e₂) Î a A' con e₁,e₂ Î a V', en definitiva, para construir un grafo dual se cambian vértices por aristas y viceversa.

· Dado un grafo G, diremos que dos vértices están conectados si entre ambos existe un camino que los une.

· Llamaremos componente conexa a un conjunto de vértices de un grafo tal que entre cada par de vértices hay al menos un camino y si se añade algún otro vértice esta condición deja de verificarse. Matemáticamente se puede ver como que la conexión es una relación de equivalencia que descompone a V en clases de equivalencia,cada uno de los subgrafos a los que da lugar cada una de esas clases de equivalencia constituiría una componente conexa. Un grafo diremos que es conexo si sólo existe una componente conexa que coincide con todo el grafo.

( IMÁGENES )

( VÍDEOS )

foto

Capturas de pantalla

1 programa

2 programa

Las Compuertas Lógicas son circuitos electrónicos conformados internamente por transistores que se encuentran con arreglos especiales con los que otorgan señales de voltaje como resultado o una salida de forma booleana, están obtenidos por operaciones lógicas binarias (suma, multiplicación). También niegan, afirman, incluyen o excluyen según sus propiedades lógicas. Estas compuertas se pueden aplicar en otras áreas de la ciencia como mecánica, hidráulica o neumática.

Existen diferentes tipos de compuertas y algunas de estas son más complejas, con la posibilidad de ser simuladas por compuertas más sencillas. Todas estas tienen tablas de verdad que explican los comportamientos en los resultados que otorga, dependiendo del valor booleano que tenga en cada una de sus entradas.

Fig. 1 Compuertas Lógicas

Trabajan en dos estado, “1” o “0”, los cuales pueden asignarse a la lógica positiva o lógica negativa. El estado 1 tiene un valor de 5v como máximo y el estado 0 tiene un valor de 0v como mínimo y existiendo un umbral entre estos dos estados donde el resultado puede variar sin saber con exactitud la salida que nos entregara. Las lógicas se explican a continuación:

La lógica positiva es aquella que con una señal en alto se acciona, representando un 1 binario y con una señal en bajo se desactiva. representado un 0 binario.
La lógica negativa proporciona los resultados inversamente, una señal en alto se representa con un 0 binario y una señal en bajo se representa con un 1 binario.

A continuación vamos a analizar las diferentes operaciones lógicas una por una comenzando por la más simple:

Compuerta AND

Esta compuerta es representada por una multiplicación en el Algebra de Boole. Indica que es necesario que en todas sus entradas se tenga un estado binario 1 para que la salida otorgue un 1 binario. En caso contrario de que falte alguna de sus entradas con este estado o no tenga si quiera una accionada, la salida no podrá cambiar de estado y permanecerá en 0. Esta puede ser simbolizada por dos o más interruptores en serie de los cuales todos deben estar activos para que esta permita el flujo de la corriente.

Fig. 2 Tabla, Representación y Fórmula Compuerta AND.

Compuerta OR

En el Algebra de Boole esta es una suma. Esta compuerta permite que con cualquiera de sus entradas que este en estado binario 1, su salida pasara a un estado 1 también. No es necesario que todas sus entradas estén accionadas para conseguir un estado 1 a la salida pero tampoco causa algún inconveniente. Para lograr un estado 0 a la salida, todas sus entradas deben estar en el mismo valor de 0. Se puede interpretar como dos interruptores en paralelo, que sin importar cual se accione, será posible el paso de la corriente.

Fig. 3 Tabla, Representación y Fórmula Compuerta OR.

Compuerta NOT

En este caso esta compuerta solo tiene una entrada y una salida y esta actúa como un inversor. Para esta situación en la entrada se colocara un 1 y en la salida otorgara un 0 y en el caso contrario esta recibirá un 0 y mostrara un 1. Por lo cual todo lo que llegue a su entrada, será inverso en su salida.

Fig. 4 Tabla, Representación y Fórmula Compuerta NOT.

Compuerta NAND

También denominada como AND negada, esta compuerta trabaja al contrario de una AND ya que al no tener entradas en 1 o solamente alguna de ellas, esta concede un 1 en su salida, pero si esta tiene todas sus entradas en 1 la salida se presenta con un 0.

Fig. 5 Tabla, Representación y Fórmula Compuerta NAND.

Compuerta NOR

Así como vimos anteriormente, la compuerta OR también tiene su versión inversa. Esta compuerta cuando tiene sus entradas en estado 0 su salida estará en 1, pero si alguna de sus entradas pasa a un estado 1 sin importar en qué posición, su salida será un estado 0.

Fig. 6 Tabla, Representación y Fórmula Compuerta NOR.

Compuerta XOR

También llamada OR exclusiva, esta actúa como una suma binaria de un digito cada uno y el resultado de la suma seria la salida. Otra manera de verlo es que con valores de entrada igual el estado de salida es 0 y con valores de entrada diferente, la salida será 1.

Fig. 7 Tabla, Representación y Fórmula Compuerta XOR.

Compuerta XNOR

Esta es todo lo contrario a la compuerta XOR, ya que cuando las entradas sean iguales se presentara una salida en estado 1 y si son diferentes la salida será un estado 0.

Fig. 8 Tabla, Representación y Fórmula Compuerta XNOR.

Compuerta IF

Esta compuerta no es una muy utilizada o reconocida ya que su funcionamiento en estados lógicos es parecido a si solo hubiera un cable conectado porque exactamente lo que se le coloque en la entrada, se encontrara en la salida. Pero también es conocido como un buffer, en la práctica se utiliza como amplificador de corriente o como seguidor de tensión para adaptar impedancias.