GRAFOS DIRIGIDOS

-

 Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un sentido definido,​ a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.



Representaciones de Grafos dirigidos

Pueden usarse varias estructuras de datos para representar un digrafo, dependiendo su selección de las operaciones que se aplicarán a los vértices y arcos del digrafo. Una representación común para un digrafo G={V,E} es la matriz de adyacencia. Suponiendo V={1,2,…,n}, la matriz de adyacencia de G es una matriz A de nxn de valores binarios donde A[i][j] es 1 si y sólo si hay un arco del vértice i a j, y 0 si no lo hay. Otra representación reñacionada es la matriz de adyacencia estiquetada donde A[i][j] es la etiqueta del arco que va de i a j. Si tal arco no existe puede usarse una etiqueta especial para ese caso.

Ejemplo: A continuación se muestra un digrafo y su correspondiente matriz de adyacencia


Más información
Más información


Comentarios

Publicar un comentario

Entradas más populares de este blog

COMPUERTAS LOGICAS

-
Imagen
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. Puerta AND Para la compuerta AND, La salida estará en estado alto de tal manera que solo si las dos entradas se encuentran en estado alto. Por esta razón podemos considerar que es una multiplicación binaria. Puerta OR la compuerta OR, la salida estará en estado alto cuando cualquier entrada o ambas estén en estado alto. De tal manera que sea una suma lógica. Puerta NOT En la compuerta NOT, el estado de la salida es inversa a la entrada. Evidentemente, una negación. Puerta NAND Para la compuerta NAND, cuand
Leer más

MAPAS DE KARNAUGH

-
Imagen
Un mapa de Karnaugh (también conocido como tabla de Karnaugh o diagrama de Veitch,es un diagrama utilizado para la simplificación de funciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1953 por Maurice Karnaugh, un físico y matemático de los laboratorios Bell. Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del  cerebro humano  para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones muy inmensas. El mapa de Karnaugh consiste en una representación bidimensional de la  tabla de verdad  de la función a simplificar. Puesto que la tabla de verdad de una función de N variables posee 2 N  filas, el mapa K correspondiente debe poseer también 2 N  cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el  código Gray , de manera que sólo una de las variables varía entre celdas ady
Leer más