Vertex (teoria graficelor)

În teoria grafurilor, un vârf este unitatea fundamentală care alcătuiește graficele - un graf nedirecționat este format din multe vârfuri și multe muchii (perechi neordonate de vârfuri), în timp ce un graf direcționat este format din multe vârfuri și multe arce (perechi ordonate de vârfuri). În desenele care reprezintă un grafic, un vârf este de obicei indicat printr-un cerc cu o etichetă, o margine printr-o linie și un arc printr-o săgeată care leagă vârfurile.

Din punct de vedere al teoriei grafurilor, vârfurile sunt tratate ca obiecte indivizibile fără trăsături, deși pot reprezenta o structură în funcție de problema din care provine graful. De exemplu , o rețea semantică  este un grafic în care vârfurile reprezintă conceptul unei clase de obiecte.

Cele două vârfuri care formează o muchie se numesc vârfuri de capăt ale muchiei, iar muchia se spune că este incidentă vârfurilor. Se spune că un vârf w este adiacent unui alt vârf v dacă graficul conține o muchie ( v , w ). O vecinătate a unui vârf v este un subgraf generat format din toate vârfurile adiacente v .

Tipuri de vârfuri

Gradul unui vârf dintr-un grafic este numărul de muchii incidente cu acesta. Un vârf se numește izolat dacă gradul său este zero. Adică este un vârf care nu este capătul vreunei muchii. Un vârf se numește frunză (sau agățat ) dacă are un grad de unu. Un grafic direcționat distinge între gradul de ieșire (numărul de arce de ieșire) și gradul de intrare (numărul de muchii de intrare). Sursa se numește vârful cu zero în grad, iar vârful cu zero în afara gradului se numește sink .

O balama este un vârf a cărui îndepărtare duce la o creștere a componentelor conectate ale graficului. Un separator de vârfuri este un set de vârfuri, a căror eliminare duce la o creștere a componentelor conectate ale graficului. Un grafic k-conectat de vârfuri  este unul în care eliminarea a mai puțin de k vârfuri lasă întotdeauna graficul conectat. O mulțime independentă este un set de vârfuri dintre care două nu sunt adiacente, iar o acoperire de vârfuri este un set de vârfuri care include cel puțin un vârf de capăt al oricărei margini a graficului. Spațiul vectorial al vârfurilor al unui grafic este un spațiu vectorial care are ca bază vectorii corespunzători vârfurilor graficului (peste câmpul numerelor {0, 1}) [1] [2] .

Se spune că un grafic este tranzitiv la vârf dacă are simetrii care duc orice vârf la orice alt vârf. În contextul enumerării grafurilor și al izomorfismului grafului, este important să se facă distincția între vârfurile etichetate și vârfurile neetichetate . Un vârf etichetat este informații suplimentare asociate cu un vârf care îl deosebește de alte vârfuri etichetate. Două grafice pot fi considerate izomorfe numai dacă izomorfismul duce vârfuri la vârfuri cu aceleași etichete. Nodurile neetichetate pot fi apoi traduse în alte vârfuri pe baza numai adiacenței și fără a utiliza informații suplimentare.

Vârfurile unui graf sunt similare cu vârfurile unui politop , dar nu sunt la fel - scheletul al unui politop formează un graf ale cărui vârfuri sunt vârfurile politopului, dar vârfurile politopului au un suplimentar structura (locația geometrică) care este ignorată în teoria grafurilor. Figura de vârf a unui poliedru este similară cu vecinătatea unui vârf de graf.

Vezi și

Note

  1. ↑ M. Swami, K. Tulasimaran. Grafice, rețele și algoritmi. - Moscova: Mir, 1984. - S. 62-76. capitolul 4
  2. ↑ Reinhard Distel. Teoria grafurilor. - Novosibirsk: Editura Institutului de Matematică, 2002. - P. 35.

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii