Colaborativo de estructura de datos

TRABAJO COLABORATIVO CONTEXTUALIZADO

ESTRUCTURA DE DATOS

CIPA ZAMBRANO

ELIAS JABBA PADILLA

JOSE CAMPO VACA

DAVID CASTELLAR ESPAÑA

DELVIS GONZÁLEZ

TUTOR(A)

III SEMESTRE INGENIERIA DE SOFTWARE

UNIVERSIDAD DE CARTAGENA

CARMEN DE BOLIVAR

2021

OBJETIVOS

 Reconocer de manera amplia y correcta el tema de grafos

 Explicar las aplicaciones que tienen los grafos en distintas áreas

 Identificar todos y cada uno de los tipos de grafos

DESCRIPCION DEL PROBLEMA

Este capítulo profundiza en otra estructura de datos no lineal: el grafo. Como hemos hecho con otras estructuras de datos. Discutiremos la representación de los grafos en memoria y Presentaremos varias operaciones y algoritmos sobre ellos. En particular discutiremos la búsqueda en anchura y la búsqueda en profundidad para nuestros grafos. También se repasaran ciertas aplicaciones de los grafos, incluyendo la ordenación topológica.

MARCO CONCEPTUAL

Grafos dirigidos y no dirigidos

Dependiendo del tipo de relación entre los vértices del grafo, se definen distintos tipos de grafos. Así se distinguen aristas dirigidas y no dirigidas:

Arista dirigida: es aquella que define un par ordenado de vértices (u,v), donde el primer vértice u es el origen de la arista y el segundo vértice v es el término (o vértice final). El par (u, v) ≠ (v, u).

Arista no dirigida: es aquella que define un par no ordenado de vértices (u, v), donde (u, v) = (v, u).

De esta forma se distinguen entre grafos dirigidos y grafos no dirigidos.

Grafo dirigido: Es aquel cuyas aristas son dirigidas. Los grafos dirigidos suelen representar relaciones asimétricas como por ejemplo: relaciones de herencia, los vuelos entre ciudades, etc.

Grafo no dirigido: Es aquel cuyas aristas son no dirigidas. Representan relaciones simétricas como relaciones de hermandad y colaboración, conexiones de transportes, etc.

Incidencia, adyacencia y grado de un vértice

Sea un grafo G = (V, A), los vértices u y v pertenecientes a V; y una arista (u,v) perteneciente a A, se dice que:

Incidencia: la arista (u,v) es incidente con los vértices u y con v.

Adyacencia: Dos vértices u y v son adyacentes si existe una arista cuyos vértices sean u y v:

o El vértice u es adyacente a v

o El vértice v es adyacente desde u

Grado: El grado de un vértice u es el número de vértices adyacentes a u. Para un grafo dirigido, el grado de salida de un vértice u es el número de vértices adyacentes desde u, mientras que el grado de entrada de un vértice u es el número de vértices adyacentes a u. La Figura 5.2 muestra los grados de los vértices para un grafo no dirigido y un grafo dirigido.

METODOLOGIA

DEFINICIÓN DE GRAFO

A menudo, cuando se observa la red de rutas aéreas de un país interesa observar cómo ir de una ciudad a otra por las rutas posibles. En consecuencia, se tiene dos conjuntos de objetos distintos: ciudades y rutas. La Figura 5.1 muestra una manera de representar la relación existente entre las ciudades y las rutas, así como la distancia entre las distintas ciudades.

En general, un grafo es una manera de representar relaciones que existen entre pares de objetos. Así, un grafo es un conjunto de objetos, llamados vértices1, y relaciones entre objetos que establecen una relación entre pares de vértices, representadas por aristas.

En el ejemplo anterior, el grafo de la Figura 5.1 representa las conexiones aéreas entre ciudades. Los vértices representarían las ciudades. Las aristas representan las conexiones entre ciudades y, en este caso, se almacenan la distancia en kilómetros entre las ciudades que une.

Definición 1. Un grafo se define como un par G = (V, A), donde V es un conjunto finito no vacío de vértices y A es un conjunto de pares de vértices de V, es decir, las aristas.

Definición 2. Un grafo G se define como un par ordenado, G = (V, A), donde V es un conjunto finito y A es un conjunto que consta de dos elementos de V.

La terminología de la teoría de grafos no es estándar. El concepto de vértice también se referencia como nodo. Asimismo, aristas (edges en inglés) y arcos denotan el mismo elemento. En algunos libros, sin embargo, se establece una diferencia entre aristas (unen vértices en un grafo no dirigido) y arcos (unen vértices en grafos dirigidos). En este capítulo, se dará preferencia a los términos vértice y arista.

PRESENTACION DE RESULTADOS

Grafo no dirigido: Grafo dirigido:

Grado (a) = 3 GradoE (a) = 2 GradoS (a) = 1

Grado (b) = 3 GradoE (b) = 3 GradoS (b) = 0

Grado (c) = 2 GradoE (c) = 0 GradoS (c) = 2

Grado (d) = 4 GradoE (d) = 2 GradoS (d) = 2

Grado (e) = 4 GradoE (e) = 1 GradoS (e) = 3

Figura 5.2. Grado de los vértices en un grafo no dirigido y dirigido.

Grafos simples y multígrafos

Un grafo simple es aquel que no tiene aristas paralelas o múltiples que unan el mismo par de vértices. Un grafo que cuente con múltiples aristas entre dos vértices se denomina multigrafo. La Figura 5.3 muestra un ejemplo de grafo simple y de multigrafo, donde existen aristas paralelas incidentes a los vértices a y d, y e y d. En este caso, se dice que el grafo tiene multiplicidad 2 (máximo de aristas paralelas entre dos vértices).

GRAFO SIMPLE:

MULTIGRAFO:

Figura 5.3. Grafo simple y grafo no simple

Si asumimos un grafo simple, se observan las siguientes propiedades: Si G

...