# 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.