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

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 .

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

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.

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.

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

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 .

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.

## Individual evidence

## literature

- Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).