TEORÍA DE GRAFOS

Proyecto de Aula Primera Entrega

PRESENTADO POR:

Santiago Bermúdez Bonilla

Santiago Ladino Giraldo

PRESENTADO A:

Gustavo Adolfo Gamarra Bustamante

Corporación Unificada Nacional de Educación Superior CUN

Ingeniería de Sistemas

Investigación De Operaciones 51262

Bogotá D.C

2021

INTRODUCCIÓN

En las matemáticas y las ciencias de la computación, existe la teoría de grafos, que también es conocida como la teoría de las gráficas, cuyo objetivo es el estudiar las propiedades de los grafos o también llamados como gráficas.

Aunque por lo general se tenga una visión muy matemática y se piense que solo se usa en el desarrollo de problemas matemáticos, sus usos se expanden a campos en los cuales inclusive puede ayer a detectar crimines por fraude.

TEORÍA DE GRAFOS

En las matemáticas y las ciencias de la computación, existe la teoría de grafos, que también es conocida como la teoría de las gráficas, cuyo objetivo es el estudiar las propiedades de los grafos o también llamados como gráficas. Un grafo, tiene como definición el ser un conjunto, no vacío, que posee objetos que son llamados vértices o también nodos, además de una selección de pares de vértices, que son conocidos como aristas, y que pueden ser orientados o no. Particularmente, un grafo es representado mediante una serie de puntos, siendo estos los vértices, que se conectan por líneas o las también llamadas aristas.

Hay diferentes maneras de almacenar grafos en una computadora. La estructura de datos usada necesita de las características del grafo, y el algoritmo que se usa para su manipulación. Dada la existencia de estructuras que son más sencillas y usadas, entre ellas se encuentran las listas y las matrices, aun cuando comúnmente se usa una combinación de estas. Las listas son particularmente preferidas en grafos dispersos, ya que estos tienen un uso eficiente de la memoria. En cambio, las matrices proporcionan un acceso rápido, pero pueden llegar a consumir una gran cantidad de memoria.

• lista de incidencia:

 Las aristas se representan con un vector de pares, siendo estos conocidos como ordenados, si el grafo es dirigido, por lo cual resulta que cada par representa a una de las aristas.

• lista de adyacencia:

Cada vértice posee una lista de vértices que son adyacentes a él. Esto se identifica como una de las mayores causas de la redundancia en un grafo no dirigido, ya que A se halla en la lista de adyacencia de B y, al contrario, pero con ello las búsquedas son más rápidas, en comparación al costo de almacenamiento extra. En dichas estructuras de datos e tiene como objetivo el asociar a los vértices I de este grafo en una lista que tiene a todos los vértices j que son o pueden ser adyacentes a él. De dicho modo sólo se reserva memoria para los arcos adyacentes a I y no para todos los posibles arcos que tengan su origen en I. El grafo, por consiguiente, se representa a través de un vector de n componentes, en cuyo caso cada componente va a tener una lista de adyacencia que corresponde a cada uno de los vértices del grafo. Cada elemento de esta lista se compone de un campo que indica el vértice adyacente. Dado el caso en el que el grafo sea etiquetado, se tendrá que añadir un campo secundario para así mostrar el valor de la etiqueta.

...