Neighborhood (graph theory)

from Wikipedia, the free encyclopedia

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

  1. HWLang, FH Flensburg

literature