Graph theory: the basics

In short: A graph consists of nodes (points) and edges (connections between them) and abstractly describes relationships between objects. From social networks to road maps to computer networks, countless real systems can be modeled as graphs.

In more detail: Graph theory originated in the 18th century, when Leonhard Euler solved the famous Seven Bridges of Königsberg problem using abstract nodes and edges.

In detail

• Directed and undirected graphs: In directed graphs, edges have a direction, as with one-way streets, while in undirected graphs they connect nodes symmetrically.
• Weighted graphs: Edges can carry numerical values, such as distances or costs, enabling optimization problems like finding shortest paths.
• Degree of a node: The number of edges connected to a node shows how strongly connected that node is.
• Trees as a special case: A tree is a connected graph without cycles and forms the basis for many data structures in computer science.
• Shortest-path algorithms: Methods like Dijkstra’s algorithm efficiently find the cheapest route between two nodes in a weighted graph.
• Real-world applications: Navigation systems, social networks, power grids, and the internet itself can all be described as giant graphs.
• Coloring problems: Coloring nodes or maps so that adjacent elements have different colors is a classic graph problem with practical applications (matrizen-grundlagen).