Flashcard sui fondamenti della teoria dei grafi

Question 1

Che cos'è un grafo $G=(V,E)$?

Accepted Answer

Un grafo è una coppia ordinata $G=(V,E)$ in cui $V$ è un insieme di vertici (nodi) ed $E$ è un insieme di archi, ciascun arco collega due vertici (in un grafo non orientato, un arco è una coppia non ordinata $\{u,v\}$).

Question 2

Qual è la differenza tra una passeggiata, un cammino e un ciclo?

Accepted Answer

Una passeggiata può ripetere vertici/archi. Un cammino è una passeggiata senza vertici ripetuti. Un ciclo è un cammino chiuso (inizio = fine) senza vertici ripetuti tranne il primo/ultimo.

Question 3

Che cosa significa che un grafo è planare e qual è la formula di Eulero per grafi planari connessi?

Accepted Answer

Planare significa che può essere disegnato sul piano senza incroci di archi (tranne che nei vertici). Per un'immersione planare connessa, $$V-E+F=2,$$ dove $F$ è il numero di facce (inclusa la faccia esterna).

Flashcard sui fondamenti della teoria dei grafi

Padroneggia la Matematica con l'IA

Risorse di Apprendimento

Affidabile e Riconosciuto