Vecinătate (teoria graficelor)

În teoria grafurilor, un vârf adiacent al unui vârf v este un vârf conectat la v printr-o muchie . O vecinătate a unui vârf v într-un grafic G este un subgraf generat al graficului G , constând din toate vârfurile conjugate cu v și toate muchiile care conectează două astfel de vârfuri. De exemplu, figura prezintă un grafic cu 6 vârfuri și 7 muchii. Vârful 5 este adiacent vârfurilor 1, 2 și 4, dar nu adiacent vârfurilor 3 și 6. Vecinătatea vârfului 5 este un grafic cu trei vârfuri 1, 2 și 4 și o muchie care conectează vârfurile 1 și 2.

O vecinătate este adesea notată ca N G ( v ) sau (dacă știți care grafic este în discuție) N ( v ). Aceeași notație de vecinătate poate fi folosită pentru a se referi la mulțimea de vârfuri adiacente, mai degrabă decât la subgraful generat corespunzător. Vecinătatea descrisă mai sus nu include v în sine , iar această vecinătate este denumită o vecinătate deschisă a lui v . Puteți defini un cartier care include v . În acest caz, vecinătatea se numește închisă și se notează ca N G [ v ]. Dacă nu se specifică în mod explicit, se presupune că cartierul este deschis.

Vecinătățile pot fi folosite pentru a reprezenta grafice în algoritmi de computer prin lista de adiacență și matricea de adiacență . Vecinătățile sunt, de asemenea, utilizate în coeficientul de clustering al unui grafic, care măsoară densitatea medie a cartierelor sale. În plus, multe clase importante de grafice pot fi definite prin proprietățile vecinătăților sale sau prin simetria reciprocă a vecinătăților.

Un vârf izolat nu are vârfuri adiacente. Gradul unui vârf este egal cu numărul de vârfuri adiacente. Un caz special este o buclă care conectează un vârf de același vârf. Dacă o astfel de muchie există, vârful aparține propriei sale vecinătăți.

Proprietățile locale ale unui grafic

Dacă toate nodurile unui grafic G au vecinătăți izomorfe cu un grafic H , atunci se spune că G este local un grafic H , iar dacă toate vârfurile lui G au vecinătăți aparținând unei familii de grafice F , se spune că G este local un grafic F [1] [2] . De exemplu, în graficul octaedrului prezentat în figură, fiecare vârf are o vecinătate izomorfă cu un ciclu de patru vârfuri, deci octaedrul este local C 4 .

De exemplu:

Mulți vecini

Pentru o mulțime A de vârfuri, vecinătatea lui A este uniunea vecinătăților vârfurilor, astfel încât să conțină toate vârfurile conjugate la cel puțin un membru al lui A .

Se spune că o mulțime de vârfuri A a unui graf este un modul dacă toate vârfurile lui A au același set de vecinătăți în afara lui A. Orice grafic are o modularizare recursivă unică, numită modularizare , care poate fi construită din grafic în timp liniar . Algoritmul de descompunere modulară este aplicat altor algoritmi pentru grafice, inclusiv recunoașterea graficelor de comparabilitate .

Vezi și

Note

  1. ↑ Iadul, 1978 .
  2. ↑ Sedlacek, 1983 .
  3. ^ Wigderson , 1983 .
  4. ↑ Hartsfeld, Ringel, 1991 .
  5. ↑ Larión, Neumann-Lara, Pizaña, 2002 .
  6. ↑ Malnic, Mohar, 1992 .
  7. ↑ Seress, Szabó, 1995 .

Literatură