Grafic nul

În câmpul matematic al teoriei graficelor , graficul nul se poate referi fie la graficul de ordin zero , fie, alternativ, la orice grafic fără punți (acesta din urmă este uneori numit grafic gol ).

Grafic de ordine zero

Graficul nul este conceput ca un grafic de ordine zero $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ este singurul grafic de ordin zero (adică care are zero vârfuri ). În consecință, are și margini zero. În unele contexte, $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ nu este considerat un grafic (fie prin definiție, fie mai simplu ca o chestiune de comoditate).

Graficul de ordine zero este obiectul inițial din categoria graficelor, conform unor definiții ale categoriilor de grafice. Includerea sa în definiția teoriei graficelor este într-adevăr mai utilă în unele contexte decât în altele. Pe partea pozitivă, $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ rezultă în mod natural din definițiile grafice obișnuite ale teoriei mulțimilor (este perechea ordonată de mulțimi goale ) și în structurile de date definite recursiv $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ este util să definiți cazul de bază pentru recursivitate (tratarea cu „ copacul zero ca fiul (nodului) fișierului marginilor lipsă în orice copac binar nu este zero, fiecare copac binar non-zero are exact doi copii). Dezavantajul este că majoritatea formulelor bine definite pentru proprietățile graficului trebuie să includă excepții pentru $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ dacă este inclus ca grafic („numărarea tuturor componentelor puternic conectate ale unui grafic” ar deveni „numărarea tuturor componentelor non-zero puternic conectate ale unui grafic”). Datorită aspectelor nedorite, în literatura de specialitate se presupune că termenul „grafic” implică un „grafic cu cel puțin un vârf”, cu excepția cazului în care contextul sugerează altfel. ^[1] ^[2]

Când este recunoscut, $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ satisface ( gol ) majoritatea acelorași proprietăți de bază ca și graficele $K_{1}$ ${\ displaystyle K_ {1}}$ $K_ {1}$ (graficul cu un singur vârf și fără margine): are o dimensiune zero, este egal cu graficul complementului ( ${\bar {K}}_{0}$ ${\ displaystyle {\ bar {K}} _ {0}}$ ${\ displaystyle {\ bar {K}} _ {0}}$ ), este o componentă conectată (adică, $\forall x\in V:\forall y\in V:\exists {\text{path}}(x,y)$ ${\ displaystyle \ forall x \ în V: \ forall y \ în V: \ există {\ text {cale}} (x, y)}$ ${\ displaystyle \ forall x \ în V: \ forall y \ în V: \ există {\ text {cale}} (x, y)}$ ), opădure și un grafic plan . Poate fi un grafic indirect sau un grafic direct (sau chiar ambele); atunci când este considerat drept direct, este un grafic aciclic direct și este atât un grafic complet, cât și un grafic gol (pentru a numi câteva). Cu toate acestea, definițiile pentru fiecare dintre aceste proprietăți ale graficului vor varia în funcție de contextul permis $K_{0}$ ${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$ .

Grafic fără punți

Pentru orice număr natural n , graficul fără punte (sau graficul gol) ${\bar {K}}_{n}$ ${\ displaystyle {\ bar {K}} _ {n}}$ ${\ displaystyle {\ bar {K}} _ {n}}$ este graficul cu n vârfuri și margini zero. Un grafic fără punte este ocazional desemnat ca grafic nul în contexte în care graficul de ordine zero nu este permis. ^[1] ^[2]

Graficul fără punte cu n -vertex este graficul complementului pentru graficul complet $K_{n}$ ${\ displaystyle K_ {n}}$ $K_ {n}$ , și, prin urmare, este denumit în mod obișnuit ${\bar {K}}_{n}$ ${\ displaystyle {\ bar {K}} _ {n}}$ ${\ displaystyle {\ bar {K}} _ {n}}$ .

Notă

^ ^A ^b (EN) Eric W. Weisstein, Grafic gol , în MathWorld , Wolfram Research.
^ ^A ^b (EN) Eric W. Weisstein, Null Graph , în MathWorld , Wolfram Research.

Bibliografie

Harary, F. și Read, R. (1973), „Este graficul nul un concept inutil?”, Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere cu grafice nule

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[ref_A-1] A ^b (EN) Eric W. Weisstein, Grafic gol , în MathWorld , Wolfram Research.

[ref_B-2] A ^b (EN) Eric W. Weisstein, Null Graph , în MathWorld , Wolfram Research.

[1]

[2]