v = |V| = numero di vertici

e = |E| = numero di spigoli

r = numero di regioni

FORMULA DI EULERO (1752)Se G è un grafo non orientato, connesso e planare, allora ogni sua rappresentazione piana ha r regioni, con

r = e - v + 2.

FORMULA DI EULEROgiovedì 17 aprile 201416:09

GRAFI PLANARI Pagina 1

GRAFI PLANARI Pagina 2

FORMULA DI EULERO PER I POLIEDRI CONVESSISia P un poliedro convesso nello spazio tridimensionale. Sia v = numero dei vertici,e = numero degli spigoli,r = numero delle facce,allora vale la relazione r = e - v + 2 .

Ogni poliedro (convesso) si può trasformare in un grafo connesso e planare.

POLIEDRI CONVESSI giovedì 17 aprile 201416:50

GRAFI PLANARI Pagina 3

COROLLARIO 1Se G(V,E) è un grafo planare e connesso con e > 1, allora e ≤ 3v - 6.

COROLLARIO 2Se G(V,E) è un grafo planare, connesso e bipartito con e > 1, allora e ≤ 2v - 4.

COROLLARIgiovedì 17 aprile 201416:50

GRAFI PLANARI Pagina 4

GRAFI PLANARI Pagina 5

Problema: Quanti colori sono necessari per colorare i paesi di una mappa in modo tale che paesi adiacenti abbiano colori diversi?

Mappa

Grafo planare, ad ogni paese corrisponde un vertice.

Problema: Quanti colori sono necessari per colorare i vertici di un grafo planare, in modo che vertici adiacenti abbiano colori diversi?

Congettura dei 4 colori, dimostrata da Appel e Haken (1976):Tutti i grafi planari sono 4-colorabili.

PROBLEMA DEI QUATTRO COLORIgiovedì 17 aprile 201415:28

GRAFI PLANARI Pagina 6

Qual è il massimo numero possibile di vertici in un grafo con 19 spigoli e tutti i vertici di grado maggiore o uguale a 3?

ESERCIZIO 1giovedì 17 aprile 201409:30

ESERCIZI Pagina 7

Se un grafo ha n vertici, tutti di grado dispari tranne uno, quanti vertici di grado dispari ci sono nel suo complementare?

ESERCIZIO 2giovedì 17 aprile 201409:36

ESERCIZI Pagina 8

Determinare se i seguenti grafi sono bipartiti:

ESERCIZIO 3giovedì 17 aprile 201409:38

ESERCIZI Pagina 9

Dimostrare che un grafo con n vertici e più di

spigoli

non può essere bipartito.

ESERCIZIO 4giovedì 17 aprile 201409:46

ESERCIZI Pagina 10

Dimostrare che tutti i grafi con 5 vertici e con ciascun vertice di grado 2 sono isomorfi. La stessa proprietà vale anche per grafi con 6 vertici?

ESERCIZIO 5giovedì 17 aprile 201409:53

ESERCIZI Pagina 11

I seguenti grafi orientati sono isomorfi?

ESERCIZIO 6giovedì 17 aprile 201409:55

ESERCIZI Pagina 12