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
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
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
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
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
La grande scienza. Geometria numerativa e invarianti di Gromov-Witten
Enrico Arbarello
Geometria numerativa e invarianti di Gromov-Witten
Nel trattato Le coniche, Apollonio di Perge (262-180 a.C. circa) [...] vertice pi il suo vertice corrisponde alla componente di C e lo si decora con l'indice i. Nella fig. 13 si illustra il grafo duale della curva disegnata nella fig. 11.
Il genere di una curva stabile C è definito dalla formula
dove C1,…,Cs, sono le ...
Leggi Tutto
Whitney Hassler
Whitney 〈uìtni〉 Hassler [STF] (n. New York 1907) Prof. di matematica nella Harvard Univ. (1946) e di Princeton (1952). ◆ [ALG] Classi di W., o di Stiefel-W.: per una varietà differenziabile [...] classi caratteristiche: I 630 d. ◆ [ANM] Teorema locale di W.: v. analisi non lineare: I 141 c. ◆ [ALG] Teorema di W. sui grafi: due grafi G, G' isomorfi (dal punto di vista della struttura algebrica) sono anche omeomorfi; c'è un'unica eccezione: il ...
Leggi Tutto
Hamilton Sir William Rowan
Hamilton 〈hèmiltën〉 Sir William Rowan [STF] (Dublino 1805 - ivi 1865) Prof. di astronomia nell'univ. di Dublino e astronomo reale d'Irlanda (1827). ◆ [MCC] Condizione di H.-Jacobi: [...] ◆ [ALG] [ANM] Funzione di H.: lo stesso che hamiltoniana (←). ◆ [MCC] Operatore di H.: → hamiltoniano. ◆ [ALG] Linea di H.: per un grafo (←), la linea che passa una sola volta per tutti i vertici di esso. ◆ [MCC] Metodo d'integrazione di H.-Jacobi: v ...
Leggi Tutto
ZAPPA, Guido
Francesco Gherardelli
Matematico, nato a Napoli il 7 dicembre 1915. Laureatosi in matematica presso la Scuola Normale di Pisa, dal 1947 è stato professore di Geometria e di Algebra presso [...] in geometria combinatoria. Notevoli inoltre i contributi giovanili alla geometria algebrica, dove ha introdotto la nozione di grafo duale di una degenerazione di una superficie algebrica e ha studiato sottili esempi di deformazioni di curve su ...
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...