Indice
19 relazioni: Clique, Coefficiente di clustering, Colorazione dei grafi, Cricca, Grafo complemento, Grafo completo, Grafo cordale, Grafo d'intervallo, Grafo di Turán, Grafo perfetto, Insieme indipendente (teoria dei grafi), Ipotesi del tempo esponenziale, JOELib, Klaus Wagner, L (complessità), Polinomio cromatico, Problema della cricca, Problema di copertura delle cricche, Quadratic pseudo-Boolean optimisation.
Clique
* Clique – serie televisiva britannica del 2017.
Vedere Cricca (teoria dei grafi) e Clique
Coefficiente di clustering
Nella teoria dei grafi, il coefficiente di clustering (o transitività) è la misura del grado in cui i nodi di un grafo tendono ad essere connessi fra loro.
Vedere Cricca (teoria dei grafi) e Coefficiente di clustering
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 Cricca (teoria dei grafi) e Colorazione dei grafi
Cricca
*Cricca – fenditura sottile e profonda in un materiale metallico.
Vedere Cricca (teoria dei grafi) e Cricca
Grafo complemento
Nella teoria dei grafi, il complemento o inverso di un grafo G è un grafo H sugli stessi vertici tale che due distinti vertici di H sono adiacenti se e solo se non sono adiacenti in G. Ossia, per generare il complemento di un grafo, si riempiono tutti gli spigoli mancanti richiesti per formare un grafo completo, e si rimuovono tutti gli spigoli che vi erano in precedenza.
Vedere Cricca (teoria dei grafi) e Grafo complemento
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 Cricca (teoria dei grafi) e Grafo completo
Grafo cordale
Nel campo matematico della teoria dei grafi, un grafo è cordale se ciascuno dei suoi cicli di quattro o più vertici ha una corda, che è uno spigolo che non fa parte del ciclo ma connette due vertici di quest'ultimo.
Vedere Cricca (teoria dei grafi) e Grafo cordale
Grafo d'intervallo
Nella teoria dei grafi, un grafo d'intervallo è il grafo d'intersezione di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice per ciascun intervallo dell'insieme, e uno spigolo tra ogni coppia di vertici corrispondenti agli intervalli che intersecano.
Vedere Cricca (teoria dei grafi) e Grafo d'intervallo
Grafo di Turán
Il grafo di Turán T(n,r) è un grafo formato suddividendo un insieme di n vertici in r sottoinsiemi, con dimensioni più uguali possibili, e connettendo due vertici mediante uno spigolo ogni volta che appartengono a sottoinsiemi diversi.
Vedere Cricca (teoria dei grafi) e Grafo di Turán
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.
Vedere Cricca (teoria dei grafi) e Grafo perfetto
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 Cricca (teoria dei grafi) e Insieme indipendente (teoria dei grafi)
Ipotesi del tempo esponenziale
Nella teoria della complessità computazionale, l'ipotesi del tempo esponenziale è un'assunzione di difficoltà computazionale non dimostrata, formalizzata da, che afferma che 3-SAT (o uno qualsiasi dei vari problemi NP-completi) non possono essere risolti in tempo subesponenziale nel caso peggiore.
Vedere Cricca (teoria dei grafi) e Ipotesi del tempo esponenziale
JOELib
JOELib è un software libero, un sistema esperto chimico usato principalmente per convertire il formato di file chimici. Data la sua forte relazione con l'informatica, questo programma appartiene più alla categoria della chemioinformatica che della modellistica molecolare.
Vedere Cricca (teoria dei grafi) e JOELib
Klaus Wagner
Wagner studiò topologia all'Università di Colonia sotto la direzione di Karl Dorge, che a sua volta era un ex allievo di Issai Schur.
Vedere Cricca (teoria dei grafi) e Klaus Wagner
L (complessità)
Nella teoria della complessità computazionale, L (nota anche come LSPACE, LOGSPACE o DLOGSPACE) è la classe di complessità che contiene i problemi di decisione che possono essere risolti da una macchina di Turing deterministica usando una quantità logaritmica di memoria.
Vedere Cricca (teoria dei grafi) e L (complessità)
Polinomio cromatico
Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica. Esso conta il numero di colorazioni dei grafi come funzione del numero dei colori e fu definito originariamente da George David Birkhoff per affrontare il problema dei quattro colori.
Vedere Cricca (teoria dei grafi) e Polinomio cromatico
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.
Vedere Cricca (teoria dei grafi) e Problema della cricca
Problema di copertura delle cricche
Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP-completo di teoria dei grafi. Il problema era uno dei 21 problemi originali di Richard Karp che erano stati dimostrati NP-completi nel suo saggio del 1972 Riducibilità tra problemi combinatori (Reducibility among Combinatorial Problems).
Vedere Cricca (teoria dei grafi) e Problema di copertura delle cricche
Quadratic pseudo-Boolean optimisation
Quadratic pseudo-Boolean optimisation (QPBO) è un metodo di ottimizzazione discreta di funzioni pseudo-booleane quadratiche non submodulari nella forma nelle variabili binarie x_p in ; forall p in V.
Vedere Cricca (teoria dei grafi) e Quadratic pseudo-Boolean optimisation
Conosciuto come Cricca massima, Cricca massimale.