Description: An undirected graph is a data structure composed of a set of nodes (or vertices) and a set of edges that connect pairs of nodes. Unlike a directed graph, where edges have a specific direction indicating a sense of connection, in an undirected graph, edges have no direction, meaning the relationship between nodes is bidirectional. This characteristic allows nodes to connect to each other more flexibly, facilitating the representation of symmetric relationships. Undirected graphs are fundamental in graph theory and are used in various applications, from modeling social networks to representing maps and routes. In terms of notation, an undirected graph can be represented as G = (V, E), where V is the set of vertices and E is the set of edges. Edges are commonly represented as pairs of vertices, indicating that there is a connection between them. This structure allows for various operations, such as pathfinding, cycle detection, and identifying connected components, making it an essential tool in data analysis and algorithms.
History: The concept of graphs dates back to the 18th century when Swiss mathematician Leonhard Euler solved the famous Seven Bridges of Königsberg problem in 1736. This problem involved finding a path that crossed each bridge exactly once, leading to the formulation of what we now know as graph theory. Throughout the 20th century, graph theory developed significantly, becoming an important branch of mathematics and computer science. In particular, undirected graphs have been widely used in the study of networks and complex structures, being fundamental in the development of algorithms and mathematical models.
Uses: Undirected graphs have multiple applications in various fields. They are used in the representation of social networks, where nodes represent users and edges represent friendship relationships. They are also essential in network theory, where communication and transportation systems are modeled. In computer science, they are applied in search and optimization algorithms, such as Dijkstra’s algorithm for finding the shortest path in a graph. Additionally, they are used in biology to model interactions between species and in data research to analyze relationships between variables.
Examples: A practical example of an undirected graph is the representation of a road map, where cities are nodes and roads are edges connecting these cities. Another example is a graph representing a social network, where each person is a node and each friendship is an edge connecting two nodes. In computer science, undirected graphs are used in recommendation algorithms, where connections between users and products are analyzed to suggest relevant items.
