ROBOT HORIZONTAL INFO

GRAFOS

TIPOS DE GRAFOS

¿QUE ES?

los grafos se representan mediante los v´ertices conectados por l´ıneas o aristas, estos pueden ser orientados o no orientados. Un grafo G puede ser descrito por el par de v´ertices y aristas, G= (V, A) [1].

Un grafo es una pareja de conjuntos , donde es el conjunto de vértices, y es el conjunto de aristas, este último es un conjunto de pares de la forma tal que . Para simplificar, notaremos la arista como . En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Estructuras de datos en la representación de grafos: Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

ESTRUCTURA DE DATOS

Ruiz valdivia oscar octavio

GRADO DE UN VERTICE

LAZO O BUCLE

Un lazo o bucle en un grafo es un enlace cuyos puntos finales son el mismo nodo. Un grafo se dice simple si no tiene lazos y existe como mucho un enlace entre cada par de nodos (no hay enlaces en paralelo). El grado de incidencia de un nodo es el numero de enlaces que son incidentes en el.

El grado de un vértice es el número de aristas que conectan ese vértice con otros vértices en el grafo. Los vértices que no están conectados a ningún otro vértice tienen un grado de cero.

CAMINO CERRADO

CAMINO

Un camino cerrado es un camino que comienza y termina en el mismo vértice.

¿QUE ES?

Un camino en el grafo G es una sucesión de vértices y arcos: v(0), a(1), v(1), a(2), v(2), ... , a(k), v(k); tal que los extremos del arco a(i) son los vértices v(i-1) y v(i). Longitud de un camino: es el número de arcos que componen el camino.

CICLO

¿QUE ES?

Un ciclo es un camino cerrado que no tiene vértices repetidos, excepto el vértice inicial y final que son iguales.

GRAFO ÁRBOL

GRAFO CONEXO

¿QUE ES?

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay n n-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

GRAFO COMPLETO

GRAFO ETIQUETADO

¿QUE ES?

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

¿QUE ES?

un grafo etiquetado es un grafo cuyos vértices tienen nombres o etiquetas.​ Estas etiquetas comúnmente son números enteros.

MULTIGRAFO

SUBGRAFO

¿QUE ES?

¿QUE ES?

Un multigrafo o grafo multivariado es una generalización de un grafo que permite aristas múltiples, o equivalentemente, más de un conjunto de aristas. De esta forma, dos nodos pueden estar conectados por más de una arista.​

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación). El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.

GRAFO DIRIGIDO

LISTA DE ADYACENCIA

¿Que es?

¿Que es?

Un grafo dirigido es un grafo en el que las aristas tienen una dirección. Matriz de adyacencia: Una matriz de adyacencia es una matriz cuadrada que se utiliza para representar un grafo. La entrada (i, j) de la matriz representa la arista que conecta los vértices i y j.

la lista de adyacencia asocia cada vértice del grafo con la colección de sus vértices o aristas vecinos, es decir, cada vértice almacena una lista de vértices adyacentes. Hay muchas variaciones de la representación de la lista de adyacencia dependiendo de la implementación.

Bibliografía

García, M. E. (s/f). Los grafos son modelos matemáticos de numerosas situaciones reales: un mapa de. Utm.mx. Recuperado el 25 de marzo de 2023, de https://www.utm.mx/~mgarcia/ED4%28Grafos%29.pdf Grafos, 1. (s/f). Proped ́eutico: Programaci ́on. Inaoep.mx. Recuperado el 25 de marzo de 2023, de https://posgrados.inaoep.mx/archivos/PosCsComputacionales/Curso_Propedeutico/Programacion_Estructuras_Datos/Capitulo_10_Grafos.pdf De la computación, E. M. y. en C., De grafos, la T., Conjunto, U., Vacío, N., Vértices, de O. L., Mediante, un G. se, & Líneas, C. P. (s/f). Teoría de grafos. Edu.co. Recuperado el 25 de marzo de 2023, de https://www.unipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general/11072012/grafo3.pdf Implementación de grafos en C++ usando STL. (s/f). Techiedelight.com. Recuperado el 25 de marzo de 2023, de https://www.techiedelight.com/es/graph-implementation-using-stl/