l'accesso più veloce di browser!
72 relazioni: Accoppiamento (teoria dei grafi), Albero (grafo), Alfred Bray Kempe, Algoritmo di approssimazione, Algoritmo greedy, Arthur Cayley, Assioma della scelta, Augustus De Morgan, Branch and bound, Calibro (teoria dei grafi), Caratteristica di Eulero, Classi di complessità P e NP, Claude Shannon, Colorazione golosa, Communications of the ACM, Compilatore, Complessità temporale, Contrazione degli spigoli, Cricca (teoria dei grafi), George David Birkhoff, Glossario di teoria dei grafi, Grafo, Grafo bipartito, Grafo ciclo, Grafo completo, Grafo cubico, Grafo d'intervallo, Grafo di Petersen, Grafo duale, Grafo nullo, Grafo perfetto, Grafo planare, Insieme indipendente (teoria dei grafi), Introduzione agli algoritmi, Isomorfismo, Kenneth Appel, Larghezza di banda, Lingua inglese, Linguaggio di programmazione, Logaritmo iterato, London Mathematical Society, Metodo forza bruta, NP (complessità), NP-completo, NP-difficile, P (complessità), Paul Seymour (matematico), Polinomio, Polinomio cromatico, Ponte (teoria dei grafi), ..., Principio di inclusione-esclusione, Programma (informatica), Programmazione dinamica, Registro (informatica), Relazione di ricorrenza, Ricerca in ampiezza, Royal Society, RP (complessità), Sharp-P-completo, Springer (azienda), Successione di Fibonacci, Sudoku, Teorema dei cinque colori, Teorema dei quattro colori, Teoria dei grafi, Teoria dell'informazione, Teoria di Ramsey, University College (Londra), William Rowan Hamilton, William Thomas Tutte, Wolfgang Haken, 21 problemi NP-completi di Karp. Espandi índice (22 più) »
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!!: Colorazione dei grafi e Accoppiamento (teoria dei grafi) · Mostra di più »
Albero (grafo)
In teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino (grafo non orientato, connesso e privo di cicli).
Nuovo!!: Colorazione dei grafi e Albero (grafo) · Mostra di più »
Alfred Bray Kempe
Nessuna descrizione.
Nuovo!!: Colorazione dei grafi e Alfred Bray Kempe · 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!!: Colorazione dei grafi e Algoritmo di approssimazione · Mostra di più »
Algoritmo greedy
Un algoritmo greedy è un algoritmo che cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa (aggressiva o avida, a seconda della traduzione preferita del termine greedy dall'inglese) ad ogni passo locale.
Nuovo!!: Colorazione dei grafi e Algoritmo greedy · Mostra di più »
Arthur Cayley
Cayley fu tra i matematici più prolifici del XIX secolo.
Nuovo!!: Colorazione dei grafi e Arthur Cayley · Mostra di più »
Assioma della scelta
L'assioma della scelta è un assioma di teoria degli insiemi enunciato per la prima volta da Ernst Zermelo nel 1904.
Nuovo!!: Colorazione dei grafi e Assioma della scelta · Mostra di più »
Augustus De Morgan
A lui si devono i teoremi di De Morgan che sono alla base dei sistemi logici elettronici ed informatici.
Nuovo!!: Colorazione dei grafi e Augustus De Morgan · Mostra di più »
Branch and bound
Il branch and bound è una tecnica generale per la risoluzione di problemi di ottimizzazione combinatoria (cioè problemi con spazio di soluzioni finito) e si basa sulla scomposizione del problema originale in sottoproblemi più semplici da risolvere.
Nuovo!!: Colorazione dei grafi e Branch and bound · Mostra di più »
Calibro (teoria dei grafi)
Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo.
Nuovo!!: Colorazione dei grafi e Calibro (teoria dei grafi) · Mostra di più »
Caratteristica di Eulero
In matematica, e più precisamente in geometria e topologia, la caratteristica di Eulero è un numero intero che descrive alcuni aspetti della forma di uno spazio topologico.
Nuovo!!: Colorazione dei grafi e Caratteristica di Eulero · Mostra di più »
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.
Nuovo!!: Colorazione dei grafi e Classi di complessità P e NP · Mostra di più »
Claude Shannon
Claude Shannon, lontano parente di Thomas Edison, nacque a Petoskey, una piccola città del Michigan.
Nuovo!!: Colorazione dei grafi e Claude Shannon · Mostra di più »
Colorazione golosa
Due colorazioni golose dello stesso grafo che usano ordini diversi dei vertici. L'esempio di destra generalizza ai grafi 2-colorabili con ''n'' vertici, dove l'algoritmo goloso spende n/2 colori. Nello studio dei problemi della colorazione dei grafi in matematica e in informatica, una colorazione golosa (in inglese greedy coloring) è una colorazione dei vertici di un grafo formata da un algoritmo goloso (greedy algorithm) che considera i vertici del grafo in sequenza e assegna a ciascun vertice il suo primo colore disponibile.
Nuovo!!: Colorazione dei grafi e Colorazione golosa · Mostra di più »
Communications of the ACM
Communications of the ACM (CACM) è una delle maggiori riviste mensili dell'Association for Computing Machinery.
Nuovo!!: Colorazione dei grafi e Communications of the ACM · Mostra di più »
Compilatore
Un compilatore è un programma informatico che traduce una serie di istruzioni scritte in un determinato linguaggio di programmazione (codice sorgente) in istruzioni di un altro linguaggio (codice oggetto).
Nuovo!!: Colorazione dei grafi e Compilatore · Mostra di più »
Complessità temporale
In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.
Nuovo!!: Colorazione dei grafi e Complessità temporale · Mostra di più »
Contrazione degli spigoli
right Nella teoria dei grafi, una contrazione dei grafi è un'operazione che rimuove uno spigolo da un grafo mentre fonde simultaneamente i due vertici che connetteva in precedenza.
Nuovo!!: Colorazione dei grafi e Contrazione degli spigoli · Mostra di più »
Cricca (teoria dei grafi)
In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega.
Nuovo!!: Colorazione dei grafi e Cricca (teoria dei grafi) · Mostra di più »
George David Birkhoff
Birkhoff fu uno dei matematici statunitensi più influenti della sua generazione e nel periodo di maggiore attività fu considerato da molti il matematico americano preminente.
Nuovo!!: Colorazione dei grafi e George David Birkhoff · Mostra di più »
Glossario di teoria dei grafi
Un grafo G è una coppia (V, E) dove V è un insieme e E ⊆ V × V è un sottoinsieme del prodotto cartesiano di V per se stesso.
Nuovo!!: Colorazione dei grafi e Glossario di teoria dei grafi · 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!!: Colorazione dei grafi 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!!: Colorazione dei grafi e Grafo bipartito · Mostra di più »
Grafo ciclo
Nella teoria dei grafi, un grafo ciclo o grafo circolare è un grafo che consiste di un unico ciclo o, in altre parole, di un certo numero di vertici connessi in una catena chiusa.
Nuovo!!: Colorazione dei grafi e Grafo ciclo · Mostra di più »
Grafo completo
Nella teoria dei grafi un grafo completo è un grafo semplice nel quale ogni vertice è collegato a tutti i vertici rimanenti.
Nuovo!!: Colorazione dei grafi e Grafo completo · 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!!: Colorazione dei grafi e Grafo cubico · Mostra di più »
Grafo d'intervallo
Sette intervalli sulla linea reale e il corrispondente grafo d'intervallo a sette vertici. Nella teoria dei grafi, un grafo d'intervallo è il grafo d'intersezione di un multiinsieme di intervalli sulla linea reale.
Nuovo!!: Colorazione dei grafi e Grafo d'intervallo · Mostra di più »
Grafo di Petersen
Il grafo di Petersen è disegnato più comunemente come un pentagono con un pentragramma all'interno, con cinque raggi. Nel campo matematico della teoria dei grafi, il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli.
Nuovo!!: Colorazione dei grafi e Grafo di Petersen · Mostra di più »
Grafo duale
Nella teoria dei grafi il grafo duale di un grafo planare (o in generale di un grafo raffigurato su una varietà) G è un nuovo grafo G′ che ha un nodo per ogni regione di G ed un arco per ogni arco di G (due nodi di G′ sono connessi da un arco se e solo se le due corrispondenti regioni di G sono separate da un arco).
Nuovo!!: Colorazione dei grafi e Grafo duale · Mostra di più »
Grafo nullo
Nel campo matematico della teoria dei grafi, il grafo nullo può riferirsi o al grafo di ordine-zero o, alternativamente, a qualunque grafo privo di ponti (quest'ultimo è chiamato a volte grafo vuoto).
Nuovo!!: Colorazione dei grafi e Grafo nullo · Mostra di più »
Grafo perfetto
Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo.
Nuovo!!: Colorazione dei grafi e Grafo perfetto · 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!!: Colorazione dei grafi e Grafo planare · 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!!: Colorazione dei grafi 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!!: Colorazione dei grafi e Introduzione agli algoritmi · Mostra di più »
Isomorfismo
In matematica, in particolare in algebra astratta, un isomorfismo (dal greco ἴσος, isos, che significa uguale, e μορφή, morphé, che significa forma) è un'applicazione biunivoca fra oggetti matematici tale che l'applicazione e la sua inversa siano omomorfismi.
Nuovo!!: Colorazione dei grafi e Isomorfismo · Mostra di più »
Kenneth Appel
Nessuna descrizione.
Nuovo!!: Colorazione dei grafi e Kenneth Appel · Mostra di più »
Larghezza di banda
In telecomunicazioni ed elettronica la larghezza di banda è la misura dell'ampiezza di banda dello spettro di un segnale informativo trasmesso dalla banda passante disponibile o utilizzata in un canale di comunicazione oppure, la banda di lavoro di un certo sistema fisico in relazione alla sua risposta in frequenza.
Nuovo!!: Colorazione dei grafi e Larghezza di banda · 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!!: Colorazione dei grafi e Lingua inglese · Mostra di più »
Linguaggio di programmazione
Un linguaggio di programmazione, in informatica, è un linguaggio formale che specifica un insieme di istruzioni che possono essere usate per produrre dati in output.
Nuovo!!: Colorazione dei grafi e Linguaggio di programmazione · Mostra di più »
Logaritmo iterato
In informatica, il logaritmo iterato di n, scritto log* n (solitamente letto "log asterisco"), è il numero di volte che la funzione logaritmo deve essere applicata iterativamente prima che il risultato sia minore o uguale a 1.
Nuovo!!: Colorazione dei grafi e Logaritmo iterato · Mostra di più »
London Mathematical Society
La Società Matematica di Londra (London Mathematical Society, sigla LMS) è uno dei circoli culturali del Regno Unito per la matematica (gli altri sono la Royal Statistical Society (RSS) e l'Istituto di Matematica e delle sue Applicazioni (IMA)).
Nuovo!!: Colorazione dei grafi e London Mathematical Society · 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!!: Colorazione dei grafi e Metodo forza bruta · Mostra di più »
NP (complessità)
La classe di problemi NP comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale.
Nuovo!!: Colorazione dei grafi e NP (complessità) · 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!!: Colorazione dei grafi e NP-completo · Mostra di più »
NP-difficile
In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP.
Nuovo!!: Colorazione dei grafi e NP-difficile · 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!!: Colorazione dei grafi e P (complessità) · Mostra di più »
Paul Seymour (matematico)
Nessuna descrizione.
Nuovo!!: Colorazione dei grafi e Paul Seymour (matematico) · Mostra di più »
Polinomio
In matematica un polinomio è un'espressione composta da costanti e variabili combinate usando soltanto addizione, sottrazione e moltiplicazione.
Nuovo!!: Colorazione dei grafi e Polinomio · Mostra di più »
Polinomio cromatico
Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica.
Nuovo!!: Colorazione dei grafi e Polinomio cromatico · Mostra di più »
Ponte (teoria dei grafi)
Un grafo con 6 ponti (marcati in rosso) Un grafo non orientato senza ponti Nella teoria dei grafi, un ponte (conosciuto anche come bridge, cut-edge, cut arc o istmo) è un arco la cui eliminazione aumenta il numero di componenti connesse.
Nuovo!!: Colorazione dei grafi e Ponte (teoria dei grafi) · Mostra di più »
Principio di inclusione-esclusione
In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi.
Nuovo!!: Colorazione dei grafi e Principio di inclusione-esclusione · Mostra di più »
Programma (informatica)
Un programma, in informatica,è un software che può essere eseguito da un elaboratore per ricevere in input determinati dati di un problema automatizzabile e restituirne in output le (eventuali) soluzioni.
Nuovo!!: Colorazione dei grafi e Programma (informatica) · Mostra di più »
Programmazione dinamica
In Informatica la programmazione dinamica è una tecnica di progettazione di algoritmi basata sulla divisione del problema in sottoproblemi e sull'utilizzo di sottostrutture ottimali.
Nuovo!!: Colorazione dei grafi e Programmazione dinamica · Mostra di più »
Registro (informatica)
Nell'architettura dei calcolatori un registro (o registro del processore) è una piccola parte di memoria utilizzata per velocizzare l'esecuzione dei programmi fornendo un accesso rapido ai valori usati più frequentemente — tipicamente, i valori correntemente in uso in una determinata parte di un calcolo.
Nuovo!!: Colorazione dei grafi e Registro (informatica) · Mostra di più »
Relazione di ricorrenza
In matematica, una relazione di ricorrenza, chiamata anche equazione di ricorrenza, è un'equazione che, nei casi più semplici, riguarda i componenti di una successione la quale stabilisce un legame tra alcuni componenti che occupano posizioni generiche, ma successive, cioè presenta una forma del tipo: Il numero k viene detto ordine della relazione.
Nuovo!!: Colorazione dei grafi e Relazione di ricorrenza · Mostra di più »
Ricerca in ampiezza
Nella teoria dei grafi, la ricerca in ampiezza (in inglese breadth-first search, BFS) è un algoritmo di ricerca per grafi che partendo da un vertice (o nodo) detto sorgente permette di cercare il cammino fino ad un altro nodo scelto e connesso al nodo sorgente.
Nuovo!!: Colorazione dei grafi e Ricerca in ampiezza · Mostra di più »
Royal Society
La Royal Society – formalmente The President, Council, and Fellows of the Royal Society of London for Improving Natural Knowledge ("Il presidente, il consiglio e i membri della Reale Società londinese per lo sviluppo della conoscenza naturale") – è un'associazione scientifica britannica, fondata il 28 novembre 1660 per iniziativa di John Evelyn e altri accademici allo scopo di promuovere l'eccellenza scientifica come viatico per il benessere della società; altri membri fondatori furono Christopher Wren, Robert Boyle, John Wilkins e William Brouncker.
Nuovo!!: Colorazione dei grafi e Royal Society · Mostra di più »
RP (complessità)
Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica.
Nuovo!!: Colorazione dei grafi e RP (complessità) · Mostra di più »
Sharp-P-completo
#P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale.
Nuovo!!: Colorazione dei grafi e Sharp-P-completo · Mostra di più »
Springer (azienda)
Springer Science+Business Media è un gruppo editoriale con sedi a Berlino, Heidelberg, negli Stati Uniti e nei Paesi Bassi.
Nuovo!!: Colorazione dei grafi e Springer (azienda) · Mostra di più »
Successione di Fibonacci
La successione di Fibonacci (detta anche successione aurea), indicata con F_n o con Fib(n), in matematica indica una successione di numeri interi positivi in cui ciascun numero a cominciare dal terzo è la somma dei due precedenti, dove i primi due sono (per definizione) F_1.
Nuovo!!: Colorazione dei grafi e Successione di Fibonacci · Mostra di più »
Sudoku
Il sudoku (giapponese: 数独, sūdoku, nome completo 数字は独身に限る Sūji wa dokushin ni kagiru, che in italiano vuol dire "sono consentiti solo numeri solitari") è un gioco di logica nel quale al giocatore o solutore viene proposta una griglia di 9×9 celle, ciascuna delle quali può contenere un numero da 1 a 9, oppure essere vuota; la griglia è suddivisa in 9 righe orizzontali, 9 colonne verticali e in 9 "sottogriglie" di 3×3 celle contigue.
Nuovo!!: Colorazione dei grafi e Sudoku · Mostra di più »
Teorema dei cinque colori
Il teorema dei cinque colori è un risultato della teoria dei grafi, che afferma che, dato un piano suddiviso in regioni connesse (come una mappa politica delle regioni di uno Stato), queste possono essere colorate utilizzando non più di cinque colori, in modo tale che non esistono due regioni adiacenti con lo stesso colore.
Nuovo!!: Colorazione dei grafi e Teorema dei cinque colori · Mostra di più »
Teorema dei quattro colori
Esempio di mappa a quattro colori Il teorema dei quattro colori è un teorema di matematica che afferma che data una superficie piana divisa in regioni connesse, come ad esempio una carta geografica politica, sono sufficienti quattro colori per colorare ogni regione facendo in modo che regioni adiacenti non abbiano lo stesso colore.
Nuovo!!: Colorazione dei grafi e Teorema dei quattro colori · Mostra di più »
Teoria dei grafi
In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi si occupa di studiare i grafi, che sono oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentirne delle analisi in termini quantitativi e algoritmici.
Nuovo!!: Colorazione dei grafi e Teoria dei grafi · Mostra di più »
Teoria dell'informazione
La teoria dell'informazione è una disciplina dell'informatica e delle telecomunicazioni il cui oggetto è l'analisi e l'elaborazione su base matematica dei fenomeni relativi alla misurazione e alla trasmissione di informazioni su un canale fisico di comunicazione.
Nuovo!!: Colorazione dei grafi e Teoria dell'informazione · Mostra di più »
Teoria di Ramsey
La teoria di Ramsey, così chiamata dal nome di Frank Plumpton Ramsey, è un ramo della matematica discreta che si occupa di problemi della forma: qual è il minor numero di elementi necessario affinché una certa proprietà sia vera?.
Nuovo!!: Colorazione dei grafi e Teoria di Ramsey · Mostra di più »
University College (Londra)
La University College London, nota anche con la sigla UCL, è una prestigiosa università britannica, con sede a Londra.
Nuovo!!: Colorazione dei grafi e University College (Londra) · Mostra di più »
William Rowan Hamilton
Il suo più grande contributo è forse la riformulazione della meccanica newtoniana sotto forma di meccanica hamiltoniana che è parte della meccanica razionale.
Nuovo!!: Colorazione dei grafi e William Rowan Hamilton · Mostra di più »
William Thomas Tutte
Durante la seconda guerra mondiale egli riuscì a penetrare in uno dei maggiori sistemi di cifratura tedeschi, risultato che ebbe una significativa influenza sullo sbarco nel continente europeo da parte degli Alleati.
Nuovo!!: Colorazione dei grafi e William Thomas Tutte · Mostra di più »
Wolfgang Haken
Nessuna descrizione.
Nuovo!!: Colorazione dei grafi e Wolfgang Haken · Mostra di più »
21 problemi NP-completi di Karp
Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi.
Nuovo!!: Colorazione dei grafi e 21 problemi NP-completi di Karp · Mostra di più »
Riorienta qui:
Numero cromatico, Problema della colorazione dei grafi.
