Lezione 15 (7 maggio 2001 h. 9.30-10.30)

Una stima del numero di grafi non isomorfi su n vertici

Sia $V=\{1,2,\dots,n\}$ e indichiamo con ${\cal G}_n$ l'insieme dei grafi che hanno V come insieme dei vertici. Dall'esercizio 14.8 segue che $\oldcong$ è una relazione d'equivalenza su ${\cal G}_n$. Indichiamo con $g_n=\left\vert{\cal G}_n\big/\mathchoice {{}_{\!\displaystyle {}\oldcong}} {{... ...{\!\scriptstyle {}\oldcong}} {{}_{\!\scriptscriptstyle {}\oldcong}}\right\vert$.

In parolo povere g_n è il massimo numero di grafi di ${\cal G}_n$ tra loro non isomorfi. ovvero se si è interessati a sapere quanti sono i grafi essenzialmente diversi con vertici V il numero interessante è g_n.

Proposizione 15.1   Con le notazioni appena introdotte si ha che

$$\frac{n^2}{2}\Big( 1 - \frac{1}{n} - \frac{2}{n}\log_2(n)\Big ) \le \log_2(g_n) \le \frac{n^2}{2}\Big( 1 - \frac{1}{n}\Big )$$

Dimostrazione. 

    $\square$

Passeggiate, cammini e cicli

Definizione 15.2   Sia G=(V,E) un grafo una successione finita di vertici $(v_0,\dots, v_n)$ sarà detta

• passeggiata se $\{v_i,v_{i+1}\}\in E$ per ogni $i=0,\dots,n-1$
• cammino se è una passeggiata e $v_i\ne v_j$ per ogni $i\ne j$.
• ciclo se è una passeggiata e $v_i\ne v_j$ per ogni $i\ne j$ a parte v₀=v_n.

Proposizione 15.3   Sia G un grafo e sia $(_0,\dots, v_n)$ un cammino in G allora il grafo G' definito da:

• $V(G')=\{v_0,\dots,v_n\}$
• $E(G')=\big\{\{v_i,v_{i+1}\bigm\vert i=0,\dots,n-1\big\}$

è un sottografo di G isomorfo a P_n.

Dimostrazione.  Esercizio.     $\square$

Proposizione 15.4   Sia G un grafo e sia $(v_0,\dots, v_n)$ un ciclo in G allora il grafo G' definito da:

• $V(G')=\{v_0,\dots,v_{n-1}\}$
• $E(G')=\big\{\{v_i,v_{i+1}\bigm\vert i=0,\dots,n-1\big\}\cup\big\{\{v_n,v_0\}\big\}$

è un sottografo di G isomorfo a C_n.

Dimostrazione.  Esercizio.     $\square$

Osservazione 15.5   In effetti è facile vedere che dare un cammino o un ciclo in un grafo è equivalente a dare un sottografo isomorfo a P_n o C_n per qualche n.

La relazione di essere congiungibili

Definizione 15.6   Sia G=(V,E) e siano $v,w\in V$. Diremo che v e w sono congiungibili con un cammino [risp. una passeggiata] se e siste un cammino [risp. una passeggiata] $(v_0,\dots, v_n)$ tale che v₀=v e v_n=w.

Proposizione 15.7   Le relazione di essere congiungibli da un cammino è una passeggiata d'equivalenza.

Proposizione 15.8   Due punti sono congiungibili mediante un cammino se e solo se lo sono mediante una passeggiata.

Dimostrazione.  Dato che un cammino è una passeggiata, se due vertici sono congiungibili mediante un cammino lo sono anche mediante una passeggiata.

Viceversa. Sia ${\cal P}$    $\square$