ⓘ L'enciclopedia libera. Lo sapevi che? pagina 490

Lemma di Sperner

Il lemma di Sperner è un teorema della teoria dei grafi che ha delle importanti applicazioni in topologia; in particolare, permette quella che è forse la dimostrazione più elementare del teorema del punto fisso di Brouwer.

Lista di adiacenza

In algebra computazionale, le liste di adiacenza sono una modalità di rappresentazione in memoria di grafi. È probabilmente la rappresentazione più immediata a cui è possibile pensare e la più semplice da implementare, anche se in generale non la ...

Matrice delle adiacenze

La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi finiti. Dato un qualsiasi grafo la sua matrice delle adiacenze è costituita da una matrice bina ...

Matrice delle probabilità di transizione

La matrice di transizione o matrice di Markov per un processo markoviano discreto è la matrice generata dalle probabilità di transizione in k passi: P n k:= {\displaystyle \mathbf {P} _{n}^{k}:={\begin{bmatrix}P_{0.0}^{n,k}&\cdots &P_{0,N ...

Matrice di grado

Nel campo della teoria dei grafi la matrice di grado è una matrice diagonale che contiene le informazioni sul grado di ogni vertice del grafo, ovvero il numero di archi che sono collegati ad esso. È usata insieme alla matrice delle adiacenze per ...

Matrice laplaciana

Dato un grafo semplice G con n vertici, la sua matrice Laplaciana L:= n × n {\displaystyle L:=_{n\times n}} è definita come: L = D − A, {\displaystyle L=D-A,} dove D è la matrice di grado e A è la matrice delle adiacenze del grafo. In caso di gra ...

Matrice unimodulare

Un esempio di una matrice totalmente unimodulare è il seguente: A = {\displaystyle A={\begin{bmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\ ...

Modularità (reti)

La modularità è una funzione usata nellanalisi dei grafi o delle reti per esempio in reti di computer o social network. Il suo valore quantifica la qualità della divisione della rete in moduli o comunità. Una buona suddivisione possiede alti valo ...

Morfologia matematica

La morfologia matematica è una teoria ed una tecnica per lanalisi delle forme geometriche. Solitamente si applica nellelaborazione digitale delle immagini, ma anche in grafi, e nella geometria solida.

Multidigrafo

In matematica e in particolare in teoria dei grafi, per multidigrafo intendiamo una struttura discreta che generalizza quella di digrafo: come questa è costituita da vertici e collegamenti tra vertici, archi, tra due vertici si possono avere più ...

Multidigrafo euleriano

In teoria dei grafi si dice multidigrafo euleriano un multidigrafo connesso, privo di cappi e dotato di un cammino euleriano, cioè di un cammino che tocca tutti i suoi archi una e una sola volta.

Multigrafo

In matematica e in particolare in teoria dei grafi, per multigrafo si intende una struttura che può dirsi costituita da un insieme finito di vertici e da spigoli che collegano due vertici o un vertice con sé stesso, con la possibilità che due ver ...

Multigrafo duale

Consideriamo un multigrafo planare M e una sua raffigurazione piana planare R. A questa raffigurazione si associa una cosiddetta raffigurazione duale R * nel modo seguente. Scegliamo un punto in ogni faccia di R e assegnamogli il ruolo di vertice ...

Multigrafo euleriano

In teoria dei grafi si dice multigrafo euleriano un multigrafo connesso, privo di cappi e dotato di un cammino euleriano, cioè di un cammino che tocca tutti i suoi spigoli una e una sola volta.

Notazione LCF

In matematica combinatoria, la notazione LCF o codice LCF è una notazione ideata da Joshua Lederberg ed estesa da Coxeter e Frucht, per la rappresentazione dei grafi cubici che sono hamiltoniani. Poiché i grafi sono hamiltoniani, i vertici posson ...

Numero cromatico dei vertici

Dato un grafo G e un insieme C di colori, il numero cromatico di G è il minimo numero di colori necessari a colorare i vertici di G in modo che, presi comunque due vertici adiacenti in G, essi abbiano diverso colore. Per colorazione dei vertici s ...

Olone

Olone è un termine coniato da Arthur Koestler nel 1968. Nella teoria dei sistemi non lineari, lolone è una parte di un sistema complesso, che ha una sua individualità, ma è anche parte integrata di un sistema di ordine superiore. Lolone è compost ...

Omeomorfismo (teoria dei grafi)

Due grafi G e H si dicono omeomorfi se e solo se esiste un isomorfismo tra due loro suddivisioni di spigoli G e H. In maniera equivalente, si possono definire omeomorfi due grafi G e H se e solo se possono essere ottenuti da uno stesso grafo K me ...

Pluridigrafo

In matematica e in particolare in teoria dei grafi, per pluridigrafo si intende una struttura che può considerarsi costituita da una famiglia di digrafi costruiti sopra un unico insieme di nodi.

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 ...

Ponte (teoria dei grafi)

Nella teoria dei grafi, un ponte è un arco la cui eliminazione aumenta il numero di componenti connesse. Equivalentemente, un arco è un ponte se e solo se non è contenuto in nessun ciclo. Un grafo senza ponti è equivalente a un grafo con grado di ...

Problema dei ponti di Königsberg

Il problema dei sette ponti di Königsberg è un problema ispirato da una città reale e da una situazione concreta. Königsberg, un tempo in Prussia Orientale e oggi exclave russa sul Baltico nota con il nome di Kaliningrad, è percorsa dal fiume Pre ...

Problema dei servizi

In topologia e teoria dei grafi, il problema dei servizi affronta questioni che si richiamano al classico quesito: Apparentemente di immediata soluzione, il problema delle tre case e dei tre pozzi fa sorridere gli ingenui, ma fa pensare i matemat ...

Raffigurazione di un grafo

La raffigurazione dei grafi, o tracciamento dei grafi, è una disciplina che si colloca tra la teoria dei grafi e linformatica, che si occupa della rappresentazione dei grafi in due o tre dimensioni. Questa attività è motivata da importanti applic ...

Rete a invarianza di scala

Viene definita rete a invarianza di scala un grafo che gode della seguente proprietà: se si considera la relazione tra il numero di nodi ed il numero delle loro connessioni si vede che il suo grafico è di tipo esponenziale negativo, e quindi inva ...

Snark (teoria dei grafi)

Nel campo matematico della teoria dei grafi, uno snark è un grafo cubico connesso, privo di ponti, con indice cromatico uguale a 4. In altre parole, è un grafo in cui ogni vertice ha tre vicini, e gli spigoli non possono essere colorati solo con ...

Struttura relazionale

In matematica per struttura relazionale si intende una struttura matematica tra le cui componenti compare qualche relazione matematica, oppure qualche funzione o qualche famiglia che non può considerarsi una operazione algebrica o una legge di co ...

Taglio (teoria dei grafi)

Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti. Ogni taglio determina un insieme di taglio o cut-set, definito come linsieme degli archi che hanno i propri estremi nei due sottinsiemi dell ...

Teorema di Bondy-Chvátal

Il teorema di Bondy-Chvátal è un teorema della teoria dei grafi relativo ai cicli hamiltoniani. È stato provato nel 1976 dal matematico britannico e canadese John Adrian Bondy e dal matematico polacco Václav Chvátal. Fornisce una condizione neces ...

Teorema di Ore

Il teorema di Ore è un teorema della teoria dei grafi provato nel 1960 dal matematico Norvegese Oystein Ore. Fornisce una condizione sufficiente, ma non necessaria, affinché un grafo sia Hamiltoniano, affermando che un grafo che contiene un suffi ...

Teoria algebrica dei grafi

La teoria algebrica dei grafi è una branca della matematica in cui si applicano metodi algebrici a problemi concernenti i grafi. Ciò è in contrasto con lapproccio geometrico, combinatorio o algoritmico. Ci sono tre branche principali della teoria ...

Teoria chimica dei grafi

La teoria chimica dei grafi è una branca della chimica matematica che applica la teoria dei grafi ai modelli matematici utilizzati per descrivere i fenomeni chimici. I pionieri della teoria chimica dei grafi sono Alexandru Balaban, Ivan Gutman, H ...

Teoria del mondo piccolo

La teoria del mondo piccolo o dei piccoli mondi, o effetto del mondo piccolo è una teoria che sostiene che tutte le reti complesse presenti in natura sono tali che due qualunque nodi possono essere collegati da un percorso costituito da un numero ...

Tre case e tre centrali

Il problema delle tre case e tre centrali è un problema di topologia privo di soluzione nel piano geometrico, noto in ambito scolastico e spesso proposto scherzosamente a solutori che si dimostrino troppo presuntuosi. Il problema è solitamente pr ...

Vertice (teoria dei grafi)

Nella teoria dei grafi, un vertice o nodo è lunità fondamentale di cui i grafi sono costituiti: un grafo consiste in un insieme di vertici e di archi. Dal punto di vista della teoria dei grafi, i vertici sono trattati come oggetti senza caratteri ...

Aritmetica di Presburger

Aritmetica di Presburger è la teoria del primo ordine dei numeri naturali con laggiunta introdotta nel 1929 da Mojżesz Presburger, da cui prende il nome. La firma dellaritmetica Presburger contiene solo loperazione di addizione e luguaglianza, om ...

Assiomi di Peano

Gli assiomi di Peano sono un gruppo di assiomi ideati dal matematico Giuseppe Peano al fine di definire assiomaticamente linsieme dei numeri naturali. Un modo informale di descrivere gli assiomi può essere il seguente: Si prende 0 o 1 a seconda d ...

Logica intuizionista

La logica intuizionista, o logica costruttiva, è la logica dellintuizionismo matematico e di altre forme di costruttivismo matematico. Secondo la prospettiva intuizionista, la logica e la matematica sono le applicazioni di metodi internamente coe ...

Logica fuzzy

La logica fuzzy o logica sfumata o logica sfocata è una logica in cui si può attribuire a ciascuna proposizione un grado di verità diverso da 0 e 1 e compreso tra di loro. È una logica polivalente, ossia unestensione della logica booleana. È lega ...

Model checking

Il model checking è un metodo per verificare algoritmicamente i sistemi formali. Viene realizzato mediante la verifica del modello, spesso derivato dal modello hardware o software, soddisfacendo una specifica formale. La specifica è spesso scritt ...

Semantica formale

Nel campo dellinformatica teorica, il termine semantica formale riguarda i modelli matematici che definiscono formalmente i linguaggi di programmazione o, più generalmente, la computazione stessa. Esistono molteplici approcci allo studio di quest ...

Semantica operazionale

La semantica operazionale descrive lesecuzione di un programma attraverso transizioni definite direttamente sul linguaggio del programma. Questo tipo di formalismo è concettualmente simile allinterpretazione vera e propria in cui abbiamo una macc ...

Verifica formale

Nellambito dei sistemi software e hardware la Verifica formale è lazione di provare o smentire matematicamente la correttezza degli algoritmi di un sistema controllando che rispettino specifiche formali o proprietà, usando metodi formali matemati ...

Abstract state machine

Nel campo dellinformatica il termine Abstract State Machine o ASM è usato spesso come sinonimo di macchina a stati finiti per quanto riguarda gli algoritmi astratti. Una particolare teoria sullutilizzo degli ASM per la specifica formale è stata s ...

Asserzione (informatica)

In informatica, un asserzione è un predicato presente in un programma che indica che il predicato sia sempre vero. Per esempio, il codice seguente contiene due asserzioni: x > 0 and x > 1, e saranno certamente vere nei punti indicati durant ...

Bisimulazione

Nel campo dellinformatica teorica la bisimulazione è una relazione binaria tra sistemi a transizione di stati, che associa due sistemi quando si comportano nello stesso modo, quando cioè un sistema simula laltro e viceversa. Intuitivamente due si ...

Funzione 91 di McCarthy

In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che ritorna 91 per tutti gli argomenti n ≤ 101 e ritorna n − 10 {\displaystyle n-10} per n > 101 {\displaystyle n> 101}. Limitatamente allinsieme degli interi minor ...

Invariante (informatica)

In informatica, un predicato è detto invariante per una sequenza di operazioni quando il predicato risulta vero prima e dopo dellesecuzione della sequenza. Sebbene i programmi per computer sono principalmente specificati in termini di cosa cambia ...

Lambda calcolo

Il lambda calcolo o λ-calcolo è un sistema formale definito dal matematico Alonzo Church, sviluppato per analizzare formalmente le funzioni e il loro calcolo. Le prime sono espresse per mezzo di un linguaggio formale, che stabilisce quali siano l ...

Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →