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.

Individual evidence

1. ↑ HWLang, FH Flensburg

literature

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