Define a graph and provide two examples of real-world applications where graphs are commonly used.

Sure! A graph is a mathematical structure that consists of a set of vertices (also known as nodes) and a set of edges (also known as arcs) that connect these vertices. It is used to represent relationships or connections between different entities.

Example 1: Social Networks One common real-world application of graphs is in social networks. In platforms like Facebook or LinkedIn, each person is represented as a vertex, and the connections between people (friendships or professional relationships) are represented as edges. This allows for analyzing and visualizing the social connections between individuals.

Example 2: Transportation Networks Another example of a real-world application of graphs is in transportation networks. In this case, the vertices represent locations such as cities or intersections, and the edges represent the roads or routes connecting these locations. Graphs are used to model and optimize transportation systems, such as finding the shortest path between two locations or determining the most efficient routes for delivery services.

These are just two examples, but graphs have a wide range of applications in various fields, including computer science, biology, logistics, and many others.