Flashcards de fundamentos de teoria dos grafos

Question 1

O que é um grafo $G=(V,E)$?

Accepted Answer

Um grafo é um par ordenado $G=(V,E)$ em que $V$ é um conjunto de vértices (nós) e $E$ é um conjunto de arestas, cada aresta ligando dois vértices (num grafo não direcionado, uma aresta é um par não ordenado $\{u,v\}$).

Question 2

Qual é a diferença entre um passeio, um caminho e um ciclo?

Accepted Answer

Um passeio pode repetir vértices/arestas. Um caminho é um passeio sem repetição de vértices. Um ciclo é um caminho fechado (início = fim) sem repetição de vértices, exceto o primeiro/último.

Question 3

O que significa um grafo ser planar e qual é a fórmula de Euler para grafos planares conexos?

Accepted Answer

Planar significa que pode ser desenhado no plano sem cruzamento de arestas (exceto nos vértices). Para uma imersão planar conexa, $$V-E+F=2,$$ onde $F$ é o número de faces (incluindo a face externa).

Flashcards de fundamentos de teoria dos grafos

Domine Matemática com IA

Recursos de Aprendizagem

Confiável e Reconhecido