3 - Grafos Flashcards
¿Qué es un grafo en el contexto de la teoría de grafos?
Un grafo es una estructura matemática que representa relaciones entre pares de objetos.
En un grafo, los objetos se denominan vértices o nodos, y las relaciones entre ellos se denominan aristas o bordes.
Los grafos pueden ser dirigidos o no dirigidos, dependiendo de si las aristas tienen una dirección.
Define los términos “vértice” y “arista” en un grafo.
Un vértice es un punto o nodo dentro de un grafo que representa un objeto o entidad.
Una arista es una conexión entre dos vértices, que puede ser dirigida (con una dirección específica) o no dirigida.
Las aristas representan las relaciones o interacciones entre los vértices.
¿Qué representa la notación G = (V, E) en un grafo?
La notación G = (V, E) representa un grafo G, donde V es el conjunto de vértices (nodos) y E es el conjunto de aristas (bordes o “edges”) que conectan los vértices.
En términos simples, V son los puntos y E son las líneas que los conectan.
¿Qué significa que dos vértices u y v sean adyacentes en un grafo?
Dos vértices u y v son adyacentes si existe una arista que los conecta directamente.
Esto implica que existe una relación entre esos dos vértices dentro del grafo.
¿Cómo se define que una arista es incidente a un vértice en un grafo?
Una arista es incidente a un vértice si el vértice es uno de los puntos extremos de la arista.
En otras palabras, una arista conecta un vértice con otro, y por lo tanto, ambos vértices son incidentes con esa arista.
Explica la diferencia entre un multigrafo y un grafo simple.
Un grafo simple permite una única arista entre cualquier par de vértices, mientras que un multigrafo permite múltiples aristas entre dos vértices.
Los multigrafos se utilizan para representar situaciones donde pueden existir varias relaciones entre los mismos nodos.
¿Qué es un lazo en un grafo y en qué tipo de grafo se permite?
Un lazo es una arista que conecta un vértice consigo mismo. Los lazos solo se permiten en ciertos tipos de grafos, como los pseudografos, que permiten aristas entre un vértice y él mismo.
Describe un grafo dirigido (dígrafo) y cómo se diferencia de un grafo no dirigido.
Un grafo dirigido o dígrafo es un grafo en el que las aristas tienen una dirección específica. Es decir, las conexiones entre vértices son unidireccionales. En contraste, en un grafo no dirigido, las aristas no tienen dirección, y la relación entre dos vértices es bidireccional.
¿Qué es una orientación de un grafo?
La orientación de un grafo es el proceso de asignar una dirección a las aristas de un grafo no dirigido, convirtiéndolo en un grafo dirigido o dígrafo. Este proceso asigna una dirección a cada arista, lo que implica que las conexiones entre los nodos se vuelven unidireccionales.
¿Cómo se suele representar una arista en un grafo?
Una arista entre dos vértices u y v generalmente se representa como un par (u, v).
- Si el grafo es no dirigido, no importa el orden de los vértices.
- Si es dirigido, el par (u, v) indica una arista de u a v.
¿Cuál es la diferencia entre una arista en un grafo simple y una arista en un multigrafo?
En un grafo simple, solo puede existir una única arista entre dos vértices. En un multigrafo, puede haber varias aristas entre el mismo par de vértices, permitiendo la representación de múltiples relaciones entre los mismos nodos.
En el Ejemplo 1, ¿cuál es el conjunto de vértices y el conjunto de aristas del grafo G?
En el Ejemplo 1 del libro, el grafo G tiene el conjunto de vértices V = {1, 2, 3} y el conjunto de aristas E = {(1, 2), (1, 3)}.
En el Ejemplo 2, describe el grafo en el que los vértices representan personas en una fiesta y las aristas representan apretones de manos.
En el Ejemplo 2, los vértices representan personas en una fiesta y las aristas representan apretones de manos entre ellas. El conjunto de aristas E contiene pares de personas que se dieron la mano durante la fiesta.
En el Ejemplo 3, ¿cómo están conectados los vértices en el grafo que utiliza puntos en el plano con coordenadas enteras?
En el Ejemplo 3, los vértices son puntos en un plano con coordenadas enteras, y los vértices están conectados por una arista si la distancia entre ellos es exactamente 1. Este tipo de grafo se llama “grafo de cuadrícula”.
¿Qué es el producto cartesiano en el Ejemplo 3 y cómo se utiliza para formar un grafo?
El producto cartesiano en el Ejemplo 3 es el conjunto de pares de números enteros que forman las coordenadas de los vértices en un plano. Se utiliza para definir el conjunto de vértices en el grafo, donde las aristas conectan vértices adyacentes en el espacio cartesiano.
