Teorema di Bondy-Chvátal

Il teorema di Bondy-Chvátal è un teorema della teoria dei grafi relativo ai cicli hamiltoniani. È stato provato nel 1976 dal matematico britannico e canadese John Adrian Bondy e dal matematico polacco Václav Chvátal. Fornisce una condizione necessaria e sufficiente affinché un grafo $G$ sia hamiltoniano. Esso generalizza i teoremi precedenti di Ore e Dirac.

Enunciato[modifica | modifica wikitesto]

Il teorema afferma che un grafo $G$ è hamiltoniano se e solo se la sua chiusura $[G]$ è hamiltoniana, ossia possiede un ciclo hamiltoniano.

Dimostrazione[modifica | modifica wikitesto]

Sia $G$ un grafo di $n$ vertici e sia $[G]$ la sua chiusura.
È immediato dimostrare che se un grafo $G$ è hamiltoniano anche la sua chiusura lo è. Infatti $[G]$ è ottenuta da $G$ aggiungendo, se possibile, degli archi, per cui tutti gli archi di $G$ sono anche nella sua chiusura. Di conseguenza se $G$ aveva un ciclo hamiltoniano anche $[G]$ possiede lo stesso ciclo.
Viceversa bisogna ora dimostrare che se $[G]$ è hamiltoniano anche $G$ lo è. Supponiamo che la chiusura di $G$ sia stata creata aggiungendo $K-1$ archi a quelli di $G$ . Sia $G_{1}=G$ e sia $E_{1}$ l'insieme degli archi di $G$ . Sia analogamente $G_{K}=[G]$ e $E_{K}$ l'insieme degli archi della chiusura. Necessariamente si ha $E_{1}\subset E_{K}$ . Per ipotesi $G_{K}$ è hamiltoniano. Supponiamo per assurdo che $G_{1}$ non lo sia. Siano $G_{2},..G_{j-1},G_{j},...,G_{K}$ i grafi ottenuti per costruire $G_{K}$ da $G_{1}$ aggiungendo un arco per volta. Notiamo che se $G_{j}$ è hamiltoniano allora tutti i grafi $G_{i}$ con $i\geq j$ sono hamiltoniani in quanto, come prima visto, $E_{j}\subset E_{i}$ . Se $G_{1}$ non è hamiltoniano mentre $G_{K}$ si, allora deve esserci un indice $2\leq j\leq K$ per il quale $G_{j}$ è hamiltoniano mentre $G_{j-1}$ non lo è. Poiché a $G_{j-1}$ manca un solo arco affinché venga creato un ciclo hamiltoniano, vuol dire che necessariamente $G_{j-1}$ ha un cammino hamiltoniano $(v_{1},v_{2},..,v_{n})$ , dove i vertici sono stati etichettati in modo tale che l'arco che creerebbe il ciclo sia quello che collega i vertici $(v_{1},v_{n})$ . Consideriamo adesso gli insiemi $A=\{v_{i}|(v_{1},v_{i})\in E_{j-1}\}$ e $B=\{v_{i}|(v_{n},v_{i-1})\in E_{j-1}\}$ con $2<i<n$ . $A$ è l'insieme dei vertici in $G_{j-1}$ che hanno un diretto collegamento con $v_{1}$ , $v_{2}$ escluso. $B$ è invece l'insieme dei vertici che hanno il vertice che lo precede direttamente collegato con $v_{n}$ . Notiamo che entrambi gli insiemi sono contenuti in $\{v_{3},..,v_{n-1}\}$ e vale in particolare che la cardinalità di $A$ è pari $|A|=deg(v_{1})-1$ e la cardinalità di $B$ è pari $|B|=deg(v_{n})-1$ (gli elementi di $B$ sono in corrispondenza biunivoca con gli archi incidenti su $v_{n}$ escluso $(v_{n-1},v_{n})$ ). Poiché $G_{j}$ si differenzia da $G_{j-1}$ solo per l'arco tra i vertici $v_{1}$ e $v_{n}$ , sappiamo, per definizione della costruzione della chiusura di un grafo, che in $G_{j-1}$ vale $deg(v_{1})+deg(v_{n})\geq n$ e quindi vale anche $|A|+|B|\geq n-2$ . Ma sia $A$ , sia $B$ sono sottoinsiemi di $\{v_{3},..,v_{n-1}\}$ che ha cardinalità $n-3$ , ne deduciamo che la loro intersezione è non nulla, ossia che esiste un vertice $v_{k}$ in comune tra $A$ e $B$ . È allora possibile costruire in $G_{j-1}$ il seguente ciclo hamiltoniano $(v_{1},...,v_{k-1},v_{n},v_{n-1},..v_{k},v_{1})$ , il che è assurdo in quanto è contrario all'ipotesi che $G_{j-1}$ non sia hamiltoniano. Per cui abbiamo dimostrato che se $[G]=G_{K}$ è hamiltoniano non può esserci un indice $j$ tale che $G_{j-1}$ non sia hamiltoniano e quindi anche $G_{1}=G$ deve essere hamiltoniano.