Grafo nullo

Da Wikipedia, l'enciclopedia libera.

Nel campo matematico della teoria dei grafi, il grafo nullo può riferirsi o al grafo di ordine-zero o, alternativamente, a qualunque grafo privo di ponti (quest'ultimo è chiamato a volte grafo vuoto).

Grafo di ordine zero[modifica | modifica sorgente]

Il grafo nullo inteso come grafo di ordine-zero K_0 è l'unico grafo di ordine zero (cioè che ha zero vertici). Di conseguenza, esso ha anche zero spigoli. In alcuni contesti, K_0 non è considerato un grafo (o per definizione, o più semplicemente per una questione di convenienza).

Il grafo di ordine zero è l'oggetto iniziale nella categoria dei grafi, secondo alcune definizioni di categoria dei grafi. La sua inclusione nell'ambito della definizione della teoria dei grafi è infatti più utile in alcuni contesti che in altri. Dal lato positivo, K_0 consegue naturalmente dalle abituali definizioni di grafo della teoria degli insiemi (esso è la coppia ordinata di insiemi vuoti), e nelle strutture dati definite ricorsivamente K_0 è utile per definire il caso di base per la ricorsione (trattando l'albero nullo come (nodo) figlio degli spigoli mancanti in un qualunque albero binario non nullo, ogni albero binario non nullo ha esattamente due figli). Dla lato negativo, la maggior parte delle formule ben definite per le proprietà dei grafi devono includere eccezioni per K_0 se esso è incluso come grafo ("contare tutte le componenti fortemente connesse di un grafo" diventerebbe "contare tutte le componenti fortemente connesse non nulle di un grafo"). A causa degli aspetti indesiderabili, in letteratura si assume di solito che il termine "grafo" implichi un "grafo con almeno un vertice" a meno che il contesto suggerisca altrimenti.[1][2]

Quando è riconosciuto, K_0 soddisfa (vuotamente) la maggior parte delle stesse proprietà di base dei grafi di K_1 (il grafo con un solo vertice e nessuno spigolo): ha una dimensione di zero, è uguale al grafo complemento (\bar K_0), è una componente connessa (ossia, \forall x \isin V : \forall y \isin V : \exists \text{path}(x,y)), una foresta e un grafo planare. Può essere un grafo indiretto o un grafo diretto (o perfino entrambi); quando è considerato come diretto, è un grafo aciclico diretto, ed è sia un grafo completo che un grafo vuoto (solo per nominarne alcuni). Tuttavia, le definizioni per ciascuna di queste proprietà dei grafi varieranno a seconda se il contesto ammetta K_0.

Grafo privo di ponti[modifica | modifica sorgente]

Per ogni numero naturale n, il grafo privo di ponti (o grafo vuoto) \bar K_n è il grafo con n vertici e zero spigoli. Un grafo privo di ponti è designato occasionalmente come grafo nullo in contesti dove il grafo di ordine zero non è permesso.[3][4]

Il grafo privo di ponti con n-vertex è il grafo complemento per il grafo completo K_n, e perciò è comunemente indicato come \bar K_n.

Note[modifica | modifica sorgente]

  1. ^ (EN) Eric W. Weisstein, .html Empty Graph in MathWorld, Wolfram Research.
  2. ^ (EN) Eric W. Weisstein, .html Null Graph in MathWorld, Wolfram Research.
  3. ^ (EN) Eric W. Weisstein, .html Empty Graph in MathWorld, Wolfram Research.
  4. ^ (EN) Eric W. Weisstein, .html Null Graph in MathWorld, Wolfram Research.

Bibliografia[modifica | modifica sorgente]

  • Harary, F. and Read, R. (1973), "Is the null graph a pointless concept?", Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica