Geometria combinatoria

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
lezione
Geometria combinatoria
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Geometria analitica


Con il termine geometria combinatoria (o geometria combinatorica) si intende il settore della matematica che studia insiemi finiti di oggetti semplici (interi, stringhe, nodi e collegamenti, punti e linee, configurazioni discrete, insiemi finiti, ...) che soddisfano proprietà ben definite e tendenzialmente semplici. Esempi di collezioni di oggetti studiate nell'ambito della geometria combinatoria sono:

  • le permutazioni di n oggetti,
  • le combinazioni con ripetizione di 5 dei primi 7 interi,
  • i grafi poliedrali,
  • i quadrati magici e i quadrati latini.

La geometria combinatoria si propone di studiare sul piano matematico le situazioni pratiche ed i relativi problemi i cui aspetti essenziali si possono esprimere con modelli discreti. Alcuni esempi di queste situazioni sono:

  • le disposizioni delle persone intorno ad un tavolo circolare,
  • le estrazioni di palline di colori diversi da un'urna,
  • le disposizioni dei pezzi del gioco degli scacchi su una scacchiera,

Un aspetto di primaria importanza in questi studi riguarda l'enumerazione delle configurazioni: per alcuni esempi di questa problematica si vedano ad esempio fattoriale, coefficiente binomiale, numeri di Catalan e numeri di Fibonacci. Un altro aspetto fondamentale della combinatoria è quello algoritmico: innanzi tutto la conoscenza delle caratteristiche combinatorie di un tipo di configurazioni è essenziale per individuare i meccanismi che consentano di manipolarle; inoltre ogni algoritmo può essere oggetto di indagini combinatorie, come quelle di natura enumerativa richieste per valutare la sua efficienza.

T-disegni e BIBD[modifica]

Un -disegno con è una coppia ordinata in cui V è un insieme di cardinalità di elementi detti vertici o punti e B è una famiglia di parti di V ciascuna di cardinalità k dette blocchi e non necessariamente distinte con la proprietà che ciascuna t-upla di vertici è contenuta in esattamente blocchi. Ad un -disegno si può associare una matrice detta di incidenza dove se il blocco j contiene il vertice i e altrimenti.

Un -disegno con t = 2 e k < v si chiama BIBD o disegno. Un disegno con blocchi di cardinalità si chiama PBD.