Introducción

INTRODUCCIÓN

Esta página Web tiene como intención principal aportar a las nuevas generaciones de ingeniería de sistemas material didáctico para mejorar el conocimiento y manejo  de las estructuras de datos 2, por supuesto  va dirigido  a los programadores o personas que estén interesadas en  estudiar esta área. El blog contiene materiales como: texto, imágenes y videos que permitirán  mejorar o entender los diferentes conceptos relacionados con las estructuras de datos 2, los  cuales se expondrán en este blog para beneficio nuestro y de todos ustedes, se da a conocer que este sitio no está hecho como ánimo de lucro sino con fines educativos solo para adquirir conocimientos.  

Objetivos:

• Exponer los diferentes temas relacionados con las estructuras de datos 2.
• Representar gráficamente los árboles y grafos de las estructuras de datos 2 los cuales tendrán  su respectiva explicación
• Dar a conocer al lector la importancia del estudio de las estructuras de datos 2.
• Incluir material didáctico que le permita al lector conocer  y aprender los conceptos asociados a la estructura de datos 2.
• Integrar conceptos de fácil manejo para el lector, los cuales le permitan entender  esta área de conocimiento que son las estructura de datos 2.

CODIGO QR

Observaciones

-  Esta pagina esta conectada con google +, ya que cuesta con ayuda de este grandioso buscador de google

- La pagina contiene un QR para todos aquellos que no tengan un computador, con la aplicacion de appstore T.QR podra ver nuestra pagina tomandole una foto a nuestro simbolo qr

- Es resposiva (que se puede acoplar a un celular, tablet  y computadores)

Tipos De Grafos

Tipos De Grafos

Grafos dirigidos

Los grafos dirigidos son grafos en los que las aristas tienen una dirección definida; por ejemplo, se puede dar el caso de poder ir del nodo A al nodo B, pero no al revés. En la mayoría de los casos la dirección de las aristas indica algún tipo de relación de precedencia entre los nodos. Los grafos dirigidos pueden ser usados para:

• Modelar líneas de fabricación, en las que diferentes procesos dependen de otros

• Manejar dependencias en la compilación de archivos, como hace el make

Podemos ver claramente que por ejemplo, existe una arista de A a G, pero no de G a A. Sin embargo, está permitido que halla dos aristas de direcciones distintas entre los mismos nodos, como por ejemplo entre H e I, y entre L y M.

Búsqueda primero en profundidad

En el caso de grafos dirigidos, la búsqueda primero en profundidad es casi igual a la similar en el caso de grafos no dirigidos.

Grafos regulares

Los grafos son esquemas matemáticos, formados por una serie de puntos llamados vértices o nudos y unos segmentos que los unen llamados aristas.

En esta página haremos el estudio matemático de las posiciones de un rompecabezas, representaremos todas esas posiciones en forma de grafo, ello nos llevará a descubrir un concepto matemático nuevo, se trata de los grafos regulares, de cuyos vértices salen tres aristas.

Grafo Bipartido

Dícese de todo grafo simple sin lazos cuyo conjunto de vértices puede dividirse en dos subconjuntos disjuntos no vacíos de manera que los vértices que los componen solo tengan aristas o arcos con vértices del otro subconjunto, nunca con ningún vértice del mismo conjunto.

Definición.

Un grafo G=<V,A> se dice bipartido o bipartito si y solo si existe una partición de V=V1 U V2 tal que para toda arista (x,y) de A se cumple que x es un vertice de V1 e y está en V2 o simplemente que A será un subconjunto no nulo de V1xV2.

Cuando A=V1xV2 se dice que el grafo es bipartido completo.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices de V de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos o cardinalidad, decimos que el grafo bipartito G es balanceado.

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Matriz de adyacencia

Matriz de adyacencia

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de  n filas \times n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a_{ij} vale {{1}} cuando haya una arista que una los vértices i y j. En caso contrario el elemento a_{ij} vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Ejemplo : Este video no tiene lucro para esta pagina

Matriz de adyacencia. Matriz cuadrada de orden NxN asociada a un grafo de orden N, donde sus filas y columnas se identifican con los vértices del grafo y en las celdas se indican la cantidad de aristas (o arcos salientes si es un dígrafo) a los nodos asignado a la fila y columnas en cuestión.

Contenido

 [ocultar] 

1 Definición.

2 Ejemplo.

3 Véase también

4 Fuentes.

Definición.

Sea el grafo G=<V,A> de orden N al mismo se asocia una matriz cuadrada M de NxN tal que:

A cada fila se asocia un nodo de V.

A cada columna se asocia un nodo de V.

La celda Mi,j contiene la cantidad de aristas de A de la forma {i,j} ó (i, j).

Ejemplo.

Dada la relación:

G=<{0, 1, 2, 3, 4, 5, 6, 7, 8}, ((0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 6), (3, 7), (8, 3), (4, 6), (4, 7), (8, 4), (5, 6), (5, 7), (8, 5))>.

la matriz de adyacencia asociada al grafo sería:

N 0 1 2 3 4 5 6 7 8

0 0 0 0 1 1 1 0 0 0

1 0 0 0 1 1 1 0 0 0

2 0 0 0 1 1 1 0 0 0

3 1 1 1 0 0 0 1 1 1

4 1 1 1 0 0 0 1 1 1

5 1 1 1 0 0 0 1 1 1

6 0 0 0 1 1 1 0 0 0

7 0 0 0 1 1 1 0 0 0

para mayor información sigume en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Aplicaciones De Grafos

Aplicaciones  De Grafos

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.

Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.

Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos).

Se usa para la solución de problemas de genética y problemas de automatización de la proyección (SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información. Acude en las investigaciones nucleares (técnica de diagramas de Feynman).5

Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las aristas (o "edges" en inglés) representa los senderos de los animales o las migraciones. Con esta información, los científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.

El problema de los de cuatro colores (Appel y Haken 1976)Conjetura (Francis Guthrie, 1852): Todo mapa trazado sobre una hoja depapel puede colorearse usando solamente cuatro tintas de manera quelos paises" con  frontera com un" tengan coores diferentes.

- Circuito
(Redirigido desde «Circuito eléctrico»)
Para otros usos de este término, véase Circuito (desambiguación).
Un circuito es una red eléctrica (interconexión de dos o más componentes, tales como resistencias, inductores, condensadores, fuentes, interruptores y semiconductores) que contiene al menos una trayectoria cerrada. Los circuitos que contienen solo fuentes, componentes lineales (resistores, condensadores, inductores) y elementos de distribución lineales (líneas de transmisión o cables) que pueden analizarse por métodos algebraicos para determinar su comportamiento en corriente directa o en corriente alterna. Un circuito que tiene componentes electrónicos es denominado un circuito electrónico. Estas redes son generalmente no lineales y requieren diseños y herramientas de análisis mucho más complejos.

- Isomería
(Redirigido desde «Isomero»)
La isomería es una propiedad de aquellos compuestos químicos que, con igual fórmula molecular (fórmula química no desarrollada) de iguales proporciones relativas de los átomos que conforman su molécula, presentan estructuras químicas distintas, y por ende, diferentes propiedades. Dichos compuestos reciben la denominación de isómeros. Por ejemplo, el alcohol etílico o etanol y el éter dimetílico son isómeros cuya fórmula molecular es C2H6O.


Clasificación de los isómeros en Química orgánica.
Aunque este fenómeno es muy frecuente en Química orgánica, no es exclusiva de ésta pues también la presentan algunos compuestos inorgánicos, como los compuestos de los metales de transición

Ejemplo : Este vídeo no tiene fines de lucro 

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

MATRICES DISPERSA

Matrices Dispersas

En álgebra lineal numérica una matriz dispersa o matriz rala o matriz hueca es una matriz de gran tamaño en la que la mayor parte de sus elementos son cero.1
Con matrices de gran tamaño los métodos tradicionales para almacenar la matriz en la memoria de una computadora o para la resolución de sistemas de ecuaciones lineales necesitan una gran cantidad de memoria y de tiempo de proceso. Se han diseñado algoritmos específicos para estos fines cuando las matrices son dispersas.

Matrices dispersas

forma de representación

 Formato CRS

 Un vector de punto flotante de tamaño k en el que se almacenan los valores de los coeficientes.

 Otro vector de tamaño k en el que se almacenan los números de columna de los elementos distintos de cero.

 Un vector de tamaño n+1 siendo n la cantidad de filas de la matriz, en el cual se almacena la posición de la primera ocurrencia de cada fila Las matrices dispersas son ampliamente usadas en la computación científica, especialmente en la optimización a gran escala, análisis estructural y de circuitos, dinámica de fluidos computacionales y en general en solución numérica de ecuaciones diferenciales parciales; otras áreas de interés en donde se pueden aplicar la representación dispersa son la teoría de grafos, teoría de redes, la combinatoria, los métodos numéricos, entre otros. 

Ejemplo : Este video no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Algoritmo Enearios

Árboles Enearios

Al igual que en los TDAs estudiados con anterioridad, la forma de implementar un árbol n-ario dependerá del problema a resolver y de la capacidad del diseñador.

No obstante, existen 3 Implementaciones básicas:

- Implementación matricial. El árbol se representa en un vector de enteros, donde cada componente contiene el índice de su nodo padre.
- Implementación con listas. Se representa mediante un vector de listas. Cada índice de las componentes del vector se asocia con un nodo del árbol, y cada componente es una lista con los Hijos del nodo.
- Implementación con celdas enlazadas. Cada nodo del árbol es una celda enlazada con un puntero a su padre, a su hijo izquierda y a su hermano derecha.
- El tipo Nodo del árbol es entero.
- La relación padre-hijo se representa en un vector P, donde P[i] indica cuál es el nodo padre de i. Si el nodo no tiene padre (es la raíz), P[i] tomará valor -1.
- Las etiquetas de los nodos se representan en otro vector de etiquetas.

Esta implementación es relativamente sencilla y con bajo coste de memoria. Facilita las operaciones de acceso a los ancestros de un nodo (eficiencia O(log(n)) para viajar desde un nodo hoja hasta la raíz), pero resulta difícil gestionar operaciones con los hijos (conocer la altura, determinar los hijos, establecer hijo izquierda y hermano derecha...)
árbol eneario

árbol enario en piramide

Un Arbol se denomina Piramide si el valor del nodo padre es igual a la suma de los valores de los nodos hijos. Excepto para las hojas

Ejemplo: Este video no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion

Algoritmo kruskal

Algoritmo kruskal

árbol de coste total mínimo/máximo

Joseph B. KruskalJoseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.

La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.

La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros)

Árbol de Expansión

Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las 

Ejemplo: Este video no tiene lucro para esta pagina

Para mayor información sigueme en:

CIBERGRAFIA

- haz click aqui para ver de donde se saco la informacion