Neighbourhood of a vertex

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

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

D is an out-semicomplete digraph (in-semicomplete digraph) if D has no pair of non-adjacent vertices with a common in-neighbour or a common out-neighbour. D is a locally semicomplete digraph if D is both out-semicomplete and in-semicomplete.