Neighbourhood (graph theory)

Neighborhood is a fundamental concept in graph theory, a sub- area of mathematics. It describes properties of a node, which can be described by connected edges with him.

Definition

For undirected graphs

Be an undirected graph ( which may contain also wrap ). Then the names of two nodes and adjacent, connected or adjazent in when they are connected by an undirected edge, ie when. If two adjacent nodes, so they are also called neighbors.

Denotes the set of all neighbors of a node in. Further, we denote by the set of all neighbors of Knoten.Diese in quantities contained the vicinity of or are called.

A node is exactly then his own neighbor, if it has a sling. The neighborhood of a set of nodes, node from the set itself contain. The Association of Convenience with the node is called closed neighborhood.

A node and an edge are called incident if the node connects to another node (). Two undirected edges are called adjacent if they are not disjoint, ie if they have a common node.

These terms shall apply to hypergraphs and edges.

If it is clear which graph is, allowed to the index in the notation often away

For directed graphs

A node is called predecessor in a directed graph when directed edge from is. With is defined as the set of all predecessors of a node in. Further, we denote by the set of all predecessors of node in. or also called predecessor quantity or amount of input or.

The analogy succeeds in when directed edge from is. With is defined as the set of all successors of a node in. Further, we denote by the set of all successors of the node in. or also called successor amount or quantity of output or.

In directed graphs further distinction between positive and negative edges incident edges incident. A directed edge is positive incident to its start node and end node negative incident to her.