Flashcards de fundamentos de teoría de grafos

Question 1

¿Qué es un grafo $G=(V,E)$?

Accepted Answer

Un grafo es un par ordenado $G=(V,E)$ donde $V$ es un conjunto de vértices (nodos) y $E$ es un conjunto de aristas, donde cada arista une dos vértices (en un grafo no dirigido, una arista es un par no ordenado $\{u,v\}$).

Question 2

¿Cuál es la diferencia entre un recorrido, un camino y un ciclo?

Accepted Answer

Un recorrido puede repetir vértices/aristas. Un camino es un recorrido sin vértices repetidos. Un ciclo es un camino cerrado (inicio = fin) sin vértices repetidos excepto el primero/último.

Question 3

¿Qué significa que un grafo sea planar y cuál es la fórmula de Euler para grafos planares conexos?

Accepted Answer

Planar significa que se puede dibujar en el plano sin cruces de aristas (excepto en los vértices). Para una incrustación planar conexa, $$V-E+F=2,$$ donde $F$ es el número de caras (incluida la cara exterior).

Flashcards de fundamentos de teoría de grafos

Domina las Matemáticas con IA

Recursos de Aprendizaje

Confianza y Reconocimiento