Teorema di Bondy-Chvátal

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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 sia hamiltoniano. Esso generalizza i teoremi precedenti di Ore e Dirac.

Enunciato[modifica | modifica wikitesto]

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

Dimostrazione[modifica | modifica wikitesto]

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

Bibliografia[modifica | modifica wikitesto]