Nod (teoria grafurilor)

Un graf cu 6 noduri și 7 muchii unde nodul cu numarul 6 de pe extrema stanga este un nod-frunză, sau nod terminal

În matematică, mai exact în teoria grafurilor, un nod sau vârf este unitatea fundamentală din care sunt formate grafurile: un graf neorientat este format dintr-o mulțime de noduri și o mulțime de muchii (perechi neordonate de noduri), în timp ce un graf orientat este format dintr-o mulțime de noduri și o mulțime de arce (perechi ordonate de noduri). În diagrama unui graf, un nod este de obicei reprezentat printr-un cerc cu o etichetă, iar o muchie este reprezentată de o linie sau de o săgeată de la un nod la altul.

Din punctul de vedere al teoriei grafurilor, nodurile sunt tratate ca obiecte indivizibile și fără proprietăți, deși ele pot avea o structură suplimentară în funcție de aplicația în care apare graful; de exemplu, o rețea semantică este un graf în care nodurile reprezintă concepte sau clase de obiecte.

Cele două noduri care formează o muchie sunt numite extremități ale muchiei, iar muchia este incidentă la noduri. Un nod w este declarat a fi adiacent unui alt nod v dacă graful conține o muchie (v,w). Vecinătatea unui nod v este un subgraf indus al grafului, format de toate nodurile adiacente cu v.

Tipuri de noduri

Exemplu de rețea cu 8 noduri (din care unul este izolat) și 9 muchii.

Gradul unui nod, notată 𝛿(v) într-un graf este numărul de muchii incidente la el. Un nod izolat este un nod cu gradul zero, adică un nod care nu este extremitatea niciunei muchii (de exemplu imaginea ilustrează un nod izolat). Un nod frunză (sau nod terminal) este un nod cu gradul unu. Într-un graf orientat, se poate distinge gradul exterior (numărul de muchii care ies), notat cu 𝛿 ⁺(v), de gradul interior (numărul de muchii care intră), notat cu 𝛿^-(v); un nod-sursă este un nod cu gradul interior zero, în timp ce un nod-drenă este un nod cu gradul exterior zero. Un nod simplicial este unul ai cărui vecini formează o clică: nodurile vecine sunt adiacente două câte două. Un nod universal este un nod care este adiacent cu toate celelalte noduri din graf.

Un punct de articulație^⁠(d) este un nod a cărui eliminare ar deconecta graful rămas; un separator^⁠(d) este o colecție de noduri a cărei eliminare ar deconecta restul grafului în părți mai mici. Un graf k-conex în noduri este un graf din care se pot elimina oricare mai puțin de k noduri și graful ar rămâne conex. O mulțime independentă^⁠(d) este o mulțime de noduri dintre care niciunele nu sunt adiacente, și o acoperire de noduri^⁠(d) este o mulțime de noduri care include cel puțin o extremitate a fiecărei muchii din graf. Spațiul nodurilor^⁠(d) unui graf este un spațiu vectorial generat de o bază formată din nodurile grafului.

Un graf este nod-tranzitiv^⁠(d) dacă are simetrii care transformă orice nod în orice alt nod. În contextul enumerării grafurilor și izomorfismelor de graf^⁠(d) este important să se facă distincția între nodurile etichetate și nodurile neetichetate. Un nod etichetat este un nod căruia i s-au asociat informații suplimentare care permit distingerea sa de alte noduri etichetate; două grafuri pot fi considerate izomorfe numai când corespondența între nodurile lor asociază noduri cu etichete egale. Un nod neetichetat este unul care poate fi substituit cu orice alt nod doar pe baza adiacențelor sale din graf și nu se bazează pe nicio informație suplimentară.

Nodurile din grafuri sunt analoage, dar nu același lucru, cu vârfurile poliedrelor: scheletul unui poliedru formează un graf, ale cărui noduri sunt vârfurile poliedrului, dar vârfurile poliedrului au structură adițională (poziția lor geometrică), care se presupune că nu este prezentă în teoria grafurilor.

Bibliografie

• Gallo, Giorgio; Pallotino, Stefano (1988). „Shortest path algorithms”. Annals of Operations Research. 13 (1): 1–79. doi:10.1007/BF02288320. 
• Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (ediție în engleză, Wiley 1961; Methuen & Co, New York 1962; rusă, Moscova 1961; spaniolă, Mexico 1962; română, București 1969; chineză, Shanghai 1963; retipărire a primei ediții în engleză din 1962. Dover, New York 2001)
• Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9. 
• Biggs, E. H.; Lloyd; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9. 
• Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8. 
• Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2.