l'accesso più veloce di browser!
26 relazioni: Accoppiamento (teoria dei grafi), Algoritmo di approssimazione, Copertura dei vertici, Grafo, Grafo bipartito, Grafo cubico, Grafo planare, Informatica, Insieme complemento, Insieme indipendente (teoria dei grafi), Introduzione agli algoritmi, Ipergrafo, Lingua inglese, Logistica, Metodo forza bruta, NP-completo, P (complessità), Problema del commesso viaggiatore, Problema della cricca, Problema dello zaino, Relazione di equivalenza, Richard Karp, Ronald Rivest, Soddisfacibilità booleana, Teoria della complessità computazionale, Thomas H. Cormen.
Accoppiamento (teoria dei grafi)
Nella disciplina matematica della teoria dei grafi, un accoppiamento o abbinamento (in inglese matching) o insieme degli spigoli indipendenti in un grafo è un insieme bipartito di spigoli senza vertici comuni.
Nuovo!!: Problema di copertura dei vertici e Accoppiamento (teoria dei grafi) · Mostra di più »
Algoritmo di approssimazione
Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione.
Nuovo!!: Problema di copertura dei vertici e Algoritmo di approssimazione · Mostra di più »
Copertura dei vertici
In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) un sottoinsieme S dei nodi di un grafo G.
Nuovo!!: Problema di copertura dei vertici e Copertura dei vertici · Mostra di più »
Grafo
Grafo (non orientato) con 6 nodi e 5 archi I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi.
Nuovo!!: Problema di copertura dei vertici e Grafo · Mostra di più »
Grafo bipartito
Nella teoria dei grafi, un grafo bipartito è un grafo tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra.
Nuovo!!: Problema di copertura dei vertici e Grafo bipartito · Mostra di più »
Grafo cubico
Il grafo di Petersen è un grafo cubico Il grafo bipartito completo K_3,3 è un esempio di grafo bicubico Nel campo matematico della teoria dei grafi, un grafo cubico è un grafo in cui tutti i vertici hanno grado tre.
Nuovo!!: Problema di copertura dei vertici e Grafo cubico · Mostra di più »
Grafo planare
Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano.
Nuovo!!: Problema di copertura dei vertici e Grafo planare · Mostra di più »
Informatica
L'informatica è la scienza applicata che si occupa del trattamento dell'informazione mediante procedure automatizzate.
Nuovo!!: Problema di copertura dei vertici e Informatica · Mostra di più »
Insieme complemento
Nella teoria degli insiemi e in altri campi della matematica, esistono due tipi di insieme complemento: il complemento relativo (detto anche insieme differenza) e il complemento assoluto.
Nuovo!!: Problema di copertura dei vertici e Insieme complemento · Mostra di più »
Insieme indipendente (teoria dei grafi)
Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due.
Nuovo!!: Problema di copertura dei vertici e Insieme indipendente (teoria dei grafi) · Mostra di più »
Introduzione agli algoritmi
Introduzione agli algoritmi e strutture dati (Introduction to Algorithms) è un libro di Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein.
Nuovo!!: Problema di copertura dei vertici e Introduzione agli algoritmi · Mostra di più »
Ipergrafo
In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici.
Nuovo!!: Problema di copertura dei vertici e Ipergrafo · Mostra di più »
Lingua inglese
L'inglese (nome nativo English) è una lingua indoeuropea appartenente al ramo occidentale delle lingue germaniche, assieme all'olandese, all'alto e basso tedesco, al fiammingo e al frisone.
Nuovo!!: Problema di copertura dei vertici e Lingua inglese · Mostra di più »
Logistica
Esistono diverse definizioni di logistica, ognuna delle quali differisce per l'ampiezza di visione con cui viene considerata questa materia.
Nuovo!!: Problema di copertura dei vertici e Logistica · Mostra di più »
Metodo forza bruta
In informatica il metodo "forza bruta" (anche noto come ricerca esaustiva della soluzione) è un algoritmo di risoluzione di un problema dato che consiste nel verificare tutte le soluzioni teoricamente possibili fino a che si trova quella effettivamente corretta.
Nuovo!!: Problema di copertura dei vertici e Metodo forza bruta · Mostra di più »
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.
Nuovo!!: Problema di copertura dei vertici e NP-completo · Mostra di più »
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Nuovo!!: Problema di copertura dei vertici e P (complessità) · Mostra di più »
Problema del commesso viaggiatore
Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling.
Nuovo!!: Problema di copertura dei vertici e Problema del commesso viaggiatore · Mostra di più »
Problema della cricca
In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.
Nuovo!!: Problema di copertura dei vertici e Problema della cricca · Mostra di più »
Problema dello zaino
In questo caso, la soluzione è di mettere nello zaino tre scatole gialle e tre grigie Il problema dello zaino, detto anche Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente.
Nuovo!!: Problema di copertura dei vertici e Problema dello zaino · Mostra di più »
Relazione di equivalenza
Una relazione di equivalenza è un concetto matematico che esprime in termini formali quello intuitivo di "oggetti che condividono una certa proprietà".
Nuovo!!: Problema di copertura dei vertici e Relazione di equivalenza · Mostra di più »
Richard Karp
Nel 1972 ha pubblicato un elenco di 21 problemi NP-completi.
Nuovo!!: Problema di copertura dei vertici e Richard Karp · Mostra di più »
Ronald Rivest
Il suo lavoro più noto è sicuramente il sistema di crittografia asimmetrica che ha sviluppato assieme a Leonard Adleman e Adi Shamir: il crittosistema RSA (1978).
Nuovo!!: Problema di copertura dei vertici e Ronald Rivest · Mostra di più »
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Nuovo!!: Problema di copertura dei vertici e Soddisfacibilità booleana · Mostra di più »
Teoria della complessità computazionale
In informatica, la teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.
Nuovo!!: Problema di copertura dei vertici e Teoria della complessità computazionale · Mostra di più »
Thomas H. Cormen
Coautore del libro Introduction to Algorithms (Introduzione agli algoritmi), con Charles Leiserson, Ron Rivest, e Cliff Stein, è professore di informatica al Dartmouth College.
Nuovo!!: Problema di copertura dei vertici e Thomas H. Cormen · Mostra di più »
