Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, [...] , che ha dato luogo a risultati e congetture interessanti, compreso un criterio che stabilisce condizioni in base alle quali un grafo si possa immergere in R3 senza che mai due circuiti siano intrecciati.
Teoria dei disegni
In tale campo di ricerca ...
Leggi Tutto
Kuratowski Kazimierz
Kuratowski 〈kuratòfski〉 Kazimierz [STF] (Varsavia 1896 - ivi 1980) Prof. di matematica nell'univ. di Varsavia (1934); socio straniero dei Lincei (1971). ◆ [ALG] Lemma di K.: qualsiasi [...] sottoinsieme linearmente ordinato di un insieme parzialmente ordinato è contenuto nel più grande dei sottoinsiemi linearmente ordinati. ◆ [ALG] Teorema di K.: → grafo. ...
Leggi Tutto
complessita computazionale
complessità computazionale o complessità di calcolo, teoria che, nell’ambito della teoria della computazione, analizza le risorse (quali il tempo e la memoria) necessarie per [...] forma di riconoscimento R, se la risposta a P può essere solo «sì» o «no». La forma di riconoscimento dell’esempio precedente è: dato un grafo G(X, A, p) orientato e pesato sugli archi con pesi p non negativi, due nodi u e v, un numero k ∈ N, esiste ...
Leggi Tutto
stato
stato elemento descrittore di un processo che muta in modo discreto; a ogni suo mutamento, che avviene per “passi” successivi, lo stato descrive i valori delle variabili coinvolte e l’intero processo [...] stati e delle possibili transizioni da uno stato al successivo (o a uno dei successivi) è generalmente fatta attraverso un grafo degli stati che esprime ex ante l’evoluzione del processo. Se invece il processo evolve in modo caotico non esiste una ...
Leggi Tutto
ponti di Konigsberg, problema dei
ponti di Königsberg, problema dei storico problema che la tradizione vuole legato alla città di Königsberg della Prussia orientale (oggi Kaliningrad, in Russia), nota [...] in modo da ritornare infine al punto di partenza; in pratica si effettua un percorso che è un → ciclo euleriano;
• se il grafo contiene nodi di ordine pari ma soltanto due nodi collegati con un numero dispari di archi (nodi di ordine dispari) esso è ...
Leggi Tutto
calcolo molecolare
càlcolo molecolare locuz. sost. m. – Area scientifica, in rapida evoluzione, nella quale la tecnologia elettronica si fonda sull'uso di DNA, biochimica e biologia molecolare, al posto [...] tramite opportune reazioni biochimiche, si riesce a descrivere, con modalità statistiche, l’insieme di tutti i cammini nel grafo. Utilizzando strumenti biochimici, Adleman è stato in grado di estrarre dai filamenti del DNA che descrivevano l’insieme ...
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
automa a programma
automa a programma automa universale che opera secondo un programma di calcolo, cioè secondo una successione di istruzioni espresse in un linguaggio di programmazione. Il suo operare, [...] macchina di → Turing, non avviene perciò sulla base di una matrice che ne indica tutte le transizioni (o di un grafo di transizione), ma su una base di istruzioni che indicano all’automa quali transizioni selezionare tra quelle possibili e in quale ...
Leggi Tutto
random network
Armando Magrelli
Modelli matematici ipotizzati nel tentativo di comprendere le regole che governano le reti cellulari e le interazioni fra i nodi in esse individuati. Fra questi il modello [...] per la spiegazione di alcuni eventi. Un sistema di elementi interagenti può essere rappresentato da un oggetto matematico chiamato grafo con nodi o vertici, e con connessioni fra di essi (legami) così da costituire una rete (network). In matematica ...
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...