genere
genere in geometria, numero naturale collegato a determinate proprietà analitiche e topologiche di una curva o di una superficie, invariante per alcune trasformazioni. In particolare, il genere [...] il numero minimo di «manici» da aggiungere al piano per potervi immergere il grafo senza che gli archi del grafo si sovrappongano. In base a tale definizione un grafo planare ha genere 0. Un grafo con n nodi, completo (tale cioè che ogni suo nodo sia ...
Leggi Tutto
Sono chiamati suffissoidi gli ➔ elementi formativi usati prevalentemente o esclusivamente come costituenti finali di composto (➔ suffissi), le cui caratteristiche si avvicinano a quelle dei suffissi della [...] si è sviluppato un significato secondario di «repertorio, elenco» (per es., filmografia). Con il significato di «rappresentazione grafica», -grafia forma numerosi composti in cui il primo costituente può indicare il mezzo o il modo con cui avviene ...
Leggi Tutto
Königsberg Nome fino al 1946 della città capoluogo della Prussia Orientale, poi annessa all’URSS e chiamata Kaliningrad.
La disposizione di 7 ponti esistenti a K. sui due rami confluenti del Pregel diede [...] a uno dei primi problemi di topologia (L. Eulero, 1736), il problema dei sette ponti di K. e cioè determinare una via che li attraversi tutti percorrendo ciascuno di essi una volta sola; fu poi dimostrato che il problema non ha soluzione (➔ grafo). ...
Leggi Tutto
dati, struttura di
dati, struttura di modalità di organizzazione delle informazioni all’interno di un insieme di dati. Un tipico esempio elementare di struttura di dati è costituito da un dizionario, [...] questo tipo di dato si effettua utilizzando puntatori, cioè celle di memoria che contengono l’indirizzo del successivo nodo del grafo. Un file in cui sia stato memorizzato un programma è una struttura lineare, così come un brano musicale registrato ...
Leggi Tutto
nodo
nodo termine che assume diversi significati a seconda del contesto.
□ In geometria è un punto doppio di una curva algebrica nel quale la curva ha due tangenti distinte; se la curva ha equazioni [...] : nodo ordinario, tacnodo, oscnodo, flecnodo, biflecnodo ecc.(→ curva, nodo di una).
☐ In teoria dei grafi è così detto ognuno dei vertici di un grafo (→ grafo, nodo di un).
☐ Nelle applicazioni fisiche, è detto nodo ogni punto in cui un sistema di ...
Leggi Tutto
scheduling informatica La gestione dei processi in attesa di esecuzione su un calcolatore a opera di un componente del sistema operativo (➔ operativo, sistema), detto scheduler. Questo rende possibile [...] determinate le date di inizio e fine delle attività di progetto (➔ progettazione), in precedenza definite, in base alla loro durata, alla logica del reticolo (➔ grafo), ai vincoli temporali, alla disponibilità di risorse e ai calendari lavorativi. ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] il quale Andrew V. Goldberg e lo stesso Tarjan hanno proposto nel 1988 una soluzione di costo O(nmlog(n2/m)) per grafi con n nodi ed m archi, trent'anni dopo il classico (ma inefficiente) algoritmo di Ford e Fulkerson (1956).
I risultati riguardanti ...
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 [...] propone di stabilire se il dato d’ingresso ha o meno una determinata proprietà, ovvero costituisce o meno una soluzione. Trattando, per es., di grafi i due problemi decisionali del ciclo euleriano e del ciclo hamiltoniano chiedono di stabilire se un ...
Leggi Tutto
rete
réte s. f. – Termine figurativo con cui si descrive tanto un'infrastruttura fisica e l’insieme dei centri presenti in un sistema, quanto una struttura di interazione che viene rappresentata da una [...] orientamento, tutte misurabili con l’applicazione della teoria dei grafi. Con questo modello è possibile acquisire elementi più linee o segmenti che collegano i punti più distanti (diametro del grafo), il rapporto tra il numero di segmenti e di nodi ...
Leggi Tutto
Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori [...] del DNA per risolvere efficientemente un'istanza del complesso problema teorico della ricerca di un cammino hamiltoniano in un grafo orientato, problema che è NP-completo e quindi ritenuto di difficile soluzione nei modelli di c. e nelle architetture ...
Leggi Tutto
grafo-
[dal tema del gr. γράϕω «scrivere»]. – Primo elemento compositivo di parole dotte e scientifiche, formate modernamente, che significa «scrivere, scrittura», e più raram. «che scrive, che registra», e sim.
-grafo
[dal gr. -γράϕος con sign. attivo, -γραϕος con sign. passivo]. – Secondo elemento, atono, di parole composte derivate dal greco o formate modernamente, usato: 1. Con valore attivo, per indicare: a. Chi si dedica alla descrizione, alla...