Neighbourhood of a vertex

Материал из WikiGrapp
Версия от 12:27, 7 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Neighbourhood of a vertex''' --- окрестность вершины. For each vertex <math>v</math> the set <math>N(v)</math> of vertices which are ''adjacen…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Neighbourhood of a vertex --- окрестность вершины.

For each vertex [math]\displaystyle{ v }[/math] the set [math]\displaystyle{ N(v) }[/math] of vertices which are adjacent to [math]\displaystyle{ v }[/math]. The other name is open neighbourhood. The closed neighbourhood is [math]\displaystyle{ N[v] = N(v) \cup \{v\} }[/math].

For disjoint subsets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] of [math]\displaystyle{ V }[/math], we define [math]\displaystyle{ [A,B] }[/math] to be the set of all edges that join a vertex of [math]\displaystyle{ A }[/math] and a vertex of [math]\displaystyle{ B }[/math]. Furthermore, for [math]\displaystyle{ a \in A }[/math], we define the private neighbourhood [math]\displaystyle{ pn(a,A,B) }[/math] of [math]\displaystyle{ a }[/math] in [math]\displaystyle{ B }[/math] to be the set of vertices in [math]\displaystyle{ B }[/math] that are adjacent to [math]\displaystyle{ a }[/math] but to no other vertex of [math]\displaystyle{ A }[/math]; that is, [math]\displaystyle{ pn(a,A,B) = \{b \in B| N(b) \cap A = \{a\}\} }[/math].

Given a digraph [math]\displaystyle{ D }[/math], let [math]\displaystyle{ x,y }[/math] be distinct vertices in [math]\displaystyle{ D }[/math]. If there is an arc from [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math], then we say that [math]\displaystyle{ x }[/math] dominates [math]\displaystyle{ y }[/math] and write [math]\displaystyle{ x \rightarrow y }[/math] and call [math]\displaystyle{ y }[/math] (respectively, [math]\displaystyle{ x }[/math]) an out-neighbour (out-neighborhood) (respectively, an in-neighbour (in-neighborhood)) of [math]\displaystyle{ x }[/math] (respectively, [math]\displaystyle{ y }[/math]). We let [math]\displaystyle{ N^{+}(x), N^{-}(x) }[/math] denote the set of out-neighbours, respectively, the set of in-neighbours of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ D }[/math]. Define [math]\displaystyle{ N(x) }[/math] to be [math]\displaystyle{ N(x) = N^{+}(x) \cup N^{-}(x) }[/math].

[math]\displaystyle{ D }[/math] is an out-semicomplete digraph (in-semicomplete digraph) if [math]\displaystyle{ D }[/math] has no pair of non-adjacent vertices with a common in-neighbour or a common out-neighbour. [math]\displaystyle{ D }[/math] is a locally semicomplete digraph if [math]\displaystyle{ D }[/math] is both out-semicomplete and in-semicomplete.