Geometria combinatoria

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 BIBDModifica

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.