hamiltoniano
Funzione matematica (dal nome del matematico irlandese W.R. Hamilton, 1805-1865) utilizzata per risolvere un problema di controllo ottimale (➔) in cui il tempo è trattato come una variabile [...] continua, secondo il principio di massimo proposto da L. Pontryagin (➔ Pontryagin, principio di); alternativamente, R. Bellman ha sviluppato un’analisi equivalente in un modello in cui il tempo è una variabile ...
Leggi Tutto
ciclohamiltonianociclohamiltoniano in un grafo orientato G = (X, A), cammino hamiltoniano chiuso: contiene tutti i nodi una sola volta ed esiste un arco che collega l’ultimo nodo al primo. In un grafo [...] non sempre esiste un ciclohamiltoniano. Un particolare ciclohamiltoniano è ricercato nel cosiddetto problema del → commesso viaggiatore. ...
Leggi Tutto
Nel linguaggio scientifico, struttura relazionale formata da un insieme finito di oggetti detti nodi o vertici, e da un insieme di relazioni tra coppie di oggetti dette archi o spigoli. Per indicare un [...] Nel 1759 Eulero scrisse un’altra importante memoria sulla teoria dei g. definendo, fra l’altro, il problema del ciclohamiltoniano, ossia del ciclo che passa esattamente una volta per tutti i nodi di un grafo.
Nel 1771 anche A.-T. Vandermonde trattò ...
Leggi Tutto
Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, [...] importante per la combinatoria perché è noto che molti problemi intrattabili (tra cui quello dell’esistenza di un ciclohamiltoniano in un grafo) sono in NP. Nel caso – improbabile – di una soluzione positiva, vi sarebbero algoritmi veloci per ...
Leggi Tutto
Informatica
Fabrizio Luccio
Franco P. Preparata
Carl-Erik Fröberg
Piero Sguazzero
Piero Dell'Orco e Tomaso Poggio
Teoria della computazione di Fabrizio Luccio
SOMMARIO: 1. Origine e motivazioni. [...] G di n vertici, ai cui spigoli sono associati pesi interi positivi, e un intero positivo k, stabilire se esiste in G un ciclohamiltoniano la cui somma dei pesi sia ≤ k.
Problema dell'impaccamento (Pi). Dati un insieme A di n interi positivi e due ...
Leggi Tutto
La grande scienza. Combinatoria
Peter J. Cameron
Combinatoria
Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri essa non rappresenta una branca separata, [...] importante per la combinatoria perché è noto che molti problemi intrattabili (tra cui quello dell'esistenza di un ciclohamiltoniano in un grafo) sono in NP. Nel caso - improbabile - di una soluzione positiva, vi sarebbero algoritmi 'veloci' per ...
Leggi Tutto
Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] in campi diversi. Ne citiamo qui tre di particolare importanza:
Problema del ciclohamiltoniano (Pham). Dato un grafo G di n vertici stabilire se esiste in G un ciclo che attraversa tutti i vertici esattamente una volta.
Problema delle scatole (Psca ...
Leggi Tutto
riduzione polinomiale
Fabrizio Luccio
Nello studio della complessità di algoritmi combinatori l’attenzione è focalizzata sulla classificazione dei problemi come polinomiali o esponenziali. L’esame si [...] se un grafo arbitrario G contiene un percorso chiuso che attraversa esattamente una volta tutti gli spigoli (ciclo euleriano) o tutti i vertici (ciclohamiltoniano). Si definiscono la classe P come quella di tutti i problemi per i quali la decisione ...
Leggi Tutto
HamiltonHamilton William Rowan (Dublino 1805-65) matematico, fisico e astronomo irlandese. Ha dato numerosi contributi in ottica geometrica, in meccanica (riformulando in termini generali le leggi della [...] a cui maggiormente deve la sua fama. Al suo nome è anche legata l’introduzione del cammino hamiltoniano (→ cammino) e del → ciclohamiltoniano, concetti che si rivelano utili in alcuni problemi di teoria dei grafi. Divenuto professore di astronomia a ...
Leggi Tutto
complessita computazionale
complessità computazionale o complessità di calcolo, teoria che, nell’ambito della teoria della computazione, analizza le risorse (quali il tempo e la memoria) necessarie per [...] avente le proprietà richieste. Non si conosce, per esempio, nel caso generale se il problema della ricerca di un ciclohamiltoniano su un grafo sia risolubile in tempo polinomiale; se tuttavia si è in possesso di un certificato K che specifichi ...
Leggi Tutto