Indice
41 relazioni: Accoppiamento (teoria dei grafi), Acta Mathematica, Algoritmo di approssimazione, American Mathematical Monthly, Automorfismo, Cammino hamiltoniano, Classi di complessità P e NP, Colorazione dei grafi, Complessità temporale, Complesso di celle, Controesempio, Dodecaedro, Eulero, Grafo, Grafo aleatorio, Grafo bipartito, Grafo completo, Grafo di Frucht, Grafo di Heawood, Grafo di Petersen, Grafo poliedrico, Handshake (matematica), Insieme indipendente (teoria dei grafi), Journal of Combinatorial Theory, Matematica, Notazione LCF, NP-difficile, Peter Guthrie Tait, Poliedro, Ponte (teoria dei grafi), Problema dei servizi, Problema del commesso viaggiatore, Problema di copertura dei vertici, Programmazione dinamica, Raffigurazione di un grafo, Snark (teoria dei grafi), Taglio massimo, Teoria dei grafi, Topologia, Vertice (teoria dei grafi), William Thomas Tutte.
- Famiglie di grafi
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 archi senza vertici comuni.
Vedere Grafo cubico e Accoppiamento (teoria dei grafi)
Acta Mathematica
Acta Mathematica è una rivista scientifica a revisione paritaria fondata nel 1882 a Stoccolma dal matematico svedese Gösta Mittag-Leffler. È un trimestrale che pubblica articoli di ricerca sulla matematica, disponibile sia in formato cartaceo che digitale di proprietà dell'Institut Mittag-Leffler di Djursholm, dipendente dall'Accademia reale svedese delle scienze.
Vedere Grafo cubico e Acta Mathematica
Algoritmo di approssimazione
Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione.
Vedere Grafo cubico e Algoritmo di approssimazione
American Mathematical Monthly
L'American Mathematical Monthly è una rivista di matematica fondata da Benjamin Finkel nel 1894, attualmente pubblicata 10 volte all'anno dalla Mathematical Association of America.
Vedere Grafo cubico e American Mathematical Monthly
Automorfismo
In matematica, un automorfismo è un isomorfismo di un oggetto matematico in sé stesso. È, in un certo senso, una simmetria dell'oggetto, e un modo di mappare l'oggetto in sé stesso preservando tutte le sue strutture caratteristiche.
Vedere Grafo cubico e Automorfismo
Cammino hamiltoniano
Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta.
Vedere Grafo cubico e Cammino hamiltoniano
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale. Nonostante ci sia in palio un premio di un milione di dollari il problema rimane ancora senza una soluzione (si tratta di uno dei problemi del millennio).
Vedere Grafo cubico e Classi di complessità P e NP
Colorazione dei grafi
Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di etichettamento dei grafi; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli.
Vedere Grafo cubico e Colorazione dei grafi
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.
Vedere Grafo cubico e Complessità temporale
Complesso di celle
In topologia un complesso di celle è un tipo di spazio topologico costruito fondendo insieme certi blocchi basilari chiamati celle. La nozione di complesso di celle è stata introdotta da J. H. C. Whitehead per sopperire ad alcune necessità della teoria dell'omotopia.
Vedere Grafo cubico e Complesso di celle
Controesempio
In logica, e più in generale in matematica un controesempio è un fatto particolare che dimostra che una certa congettura generale è falsa. Costruire esplicitamente un controesempio è il metodo più naturale ed efficace per confutare dei teoremi.
Vedere Grafo cubico e Controesempio
Dodecaedro
In geometria solida il dodecaedro è un poliedro con dodici facce. Generalmente con questo termine si intende però il dodecaedro regolare: nel dodecaedro regolare le facce sono pentagoni regolari che si incontrano in ogni vertice a gruppi di tre.
Vedere Grafo cubico e Dodecaedro
Eulero
È considerato il più importante matematico del Settecento, e uno dei massimi della storia. È noto per essere tra i più prolifici di tutti i tempi e ha fornito contributi storicamente cruciali in svariate aree: analisi infinitesimale, funzioni speciali, meccanica razionale, meccanica celeste, teoria dei numeri, teoria dei grafi.
Vedere Grafo cubico e Eulero
Grafo
I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce un'importante parte della combinatoria; i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi, funzioni speciali, geometria dei poliedri, algebre di Lie.
Vedere Grafo cubico e Grafo
Grafo aleatorio
In teoria dei grafi un grafo aleatorio è un grafo generato da un procedimento aleatorio, ovvero è una variabile aleatoria le cui realizzazioni sono dei grafi.
Vedere Grafo cubico e Grafo aleatorio
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.
Vedere Grafo cubico e Grafo bipartito
Grafo completo
Nella teoria dei grafi un grafo completo è un grafo semplice nel quale ogni vertice è collegato direttamente a tutti i vertici rimanenti. I grafi completi con n vertici sono tutti isomorfi.
Vedere Grafo cubico e Grafo completo
Grafo di Frucht
Il grafo di Frucht è un grafo 3-regolare con 12 vertici e 18 archi descritto per la prima volta da Robert Frucht nel 1939. Il grafo di Frucht è un grafo planare hamiltoniano con numero cromatico 3.
Vedere Grafo cubico e Grafo di Frucht
Grafo di Heawood
Il grafo di Heawood. Nel campo matematico della teoria dei grafi, il grafo di Heawood è un grafo non orientato con 14 vertici e 21 spigoli, che prende nome da Percy John Heawood.
Vedere Grafo cubico e Grafo di Heawood
Grafo di Petersen
Nel campo matematico della teoria dei grafi, il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli. È un piccolo grafo che serve come utile esempio e controesempio per molti problemi di teoria dei grafi.
Vedere Grafo cubico e Grafo di Petersen
Grafo poliedrico
Nell'ambito della teoria dei grafi, un grafo poliedrico è un grafo non orientato formato dai vertici e dagli spigoli di un poligono convesso.
Vedere Grafo cubico e Grafo poliedrico
Handshake (matematica)
Nella teoria dei grafi il lemma di handshaking è l'affermazione che ogni grafo non orientato finito ha un numero pari di vertici con grado dispari (il numero di archi che toccano il vertice).
Vedere Grafo cubico e Handshake (matematica)
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.
Vedere Grafo cubico e Insieme indipendente (teoria dei grafi)
Journal of Combinatorial Theory
Il Journal of Combinatorial Theory è l'insieme di due riviste accademiche inglesi di matematica combinatoria, pubblicate mensilmente dalla casa editrice Elsevier in formato cartaceo ed elettronico.
Vedere Grafo cubico e Journal of Combinatorial Theory
Matematica
La matematica (dal greco: μάθημα (máthema), traducibile con i termini "scienza", "conoscenza" o "apprendimento"; μαθηματικός (mathematikós) significa "incline ad apprendere") è la disciplina che studia le quantità, i numeri, lo spazio,.
Vedere Grafo cubico e Matematica
Notazione LCF
In matematica combinatoria, la notazione LCF o codice LCF è una notazione ideata da Joshua Lederberg ed estesa da Coxeter e Frucht, per la rappresentazione dei grafi cubici che sono hamiltoniani.
Vedere Grafo cubico e Notazione LCF
NP-difficile
In teoria della complessità, i problemi NP-difficili o NP-ardui (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.
Vedere Grafo cubico e NP-difficile
Peter Guthrie Tait
Nato in Scozia, insegnò scienze matematiche a Belfast e fisica ad Edimburgo. Autore, in collaborazione con Lord Kelvin il Treatise of natural philosophy che, sebbene incompiuto, costituisce un lavoro fondamentale per l'esposizione della fisica matematica.
Vedere Grafo cubico e Peter Guthrie Tait
Poliedro
In matematica, e in particolare in geometria solida e in teoria dei grafi, un poliedro è un solido delimitato da un numero finito di facce piane poligonali.
Vedere Grafo cubico e Poliedro
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.
Vedere Grafo cubico e Ponte (teoria dei grafi)
Problema dei servizi
In topologia e teoria dei grafi, il problema dei servizi affronta questioni che si richiamano al classico quesito: Apparentemente di immediata soluzione, il problema delle tre case e dei tre pozzi fa sorridere gli ingenui, ma fa pensare i matematici.
Vedere Grafo cubico e Problema dei servizi
Problema del commesso viaggiatore
Il problema del commesso viaggiatore è il più semplice fra i problemi di instradamento e di gestione dei processi. Viene spesso indicato con il suo nome inglese, traveling salesman problem o traveling salesperson problem, in acronimo TSP.
Vedere Grafo cubico e Problema del commesso viaggiatore
Problema di copertura dei vertici
Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei più difficili problemi risolvibili non-deterministicamente in tempo polinomiale, assieme al problema del commesso viaggiatore, il knapsack problem, ecc.
Vedere Grafo cubico e Problema di copertura dei vertici
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.
Vedere Grafo cubico e Programmazione dinamica
Raffigurazione di un grafo
La raffigurazione dei grafi, o tracciamento dei grafi, è una disciplina che si colloca tra la teoria dei grafi e l'informatica, che si occupa della rappresentazione dei grafi in due o tre dimensioni.
Vedere Grafo cubico e Raffigurazione di un grafo
Snark (teoria dei grafi)
Lo snark a fiore J5 è uno dei 6 snark con 20 vertici. Nel campo matematico della teoria dei grafi, uno snark è un grafo cubico connesso, privo di ponti, con indice cromatico uguale a 4.
Vedere Grafo cubico e Snark (teoria dei grafi)
Taglio massimo
In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut.
Vedere Grafo cubico e Taglio massimo
Teoria dei grafi
In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare una grande varietà di situazioni e processi, e spesso di consentirne delle analisi in termini quantitativi e algoritmici.
Vedere Grafo cubico e Teoria dei grafi
Topologia
La topologia (dal greco τόπος, tópos, "luogo", e λόγος, lógos, "studio", col significato quindi di "studio dei luoghi") è una branca della matematica che studia le proprietà delle figure e, in generale, degli oggetti matematici, che non cambiano quando viene effettuata una deformazione senza "strappi", "sovrapposizioni" o "incollature".
Vedere Grafo cubico e Topologia
Vertice (teoria dei grafi)
Nella teoria dei grafi, un vertice o nodo è l'unità fondamentale di cui i grafi sono costituiti: un grafo consiste in un insieme di vertici e di archi (coppie di vertici, ordinate se diretto, non ordinate altrimenti).
Vedere Grafo cubico e Vertice (teoria dei grafi)
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.
Vedere Grafo cubico e William Thomas Tutte
Vedi anche
Famiglie di grafi
- Densità di un grafo
- Grafo bipartito
- Grafo cordale
- Grafo cubico
- Grafo delle implicazioni
- Grafo di Cayley
- Grafo planare
- Grafo regolare
- Rete a invarianza di scala
- Snark (teoria dei grafi)