Teoría de Gráficas: Conceptos y Aplicaciones Prácticas

Clase 17 de 40 • Curso de Matemáticas Discretas

Resumen

El concepto básico de un gráfico es, un modelo matemático que sirve para representar las relaciones entre objetos de un conjunto.
Un gráfico o grafo es un conjunto de vértices, o nodos, que están conectados a través de aristas, líneas o conexiones.

Hay varios tipos de grafos, el primero de todos es el nodo simple donde tenemos los nodos y las conexiones gracias a las cuales nos podemos mover fácilmente a través del grafo.

El Multígrafo tiene varias conexiones entre dos nodos, permitiendo tener dos rutas distintas para estos nodos.
Un Pseudografo al igual que el multígrafo puede tener múltiples conexiones entre dos nodos y, además, una de estas conexiones puede partir y terminar en el mismo nodo.
El Grafo Ponderado cuenta con un valor dentro de las conexiones, esto puede verse como el costo, o recurso, de una ruta de nodos.
Por último, el Grafo Dirigido establece una dirección en las conexiones, esta dirección se representa con una flecha, también existe el Multígrafo Dirigido que cuenta con dirección en las conexiones y puede haber múltiples conexiones entre dos nodos.

Jose Rodriguez

student•

Las matematicas nos permite rutas optimas, para mejor eficiencia.

Tipos de Graficos.

Simples. Lineas entre puntos, pero solo un camino de un punto a otro .
Multigrafo. Representa diferentes caminos para llegar al mismo punto.
Pseudografo, Perifericos o caminos que salen de un punto A y regresan al mismo punto A.
Grafo Ponderado, Nodos unidos por lineas pero con unidades metricas que nos representan una unidad o recurso para optimiozar las rutas.
Grafo Dirigido. Caminos de una sola via de un punto a otro, sin retorno.
Multigrafo dirigido. Caminos de una sola ruta pero con varias rutas para llegar al mismo punto.

Sergio Orduz

teacher•

Genial. Gracias Barinet por tu resumen!!! 😄

Hector Idme

student•

Buen resumen !!!

Josue Noha Valdivia

student•

Teoría de Gráficas o Grafos Los grafos son un modelo matemático que representa las relaciones entre elementos de un conjunto. Están formados por:

Vertices o nodos (V): representan los elementos en sí
Aristas (E): Representan las relaciones que hay en los vertices.

Tipos de Grafos

Simple: Son los grafos que tienen una sola arista entre los nodos y no tienen nodos que se conectan a sí mismos
Multigrafo: Son grafos que pueden tener múltiples conexiones entre dos nodos.
Pseudografo: Son los grafos que además de tener múltiples conexiones entre nodos también contienen nodos que se relacionan consigo mismos.
Grafo ponderado: Un grafo en el que se representa numéricamente alguna propiedad relevante en las conexiones.
Grafo dirigido: Grafos que representan la dirección que se pueden tomar en las relaciones.

Nota: Puede darse el caso de una combinación de los grafos ponderados y dirigidos con los otros tipos de grafos

Raul Romero

student•

Buen resumen Josue Noha te quedo genial 😄.

johan Stever Rodriguez Molina

student•

Un apunte curioso es que tensorflow en sus versiones anteriores a la 2.0, usaba este enfoque de "DAG" ( directed acyclic graph) en la construcción de nuestro código, el cual se veia como un grafo dirigido. Así podía usarse la ventaja del paradigma de cálculos en paralelo tan importante en tareas de Big data.

Luis Eduardo Salamanca Garcia

student•

Percival Ernesto Amezola Rivera

student•

No entiendo para que sería un enlace al mismo nodo. ¿Para qué servirá?

Manuel Alejandro Robles Nieto

student•

Rafael Bustamante

student•

https://posgrados.inaoep.mx/archivos/PosCsComputacionales/Curso_Propedeutico/Matematicas_Discretas/Capitulo_4_Grafos.pdf

Luis Manuel Maya Castrejón

student•

No entiendo por que le llaman teoría de gráficas, para mi es teoría de grafos.

Joseph Lázaro Ricardo

student•

Solo puedes pasar una vez por cada puente y debes recorrer todas las islas. Diviertanse un rato como Euler (;

Max Andy Diaz Neyra

student•

Aporte historico del modulo En el siglo 18 en Prusia, la ciudad de Koenigsberg esta divida por un río y las partes de la ciudad se conectaba mediante 7 puentes. Se tenia una duda: se podria recorrer toda la ciudad cruzando una sola vez cada uno de los puentes. En el año 1736, el suizo Leonard Euler dio la solucion para este problema, conocido ho como los 7 puentes de Koenigsberg . Su preciosa demostracion dejó sentada las bases de la topologia y teoria de grafos.

Fernando Carlos Paz Gómez

student•

Es lo mismo GRAFO y GRÁFICO?? (Sergio lo utiliza como igual, pero a mí me confunde con los gráficos de barras, pay, etc).

Milton Martinez

student•

Varía por región el uso de gráfico o grafo para referirse a "graph" del inglés.

Yo prefiero grafo jajajaj

Mateo Paloma

student•

Grafo viene de la forma que toma osea los circulos y las líneas pero al final del día es un gráfico por lo que sería equivalente.

Percival Ernesto Amezola Rivera

student•

¿Para qué servirá un enlace al mismo nodo?

Joalin Pineda

student•

Hola! Hay muchas utilidades dependiendo de la rama del conocimiento en la que te interese aplicarla, un ejemplo puede ser una ruta crítica, en la cual defines varias tareas para llegar a un resultado (o nodo común), sin embargo, para ello puedes pasar por varios caminos, todos llegan al mismo resultado o nodo, sin embargo, nos interesa el más óptimo, o el que implica menos tareas para llegar al resultado, es ahí donde vemos la utilidad de los grafos.

Cesar Caceres

student•

Ahora ya le encuentro lógica a como deciden los routers el camino mas optimo para enviar el trafico de datos.

Yelitza Ibonny Cruz Corpuna

student•

te quiero mucho profe :3 ♥

Emmanuel M

student•

Creo que la presentación tiene un dato erróneo: en el gráfico del grafo dirigido, entre el nodo “a” y el nodo “b” hay una flecha con los 2 sentidos ¿No esta flecha debería de estar en un solo sentido? ya sea hacia el nodo “a” o hacia el nodo “b”

Sergio Orduz

teacher•

Hola @emmanuelMr en la mayoría de grafos dirigidos nos encontramos con flechas en una sola dirección, entonces en este caso otra forma alternativa sería colocar una flecha sentido AB y otr flecha sentido BA, sin embargo me he encontrdo con algunos libros en donde se expresa de esta forma. Lo importante es que se entienda que la conexión es en ambos sentidos 😄

FRANK MAIKOL CARRASCO MAMANI

student•

Luis Fernando Úbeda Camacho

student•

Apuntes de clase

Teoría de Grafos

Un grafo es un modelo matemático que sirve para representar las relaciones entre objetos de un conjunto, son nodos conectados a través de conexiones
Dependiendo del tipo de relaciones podemos tener diferentes tipos de grafos:
· Simple
· Multigrafo
· Pseudografo
· Ponderado
· Dirigido
· Multigrafo dirigido