# Neighborhood (graph theory)

In graph theory , the neighborhood of a node is understood to be the set of all nodes in the graph that are connected to it by an edge . An adjacency matrix is often used to represent the neighborhood relationship between the nodes of a graph.

## definition

### For undirected graphs

Let be an undirected graph (which can also contain loops). Then two nodes are called adjacent , connected or adjacent in if they are connected by an undirected edge , that is, if holds. If two nodes are adjacent, they are also called neighbors . ${\ displaystyle G = (V, E)}$ ${\ displaystyle u, v \ in V}$ ${\ displaystyle G}$ ${\ displaystyle \ {u, v \} \ in E}$ ${\ displaystyle N_ {G} (v)}$ denotes the set of all neighbors of a node in . Furthermore, one denotes the set of all neighbors of the nodes contained in. These sets are also called the neighborhood of and . ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} (X)}$ ${\ displaystyle X \ subseteq V}$ ${\ displaystyle v}$ ${\ displaystyle X}$ A knot is its own neighbor if and only if it has a loop. The neighborhood of a set of nodes can contain nodes from the set itself. The union of the neighborhood with the nodes from is called a closed neighborhood . ${\ displaystyle N_ {G} (X)}$ ${\ displaystyle X}$ ${\ displaystyle X}$ A node and an edge are called incident if the node connects to another node ( ). Two undirected edges are called neighboring if they are not disjoint , i.e. i.e. if they have a common node. ${\ displaystyle v}$ ${\ displaystyle e}$ ${\ displaystyle e}$ ${\ displaystyle v}$ ${\ displaystyle v \ in e}$ These terms apply analogously to hypergraphs and hypergraphs. If it is clear which graph it is, the index is often left out of the notation. ${\ displaystyle G}$ ### For directed graphs

A node 's predecessor of in a directed graph if directed edge of is. With denotes the set of all predecessors of a node in . Furthermore, denotes the set of all ancestors of the nodes of in . or is also called the predecessor quantity or input quantity from or . ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle G}$ ${\ displaystyle (x, y)}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} ^ {-} (v)}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} ^ {-} (X)}$ ${\ displaystyle X}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} ^ {-} (v)}$ ${\ displaystyle N_ {G} ^ {-} (X)}$ ${\ displaystyle v}$ ${\ displaystyle X}$ Analog is called successor of in , if directed edge of is. With denotes the set of all successors of a node in . Furthermore, one denotes the set of all descendants of the nodes of in . or is also called successor set or initial set of or . ${\ displaystyle y}$ ${\ displaystyle x}$ ${\ displaystyle G}$ ${\ displaystyle (x, y)}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} ^ {+} (v)}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} ^ {+} (X)}$ ${\ displaystyle X}$ ${\ displaystyle G}$ ${\ displaystyle N_ {G} ^ {+} (v)}$ ${\ displaystyle N_ {G} ^ {+} (X)}$ ${\ displaystyle v}$ ${\ displaystyle G}$ In the case of directed graphs, a further distinction is made between positively incident edges and negatively incident edges. A directed edge is positively incident to its start node and negatively incident to its end node.