Nel linguaggio scientifico, struttura relazionale formata da un insieme finito di oggetti detti nodi o vertici, e da un insieme di relazioni tra coppie di oggetti dette archi o spigoli. Per indicare un [...] d(i, j). Se k è il nodo centro (o uno dei nodi centrali) del g., il valore R(k) è detto raggio del grafo.
Albero di un grafo
È un g. non orientato connesso e senza cicli (o anche, in modo del tutto equivalente, un g. connesso e senza cicli); un g ...
Leggi Tutto
crittografo
crittògrafo (o criptògrafo) [Comp. di critto- (o cripto-) e -grafo] [INF] Macchina per tradurre un testo dal linguaggio chiaro a quello cifrato e viceversa. ...
Leggi Tutto
teoria dei grafi
Gilberto Bini
Lo studio delle proprietà combinatorie, topologiche, probabilistiche ecc. dei grafi, sviluppatosi come teoria matematica autonoma negli anni Trenta del Novecento a opera [...] percorso che partendo da uno dei vertici attraversi tutti i lati una e una sola volta. Da allora la teoria dei grafi ha subito un sorprendente sviluppo con applicazione a vari settori delle scienze, in particolare i legami con le reti elettriche, le ...
Leggi Tutto
rete di Petri
Mauro Cappelli
Strumento teorico per la modellazione di processi in un sistema distribuito a stati discreti. Proposte nel 1962 da Carl Adam Petri, le reti di Petri rappresentano una teoria [...] a transizioni). In un fissato istante di tempo, lo stato della rete è rappresentato ponendo dei token (marche) nei posti del grafo. La rete evolve da uno stato all’altro: ciò graficamente viene rappresentato assegnando a ogni posto un certo numero di ...
Leggi Tutto
Insieme di linee, reali o ideali, che si intrecciano formando incroci e nodi e dando luogo a una struttura complessa. Più in particolare, infrastruttura tecnica per la distribuzione di un segnale (tipicamente [...] gli archi a condizioni logiche abilitanti l’evento successivo o a transizioni ammissibili tra stati. Fra le r. logiche più diffuse si hanno i grafi and-or, in cui i nodi hanno in genere un solo arco uscente e più archi in ingresso e l’uscita porta un ...
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
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
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] una rete, per il quale A.V. Goldberg e lo stesso Tarjan (1986) hanno proposto una soluzione di costo O(nm log(n²/m)) per grafi con n nodi e m archi, trent'anni dopo il classico (ma inefficiente) algoritmo proposto da L.R. Ford e D.R. Fulkerson (1956 ...
Leggi Tutto
In informatica, testo organizzato in un insieme di moduli elementari (v. +fig.) che ne rende possibile la lettura, integrale o parziale, secondo diversi percorsi logici (ciascuno dotato di autonomia di [...] non sequenziale delle risorse sono i collegamenti (ipertestuali) tra le stesse; l’insieme di tali collegamenti può essere schematizzato da un grafo o rete in cui a ogni nodo viene associato un concetto (un documento) e i collegamenti tra i vari nodi ...
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...