Why is graph theory important

Graph theory

Graph theory as a mathematical method deals with the study of graphs as the representation of a variety of problems. The practical application possibilities of graph theory come into play particularly in logistics and project management.

In this chapter you will learn why graph theory is important and what makes it up. You can use the following exercises to test your knowledge and prepare for your next exam.

Why is graph theory important?

As a branch of mathematics graph theory examines the properties of graphs and their relationships to one another. What at first glance appears to be an abstract and highly theoretical consideration can actually provide approaches to a variety of everyday and operationally relevant problems.

In addition to economics, graph theory is also used in computer science, as a large number of algorithmic problems can be solved using graph theory.

What is graph theory?

A "Graph G" basically consists of the following components:

  • Amount of node V
  • Amount of edges E

Two nodes are always connected by an edge. You can differentiate between different types of graphs.

Distinctions in graphs

Basically, a distinction can be made between directed and undirected graphs. The graphs differ in the properties of the respective edges between the nodes.

Directed and undirected graphs

  • Directed graphs:
    The edges that connect the individual nodes are shown as arrows. Thus, the edge can only be used in the direction of the arrow.
  • Undirected graphs:
    The edges of the graph can be used as a connection between the nodes in both directions.

Connected and disconnected graphs

In addition to the distinction between directed and undirected graphs, the relationship between the graphs must also be considered:

  • connected graphs:
    Any node can be reached from any node pair. A graph in which a node cannot be reached due to the direction of the edges is called weakly connected. If all nodes can also be reached taking into account the directions of the edges, one speaks of a strongly connected graph.
  • disconnected graphs:
    If the graph has isolated nodes or groups of nodes, i.e. if not every node can be reached, then the graph is not connected.

Weighted and unweighted graphs

Another difference is weighted and unweighted graphs:

  • weighted graph:
    The lengths of the individual edges are different and must be taken into account.
  • unweighted graph:
    The edge lengths between the nodes are the same or the length does not matter.

Nodal degree in graphs

The node degree indicates the number of incoming or outgoing edges at a node point. Here, too, a distinction is made between directed and undirected graphs.

Nodal degree in directed graphs

In the case of directed graphs, i.e. those whose edges only allow certain directions, a distinction must be made between the input degree and the output degree. The degree of entry denotes the number of incoming edges, the degree of output the number of outgoing edges.

The entry level is mentioned first, and the exit level as the second. If a node has no incoming edges but only outgoing edges, then this is referred to as the source. Nodes that have no outgoing edges and only incoming are called sinks.

A directed graph with indication of the node degree could look like this:

Nodal degree for undirected graphs

In the case of undirected graphs, the direction of the edges is irrelevant. Therefore, no distinction is made between entrance and exit degrees. The nodal degree therefore indicates the number of all edges adjoining the nodal point. The nodes are therefore also referred to as neighboring nodes.

It could look like this:

Application of graph theory

The findings of graph theory can be used for a variety of problem solutions. A typical example is the familiar one "Problem of the traveling salesman".

The representative of "Glasklar AG" would like to visit potential new customers in various cities in order to prepare contracts for future business relationships. The aim is to find the most effective route possible - on the condition that each location can only be visited once and that it arrives back in its home town at the end. Represented as a graph, this could look like this:

Various methods are available to solve this problem, in particular algorithms that allow the best possible route to be found with as little effort as possible.

These are for example:

Practice questions