Árboles y grafos

TEORÍA DE GRAFOS Y ARBOLES

¿Qué es un grafo?

Un grafo G consiste en un conjunto no vacío de vértices o nodos V y un conjunto de arcos o aristas E  G = (V,E). Grafo del griego grafos: dibujo e imagen.

Teoría de grafos 

Los grafos son estructuras discretas que aparecen ubicua mente en cada disciplina donde se requiere modelar algo, en general los grafos son mapas conceptuales que ayudan a representar el conocimiento.  Los grafos tiene muchas aplicaciones en problemas de ingeniería, computación, biología, física, urbanismo, comunicaciones, economía, redes sociales, entre muchas otras.

Aplicación de los grafos 

Aplicaciones de los grafos:  Internet y los protocolos de comunicaciones (TCP/IP, SMTP, FTP, routers, etc.)

 Diseño de redes de comunicaciones y transporte (redes computacionales, carreteras, aguas, electricidad, telecomunicaciones, aviación, satélites, aero-espacial, flotas de vehículos, etc.) 

Estructura de datos algoritmos computacionales navegador GPS (Google Maps.) Economía (bolsa, transacciones económicas, modelos de mercado, etc.)

Redes sociales (Facebook, Skype, MSN) Política y marketing, seguridad y prevención del terrorismo, inteligencia militar

propiedades 

Adyacencia: Dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.

Incidencia: Una arista es incidente a un vértice si ésta lo une a otro.

Ponderación: Corresponde a una función que asocia a cada arista un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo.

Etiquetado: Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto. 

Ejemplos

Arboles 

En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos amplia mente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados.

Aplicación de los arboles 

La estructura de árbol, independientemente de si se trata de árboles binarios, AVL o B, se usa principalmente para guardar la información organizada de tal manera que sea posible tener un rápido acceso a ella. La diferencia principal que permite decidir qué tipo de árbol usar depende de la forma en que está estructurada la información, pero sobre todo del volumen de la misma ya que cuando es posible manipular la información en memoria principal, los árboles binarios y AVL son recomendables.

propiedades de los arboles 

Todo árbol es a su vez un grafo con un conjunto numerable de vértices es un grafo plano. 

Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

Ejemplos:

Compuerta lógicas

¿Que es una compuerta lógica? 

Una compuerta lógica es un dispositivo electrónica que en función de los valores de entrada otorga un resultado o una salida determinada, son la base de la electrónica digital.

Ejemplos de algunas compuertas lógicas:

COMPUERTA NOT: 

Todo lo que ingresa por la entrada, a la salida entrega lo opuesto, si ingresa un estado alto 1 a la salida se vera un estado bajo 0 por ejemplo, tiene una sola entrada.

COMPUERTA AND

Para que una compuerta AND entregue un uno a la salida, todas las entradas deben tambien estar en uno, basta con que alguna con lo este para que en la salida se vea un cero, “Si condición uno Y condición dos Y condición tres se cumplen, entonces la salida sera verdadera.” En términos simbólicos a la operación se la conoce con el símbolo “.” o “ˆ“.

COMPUERTA OR

Esta compuerta es diferente a la AND, basta con que una de las entradas este en estado alto para que automáticamente la salida pase a estar en estado alto, “Si condición uno O condición dos O condición tres entonces la salida sera verdadera”. En términos simbólicos a la operación se la conoce con el símbolo +.

COMPUERTA NAND

Para la compuerta NAND, cuando las dos entradas estén en estado alto la salida estará en estado bajo. Como resultado de la negación de una AND.

XOR

La compuerta XOR Su salida estará en estado bajo cuando las dos entradas se encuentren en estado bajo o alto. Al mismo tiempo podemos observar que entradas iguales es cero y diferentes es uno.

https://hetpro-store.com/TUTORIALES/compuertas-logicas/