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.
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.
- Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).