Graph (mathematics)

A graph in the graph theory an abstract structure representing a set of objects, together with the existing connections between these objects. The mathematical abstractions of objects are nodes (also called vertices ) of the graph. The pairwise links between nodes are called edges (sometimes called arcs). The edges can be directed or undirected. Often graphs are vividly drawn by the nodes are represented by points and edges by lines.

Illustrative examples of graphs are a pedigree or the U- Bahn network of a city (see illustrations). With a family tree, each node represents a family member and each edge is a connection between a parent and a child. In a metro network, each node has a metro station and each edge represents a direct train between two stations.

• 2.1 Derived terms
• 2.2 Special Cases 2.2.1 subgraphs, paths and cycles

• 5.1 Colored Graphs
• 5.2 Weighted graph
• 5.3 mappings between graphs

Visualization of special graphs

Multigraph

In so-called multigraph two nodes can be connected by multiple edges, which is not allowed in simple graphs. In addition, may contain multigraph loops.

Node are connected by a plurality of edges, only one edge is often marked and the number of edges between the two nodes as the edge weight is written to the one edge. In the example, there are 60 edges between nodes A and D. Instead of all 60 edges is to draw an edge drawn with the edge weight 60.

Digraph

In digraphs (also directed or oriented graph called ) edges are held by lines marked by arrows, with the arrow pointing from the first to the second node. This shows that each edge of the graph can be traversed in one direction only.

Hypergraph

For hypergraph connects an edge ( also called hyperedge ) not only two, but several nodes simultaneously. Can be represented hypergraphs for example, by a plurality of planar graphs with indexing of the edges. Hypergraphs with few edges ( so-called thin graphs) to draw so that it draws a lot of points that correspond to the nodes, and the belonging to a hyperedge points are then encircled by a closed line, thus the subset of belonging to this node indicates within all nodes. For hypergraphs with many edges, this illustration is but quickly become confusing. Less intuitive, but it is clear then, represent a hypergraph as bipartite meta- graph, where one of the two Bipartitionsmengen the nodes of the hypergraph, the other Bipartitionsmenge meets the hyperedges of the hypergraph. The edges between these two Bipartitionsmengen then symbolize the membership of nodes to hyperedges.

Definitions

A graph is a tuple, where a set of nodes called (english vertex / vertices, often called vertices ) and a set of edges ( engl. edge / edges, sometimes called arcs). Here, in

• Undirected graph without multiple edges, a subset of all two - element subsets of,
• Directed graph without multiple edges, a subset of all pairs (i, j) resulting from the Cartesian product,
• Undirected graph with combined multiple edges a multiset over the set of all 2- element subsets of, ie a function
• Directed graph with combined multiple edges a multiset over the Cartesian product, ie a function
• Directed graph with independent multiple edges defined by two functions that map the edges of their source and target nodes.
• Hypergraph is a subset of the power set of.

The words " without multiple edges " you can usually away and called graphs with multiple edges multigraph. Furthermore, one usually omitted the attribute " non-directional " and features explicitly only directed graphs. Undirected graphs without multiple edges is called often simple or easy. Another name for directed graphs is the digraph ( directed graph ).

Derived terms

Instead, the node and edge set of a graph with the symbols and identify, you can also define public figures and that map a graph on the vertex set and edge set. For two graphs, and so and and denote and.

The ambiguity and is implemented at this notation into account, although the pictures show something other than its group node and edge set. By convention offers itself to call with or without an argument node or edge set, and with an argument against denote the defined mappings.

If a graph is said to be in general node or vertex of when to part. Moreover refers edges as

• Undirected edge of, if an undirected graph.
• Directed edge from if a directed graph is.
• Hyperedge of if a hypergraph is.

In an undirected edge is referred to as terminal nodes and of. In a directed edge is called the start node and a leaf node of.

For multi- graph, the multiplicity of designated. If true, then one speaks of a multi- or multiple edge.

Has an edge in a directed graph form, it is called a loop. If the loop in a multi- graph at the same time a multiple edge, then one speaks of a multi- loop. Directed graphs without loops is called schleifenlos or loop-free.

As the number of nodes of a graph refers to the number of its nodes, as edges number refers to the number of its edges ( in multigraph is summed over the multiplicity of the edges).

Special cases

Two different edges of a directed graph, which connect the same node, can also be regarded as a non-directional edge in the directed graph. In the case of multiple edges, the multiplicities of both edges must match.

There is at any edge of a directed graph such opposite edge in the graph, this is a symmetrical graph.

A graph whose vertex set is finite, is called a finite graph. Inevitably, in this and the edge set is finite. In contrast, we call a graph whose vertex set is infinite, infinite graphs. Mostly we only consider finite graphs and therefore leaves the attribute "finally" gone, while explicitly characterizes infinite graphs.

Subgraphs, paths and cycles

A subgraph of a graph contains only nodes and edges, which are also included. A induced by a vertex set U subgraph containing the nodes from U and all edges of G between these nodes.

A sequence of pairwise distinct nodes are connected in successive nodes and in the graph by an edge is called a path, sometimes called path. Applies, and this is the only double knots, it is called a cycle or circle. A sequence of adjacent nodes in the node may be repeated is called a sequence of edges. The terms path, path edge sequence, circle and cycle are defined in the literature in different ways.

If a directed graph contains cycles, it is called cyclically. Contains a directed graph no cycle, it is called acyclic or cycle-free. Then he represents a partial order.

Basic Operations

In the investigation of graph properties, it is more common that one needs to apply simple operations on graphs in order to be able to write as compact as possible and thus easier to understand. Particularly frequently the usual operations of set theory ( union, intersection, difference and complement) are applied to node or edge sets of graphs so that they are directly defined on graphs.

And are graphs of the same type, referred to as

• The graph, which arises when one combines the node - and edge set,
• The graph which arises if we subtract from the edge set of and
• The graph that arises when one subtracts from the node-set of all the edges and removed the nodes contain.

Note here the different definitions of union and set difference of sets and multisets. One writes also be abbreviated

• If subset is
• If empty or subset of is,
• If,
• If,
• If and
• Necessary.

Edge contraction and the formation of Komplementgraphen are more basic operations.

Comments

Undirected graphs without multiple edges are special cases of hypergraphs. Multigraph in which there are no multiple edges are not formal, but clearly equivalent to graphs without multiple edges, which is why even those designated as graphs without multiple edges. There is a bijective mapping between the two variants. In this sense, graphs without multiple edges thus special cases of graphs with multiple edges. The situation is similar with undirected graphs are special cases of directed graphs in a sense. Is a directed graph symmetric and schleifenlos, one refers to this as a non-directional, as it is a simple one-one correspondence between the two variants are also here (see also the adjacency matrix ).

Of course, it can be defined as undirected graphs with loops, with one. Defined them probably easiest as just as a (formal ) special cases of directed graphs and the condition of the Schleifenlosigkeit omits However, such graphs are rarely the subject of the considerations in graph theory.

The most common type of graphs are directed hypergraphs with multiple edges. Each graph type defined above can then be viewed as a special case of this. Such graphs are so good as not subject to the considerations in graph theory, which is why they are also explained here in detail.

If graphs serve as a representation of facts, algorithms are needed that are needed for graph drawing. This discipline of computer science has always progressed in recent years and provides solutions for different visualizations that are based on graphs.

Extensions

Graphs can be supplemented with additional properties or information.

Colored graphs

An extension of graphs to nodes colored graphs obtained by the tuple is added to a triple. is a mapping from the set of natural numbers. Clearly there is every node so that one color.

Instead, the node can also color the edges in graphs without multiple edges and in hypergraphs and then speaks of an edge- colored graph. This also extends to the tuple into a triple, but where is a mapping from (instead of ) in the set of natural numbers. Clearly there is any edge so that one color. In graphs with multiple edges, this is in principle possible, but more difficult to define, especially when multiple edges are to be according to their multiplicities associated with several different colors.

Note that the terms " coloring" and " color" in graph theory have also a more specific meaning. Exactly one speaks then indeed of valid coloring, leaves the attribute " valid" but mostly gone.

Similarly, there are also named graphs in which nodes and / or edges have a name, and assign the pictures or the node or edge a name. The examples shown above are named graphs, where the nodes are named with letters. This is often done with visualization, so you can better discuss the graph.

Weighted graphs

Instead of knots or edge- colored graph is called node - or edge-weighted graph, if the maps in real numbers instead of the natural numbers. Node - or edge- colored graphs are thus special cases of node or edge-weighted graph.

This is referred to as or weight of the node or the edge. To distinguish one also speaks of node weight and edge weight. Such weighting will be required if the information on node ties is not sufficient. Summing up, for example, the road network (simplified) as a graph on ( places are nodes that places are connecting roads edges), so could a weighting of the edges give information about the distance between two places. The edge weights of the graph can be collected in a quadratic weighting matrix, the adjacency matrix.

Mappings between graphs

Finally, also mappings between graphs can be defined. Particularly interesting are those which are compatible with the structure of the two, so-called " homomorphisms ".

Be it and graphs of the same type. A mapping is called a homomorphism between and, if the following applies:

• In undirected graphs without multiple edges: Is { v, w } of an edge G1, then { p ( v ), p ( f) }, an edge of G2.
• In a directed graph without multiple edges: Is ( v, w) edge of G1, then ( p ( v ), p ( w)) of edge G2.
• In undirected graphs with multiple edges: E1 ( { v, w } ) ≤ E2 ( {p (v ), p ( f) }), ie, the two corners are connected to a maximum of as many edges as its corners.
• In directed graphs with multiple edges: E1 ( ( v, w) ) ≤ E2 ( (p (v ), p ( w ))).
• In hypergraphs: If { v1, ..., vk } edge of G1, then { p ( v1 ), ..., p ( vk) } edge of G2.

The image p ( G1) is then a subgraph of G2. If p is invertible and the inverse is also a homomorphism, then p is an isomorphism of graphs.

Note, that the node from the edges have a priority by P is specified as a function of only the nodes that only develops a -induced effect on the edges.

Data Structures

For the representation of graphs in the computer, there are essentially two common forms: the adjacency matrix (also adjacency matrix ) and the adjacency ( neighbor list ). The importance of the two representations is that practically falls back any algorithmic solution graph theoretical problems on at least one of the two representations. Another, but less frequently used way to represent graphs in the computer is the incidence matrix, which is also referred to as a node-edge matrix.

Incidence matrices are indeed more complex to implement and manage, but offer a number of advantages over adjacency matrices. First, it is always consume at a fixed number of edge only linearly much space on the number of nodes, which (ie, the graph with few edges ) is advantageous in particular with thin graph while the adjacency matrix has square footprint with respect to the number of nodes (but compact for dense graphs, ie, graphs with many edges ). On the other hand, many graph-theoretical problems can be solved only with adjacency lists in linear time. In practice, therefore, usually used this form of representation.