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

Il grafo nullo inteso come grafo di ordine-zero   è l'unico grafo di ordine zero (cioè che ha zero vertici). Di conseguenza, esso ha anche zero spigoli. In alcuni contesti,   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,   consegue naturalmente dalle abituali definizioni di grafo della teoria degli insiemi (esso è la coppia ordinata di insiemi vuoti), e nelle strutture dati definite ricorsivamente   è 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). Dal lato negativo, la maggior parte delle formule ben definite per le proprietà dei grafi devono includere eccezioni per   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,   soddisfa (vuotamente) la maggior parte delle stesse proprietà di base dei grafi di   (il grafo con un solo vertice e nessuno spigolo): ha una dimensione di zero, è uguale al grafo complemento ( ), è una componente connessa (ossia,  ), 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  .

Grafo privo di ponti modifica

Per ogni numero naturale n, il grafo privo di ponti (o grafo vuoto)   è 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.[1][2]

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

Note modifica

  1. ^ a b (EN) Eric W. Weisstein, Empty Graph, in MathWorld, Wolfram Research.
  2. ^ a b (EN) Eric W. Weisstein, Null Graph, in MathWorld, Wolfram Research.

Bibliografia modifica

  • 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

Altri progetti modifica

Collegamenti esterni modifica

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