Grafo planare: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
HermesII (discussione | contributi)
Nessun oggetto della modifica
Corregge uno o più errori comuni o refusi o entità, replaced: a a → a using AWB
Riga 52:
In altre parole, la [[caratteristica di Eulero]] è 2. Come nell’illustrazione, nel primo grafo planare mostrato su, abbiamo ''v''=6, ''e''=7 e ''f''=3. Se il secondo grafo è ridisegnato senza archi che si intersecano, abbiamo ‘’v’’=4, ‘’e’’=6 e ''f''= 4. La formula di Eulero può essere dimostrata come segue: se il grafo non è un [[albero (teoria dei grafi)|albero]], allora togliamo uno spigolo che completa un ciclo. Questo abbassa sia ''e'' che ''f'' di una unità, lasciando invariato ''v'' − ''e'' + ''f''. Si può ripetere la manovra fino ad ottenere un albero. Gli alberi hanno ''v''=''e'' +1 e ''f''=1, dimostrando che ''v'' - ''e'' + ''f'' = 2.
 
In un grafo planare finito, semplice e connesso, qualsiasi faccia (eccetto quella illimitata) è limitata da almeno tre archi e ogni spigolo è incidente di al più due facce; usando la formula di Eulero, si può dimostrare che questi grafi sono ''sparsi'' nel senso che ''e'' ≤ 3''v'' - 6 if ''v'' ≥ 3.
 
Notiamo che la formula di Eulero è valida anche per i [[poliedri]] semplici. Questa non è una coincidenza: ogni poliedro semplice può essere trasformato in un grafo semplice connesso usando i vertici del poliedro come vertici del grafo e gli spigoli del poliedro come archi del grafo. Le facce del grafo planare risultante corrispondono alle facce del poliedro. Per esempio il secondo grafo planare mostrato all'inizio corrisponde al [[tetraedro]]. Non tutti i grafi planari connessi semplici possono essere associati a poliedri semplici; ad esempio gli alberi non possono essere riguardati come poliedri. Un teorema di [[Ernst Steinitz]] dice che i grafi planari associati ai poliedri convessi (o equivalentemente quelli associati a a poliedri semplici) sono precisamente i grafi planari semplici [[connessione nei grafi|3-connessi]].
 
Notiamo che la formula di Eulero è valida anche per i [[poliedri]] semplici. Questa non è una coincidenza: ogni poliedro semplice può essere trasformato in un grafo semplice connesso usando i vertici del poliedro come vertici del grafo e gli spigoli del poliedro come archi del grafo. Le facce del grafo planare risultante corrispondono alle facce del poliedro. Per esempio il secondo grafo planare mostrato all'inizio corrisponde al [[tetraedro]]. Non tutti i grafi planari connessi semplici possono essere associati a poliedri semplici; ad esempio gli alberi non possono essere riguardati come poliedri. Un teorema di [[Ernst Steinitz]] dice che i grafi planari associati ai poliedri convessi (o equivalentemente quelli associati a a poliedri semplici) sono precisamente i grafi planari semplici [[connessione nei grafi|3-connessi]].
 
==Casi particolari==
 
===Grafi massimali===
Un grafo semplice è chiamato '''planare massimale''' se è planare, e se con l’aggiunta di un qualunque nuovo spigolo tra due vertici presenti fa cadere la planarità. Tutte le facce (eccetto al più una) sono allora limitate da tre archi; questo giustifica il termine alternativo di '''grafo triangolare''' che si usa per questi grafi. Se un grafo triangolare ha ''v'' vertici con ''v''>2, allora ha precisamente 3''v''-6 archi e 2''v''-4 facce.
Line 79 ⟶ 77:
 
{{Portale|matematica}}
 
[[Categoria:Teoria dei grafi]]