Description: An undirected graph is a mathematical structure composed of a set of nodes (or vertices) and a set of edges (or links) that connect pairs of nodes. Unlike directed graphs, where edges have a specific direction indicating a flow of information or relationship, in an undirected graph, edges do not have a defined direction, implying that the relationship between nodes is bidirectional. This characteristic allows for the representation of symmetric relationships, such as those found in social networks, where the connection between two entities is mutual. Undirected graphs are fundamental in graph theory, an area of mathematics and computer science that studies the properties and applications of these structures. Their visual representation is often intuitive, as nodes are drawn as points and edges as lines connecting them, facilitating the understanding of the underlying structure. This simplicity in representation makes undirected graphs widely used in various disciplines, from social sciences to computer science, to model and analyze complex systems.
History: The concept of graphs dates back to 1736 when Swiss mathematician Leonhard Euler solved the famous Königsberg bridge problem, which involved finding a path that crossed each bridge exactly once. This work laid the foundations of graph theory. Throughout the 20th century, graph theory developed significantly, with contributions from mathematicians like Paul Erdős and László Lovász, who explored properties and applications of graphs, including undirected ones.
Uses: Undirected graphs are used in various applications, such as representing social networks, where nodes represent users and edges represent relationships. They are also applied in biology to model interactions between species, in computer science to optimize routes in networks, and in network theory to analyze the connectivity of complex systems.
Examples: An example of an undirected graph is the social network model of Facebook, where users are nodes and friendships are edges. Another example is the graph representing connections between cities on a map, where cities are nodes and roads are edges connecting these cities.
