Trabajo Final Estructura de Datos Unicartagena

[pic 1][pic 2]

TRABAJO CONTEXTUALIZADO

ESTRUCTURA DE DATOS

DOCENTE:

BIVIAN ROBLES ACOSTA

ESTUDIANTES

MARIA ISABEL BLANCO

YULIANIS LEONOR HIGUERA GARCIA

UNIVERSIDAD DE CARTAGENA

INGENIERIA DE SOFWARE

MAGANGUE

2021

INTRODUCCION

La Teoria de grafos es un tema muy antiguo; sin embargo, es utilizado en muchas aplicaciones modernas. Sus ideas básicas fueron introducidas en el siglo XVIII por el matemático suizo Leonhard Euler.

Los grafos son usados para resolver problemas en muchos campos, por ejemplo, se puede utilizar para diferenciar dos compuestos químicos con la misma fórmula molecular, pero empleando distintas estructuras; para el caso de nuestra área de interés, un ejemplo es que los grafos pueden ser utilizados para establecer si dos computadoras están conectadas por un enlace de comunicaciones entre las de redes de computadoras.

Un grafo es un conjunto de objetos llamados vértices (o nodos) y una selección de segmentos que unen pares de vértices, llamados aristas que pueden ser dirigidos o no dirigidos. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Los grafos son unas representaciones gráficas de problemas que se plantean en la vida real y que con una serie de fórmulas y algoritmos que nos llevan a encontrar soluciones óptimas Más rápidamente.

Los grafos son estructuras discretas ordenadas donde son conjuntos de vértices o nodos conectados por arcos. Existen diferentes tipos de grafos que difieren respecto al número y tipo de arcos que pueden enlazar un par de vértices. En las diferentes áreas de estudio existen algunas dificultades que pueden ser solucionadas utilizando los modelos de grafos. 

Los grafos con pesos asignados a sus arcos pueden emplearse para solucionar problemas, por ejemplo, hallar el camino más corto entre dos puntos en una red de transporte, o bien para programar exámenes y asignar canales a las estaciones de televisión.

OBJETIVOS

OBJETIVO GENERAL

• Definir, organizar e implementar y utilizar adecuadamente las estructuras de datos más conocidas para la solución de problemas computacionales.

OBJETIVOS ESPECIFICOS

• Aprender las diferentes clases de grafos y sus funciones

• Ver cómo se pueden usar los grafos para resolver una amplia variedad de problemas.

DESCRIPCIÓN DEL PROBLEMA

En el siguiente trabajo se busca que el estudiante en compañía de los integrantes de esta cipa, así como los compañeros del aula sepan resolver un problema de estructura de datos ya sea un ejercicio de grafos en java o una problemática social en la vida cotidiana y más en la carrera de un ingeniero de software profesional a la hora de enfrentar un problema el problema que se busca es el resolver problemáticas que ayuden al ser humano a mejorar en el ámbito de estructura de datos y en otras áreas del conocimiento y del saber.

Marco conceptual

Se considera que el trabajo cooperativo de los estudiantes puede conducir a obtener mejores soluciones que las que se obtienen en los trabajos individuales. Cuando los estudiantes están tratando de aprender, se benefician de compartir sus ideas, especialmente cuando tienen diferentes puntos de vista. Sin embargo, introducir una dimensión social en una situación de aprendizaje contribuye a un incremento en la complejidad de la situación, ya que se introduce un problema adicional al puramente matemático. La importancia de la interacción entre alumnos para el aprendizaje y desarrollo de programas ha sido subrayada recientemente, lo que ha hecho necesario caracterizar la resolución de problemas como actividad de grafos en java y los procesos de razonamiento desencadenados en situaciones de interacción cuando se resuelven problemas. Así, para identificar las características de la actividad de programar generada por estudiantes universitarios al resolver y plantear problemas de probabilidad, consideramos referencias cuya complementariedad aporta información sobre cómo interpretar las conductas de los estudiantes. Para analizar la actividad durante la resolución de problemas y la caracterización de razonamiento problemático y superficial.

GRAFOS Y DÍGRAFOS FUERTEMENTE CONECTADOS

un grafo es un conjunto de nodos unidos por un conjunto de arcos. Un ejemplo de grafo que podemos encontrar en la vida real es el de un plano de trenes. El plano de trenes está compuesto por varias estaciones (nodos) y los recorridos entre las estaciones (arcos) constituyen las líneas del trazado.

 Un grafo G= (V, E) consiste en un conjunto V de nodos (vértices) y un conjunto E de aristas (arcos). Cada arista es un par (v, w), siendo v y w un par de nodos pertenecientes al conjunto V de nodos. Podemos distinguir entre grafos dirigidos y no dirigidos. En un grafo dirigido los pares (v, w) están ordenados, traduciéndose la arista en una flecha que va desde el nodo v al nodo w.

En el caso de un grafo no dirigido, los nodos están unidos mediante líneas sin indicación de dirección.

presenta las principales características que nos podemos encontrar en los grafos:

• Grafo conexo: Cuando entre cada dos nodos del grafo hay un camino.
• Bosque: Es un grafo sin ciclos.
• Árbol libre: es un bosque conexo.

La clase grafo está compuesta de cuatro miembros:

• Adyacentes: Representa la matriz de adyacencia donde cada celda Adyacentes representará el valor del arco que va desde el nodo i al nodo j. Si el valor es 0, consideraremos que no existe arco alguno.
• nodos: que indica el número de nodos.
• vacío: con valor true si el grafo está vacío.
  

Componente fuertemente conexo

En teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos maxi males fuertemente conexos. Estos subgrafos forman una partición del grafo.

Un subgrafo fuertemente conexo es máximales si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo.

El cálculo de los componentes fuertemente conexos de un grafo es uno de los problemas fundamentales de la Teoría de los grafos. El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan en 1970 a base de una búsqueda en profundidad (depth-first search). Otros algoritmos aparecen en los principales textos sobre algorítmica. La complejidad de este algoritmo es O(V+E).

Ejemplo de un grafo dirigido, y sus componentes fuertemente conexos.

[pic 3]

Componente fuertemente conexo

Los algoritmos de grafos proporcionan los medios necesarios para comprender, modelar y establecer los parámetros de predicción de dinámicas que suceden a niveles de alta complejidad. Un ejemplo de esto pueden ser los flujos de recursos o información a través de una red en la que se pueden propagar fallas o datos inválidos, la influencia o la resistencia de los grupos a captar la Information. Dentro de estos importantes algoritmos se encuentran los algoritmos de componentes débilmente conectados que ayudan a detectar conjuntos o grupos de nodos donde cada uno de los nodos es accesible desde cualquier otro nodo en el mismo grupo sin que la dirección de las relaciones tenga algún nivel de influencia. Es posible detectar estas comunidades o conexiones múltiples entre vértices con el algoritmo nombrado en las librerías de Neo4j como “Union Find”. Este detecta los nodos vinculados dentro del grafo no dirigido, entendiendo que puede accederse a él desde cualquier otro vértice.

Grafo Débilmente Conexo:

Si un grafo dirigido no es fuertemente conexo, pero el grafo subyacente (sin sentido en los arcos) es conexo, el grafo es débilmente conexo.

[pic 4]

CAMINO SIMPLE

Un camino simple es aquel que no repite vértices en su recorrido. Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último.

es una sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia.2​ Dos vértices están conectados o son accesibles si existe un camino que forma una trayectoria para llegar de uno al otro; en caso contrario, los vértices están desconectados o bien son inaccesibles.

...