Szomszédság (grafikonelmélet)

A gráfelméletben azt mondjuk, hogy egy nem orientált gráf két csúcsa szomszédos vagy szomszédos, ha egy él kapcsolja össze őket. A csúcs szomszédsága kijelölheti a szomszédos csúcsok halmazát, vagy társított algráfot, például az indukált részgráfot. Egy irányított gráf , a kifejezés korábbi, vagy utódja általánosan használt.

Formális meghatározás

Klasszikus meghatározások

Egy irányítatlan gráf , a környék egy csúcs , gyakran nevezik ( N a környéken ) jelölhet néhány dolgot: $G = (V, E)$ $v \ a V-ben$ $N_ {G} (v)$

A szomszédos csúcstalálkozók: $\ {w: (v, w) \ E \}$
Az előző csúcsok által kiváltott részgráf, a verziótól függően vagy anélkül . $G$ $v$

Változatok

Az orientált grafikonok esetében meghatározhatjuk az orientált szomszédság fogalmát is.
Előfordul, hogy egy szomszédot tekintünk egy csúcs távolságától , vagyis az összes csúcsot, amelyet v-től kevesebb, mint k éle választ el . Ez a helyzet különösen a szinkron elosztott számítások esetében. $k$

Használ

A szomszédság fogalma a gráfelmélet klasszikus fogalma, beavatkozik például a színezés , a stabilitás és a csúcsok általi lefedettség fogalmának meghatározásába .

Alkalmazási példa a társadalmi hálózatok modellezése, ahol egy csúcs szomszédsága egy személy tudását reprezentálja. Ebben az összefüggésben a szomszédság lehetővé teszi a klaszterezési együttható meghatározását .

Megjegyzések és hivatkozások

Például Olivier Fouquet, Théorie des graphes: rövid bevezetés (feltételezett algebrai torzítással) ,2012( olvasható online [PDF] ).
Lásd például: David Peleg , Distributed Computing: A Locality-Sensitive Approach , vol. 5, SIAM,2000