Primi elementi della teoria dei grafi

Poliedri convessi e grafi planari

Un poliedro è un solido limitato da facce poligonali tali che ogni loro lato sia comune a due e solo a due facce

Può essere convesso o concavo. E' convesso se ogni sua faccia appartiene a un piano che lascia tutto il solido da una stessa parte. E' concavo se esiste almeno una faccia il cui piano divide il solido in due parti.

Lo scheletro di un poliedro convesso costituito dai vertici e dagli spigoli è un grafo nello spazio che può essere rappresentato nel piano con un grafo planare che conserva tutte le caratteristiche del grafo tridimensionale. Infatti, è possibile proiettare da un punto esterno del poliedro il grafo tridimensionale su una superficie piana

Oppure supponendo che gli spigoli del poliedro siano dei fili elastici è possibile tirare i quattro vertici della faccia superiore fino a stenderli su un piano, senza che si verifichi alcuna sovrapposizione di spigoli o di vertici, come si vede in fotografia.

Il grafo planare risultante è detto grafo poliedrale o grafo poligonale perchè è un grafo connesso in cui gli spigoli lo dividono in parti poligonali dette facce del grafo. Ogni faccia è quindi una regione di piano racchiusa in un circuito minimale.

Ecco ad esempio i grafi poliedrali dei cinque solidi platonici.