4 - Grafos parte 2 Flashcards
¿Qué es un grafo completo y cuáles son sus características principales?
Un grafo completo es un grafo en el que cada par de vértices distintos está conectado por una única arista. Esto significa que todos los vértices son adyacentes entre sí.
Las principales características de un grafo completo son:
- Cada vértice tiene un grado de n-1 donde n es el número total de vértices.
- El número de aristas es máximo y está dado por n(n-1)/2
- El diámetro del grafo es 1, ya que cualquier vértice puede llegar a otro en una sola arista.
¿Cuántas aristas tiene un grafo completo con (n) vértices?
El número de aristas en un grafo completo con (n) vértices se calcula con la fórmula: n(n-1)/2
¿Qué aplicaciones prácticas tienen los grafos completos en redes de comunicación y transporte?
- Redes de comunicación: En el diseño de redes completamente conectadas, donde cada nodo (dispositivo) puede comunicarse directamente con cualquier otro nodo.
- Optimización de rutas de transporte: Para estudiar la conexión directa entre ciudades o puntos de entrega, minimizando la distancia entre ellos.
- Teoría de juegos: Modelar situaciones en las que todos los jugadores están relacionados entre sí.
¿Qué es un grafo bipartito y cómo se define formalmente?
Un grafo bipartito es un grafo cuyos vértices pueden dividirse en dos subconjuntos disjuntos
¿Cuáles son las propiedades matemáticas de un grafo bipartito completo?
Ver el Google colab
¿En qué consiste el problema del emparejamiento en un grafo bipartito?
El problema del emparejamiento consiste en encontrar un conjunto de aristas en un grafo bipartito donde cada vértice esté conectado a exactamente un vértice del otro conjunto. Es un problema clave en algoritmos de asignación y optimización.
Explica la diferencia entre un ciclo par y un ciclo impar en teoría de grafos.
Un ciclo par es un ciclo que tiene un número par de aristas, mientras que un ciclo impar tiene un número impar de aristas. En los grafos bipartitos, solo pueden existir ciclos pares.
¿Qué condiciones debe cumplir un grafo para contener un ciclo euleriano?
Para que un grafo tenga un ciclo euleriano (un ciclo que recorre cada arista exactamente una vez), debe cumplir con las siguientes condiciones:
- El grafo debe ser conexo.
- Todos los vértices deben tener un grado par.
¿Qué es un ciclo dirigido y cómo se representa en un grafo dirigido?
Un ciclo dirigido es una secuencia de arcos en un grafo dirigido que comienza y termina en el mismo vértice, siguiendo la dirección de las aristas. Se representa mediante una secuencia de vértices donde cada vértice está conectado al siguiente en la secuencia mediante un arco dirigido.
¿Qué aplicaciones tienen los ciclos en teoría de grafos en problemas de optimización?
Los ciclos son fundamentales en problemas de optimización, como:
- Problema del viajante: Encontrar el ciclo hamiltoniano de menor costo en un grafo ponderado.
- Problema del cartero chino: Encontrar un ciclo euleriano que recorra todas las aristas de un grafo con el menor costo.
¿Qué es un grafo dirigido y cómo se diferencian sus aristas de un grafo no dirigido?
Un grafo dirigido es aquel en el que las aristas tienen una dirección. En contraste, en un grafo no dirigido, las aristas no tienen dirección, lo que implica que la relación entre dos vértices es bidireccional.
Explica el concepto de vecindario de un vértice en un grafo.
El vecindario de un vértice ven un grafo es el conjunto de vértices que son adyacentes a ves decir, aquellos vértices que están conectados a mediante una arista directa.
¿Qué es el grado de un vértice en un grafo y cómo se calcula?
El grado de un vértice es el número de aristas que están conectadas a ese vértice. En un grafo no dirigido, es el número de vecinos del vértice. En un grafo dirigido, se distingue entre el grado de entrada (número de arcos que llegan al vértice) y el grado de salida (número de arcos que parten del vértice).
¿Qué aplicaciones tienen los grafos bipartitos en la biología y la química?
Los grafos bipartitos se utilizan en:
- Biología: Para modelar redes tróficas, donde un subconjunto representa depredadores y el otro representa presas.
- Química: Para modelar moléculas en las que los átomos de diferentes tipos se conectan entre sí, como en compuestos organometálicos.
¿Cómo se utiliza un grafo bipartito en sistemas de recomendación de productos?
En sistemas de recomendación, los grafos bipartitos se utilizan para modelar relaciones entre usuarios y productos, donde los usuarios forman un subconjunto y los productos otro. Las aristas representan interacciones como compras o valoraciones.
