Graph theor 1.4 Applications of graphs Graphs are the most useful mathematical objects in computer science. You can model an enormous number of real-world systems and phenomena using graphs. Once you've created such a model, you can tap the vast store of theorems about graphs to gain insight into the system you're modeling. Here are some practical situations where graphs arise Data Structures Each vertex represents a data object. There is a directed edge from one object to another if the first contains a pointer or reference to the second Attraction Each vertex represents a person, and each edge represents a romantic attrac- tion. The graph could be directed to model the unfortunate asymmetries Airline Connections Each vertex represents an airport. If there is a direct flight be- tween two airports, then there is an edge between the corresponding vertices. These graphs often appear in airline magazines The Web Each vertex represents a web page. Directed edges between vertices represent People often put numbers on the edges of a graph, put colors on the vertices, or add other ornaments that capture additional aspects of the phenomenon being modeled. For example, a graph of airline connections might have numbers on the edges to indicate the duration of the corresponding flight. The vertices in the attraction graph might be colored to indicate the person s gender 1.5 Some Common graphs Some graphs come up so frequently that they have names. The complete graph on n vertices, also called Kn, has an edge between every pair of vertices. Here is K The empty graph has no edges at all. Here is the empty graph on 5 verticesGraph Theory 5 1.4 Applications of Graphs Graphs are the most useful mathematical objects in computer science. You can model an enormous number of real­world systems and phenomena using graphs. Once you’ve created such a model, you can tap the vast store of theorems about graphs to gain insight into the system you’re modeling. Here are some practical situations where graphs arise: Data Structures Each vertex represents a data object. There is a directed edge from one object to another if the first contains a pointer or reference to the second. Attraction Each vertex represents a person, and each edge represents a romantic attrac￾tion. The graph could be directed to model the unfortunate asymmetries. Airline Connections Each vertex represents an airport. If there is a direct flight be￾tween two airports, then there is an edge between the corresponding vertices. These graphs often appear in airline magazines. The Web Each vertex represents a web page. Directed edges between vertices represent hyperlinks. People often put numbers on the edges of a graph, put colors on the vertices, or add other ornaments that capture additional aspects of the phenomenon being modeled. For example, a graph of airline connections might have numbers on the edges to indicate the duration of the corresponding flight. The vertices in the attraction graph might be colored to indicate the person’s gender. 1.5 Some Common Graphs Some graphs come up so frequently that they have names. The complete graph on n vertices, also called Kn, has an edge between every pair of vertices. Here is K5: The empty graph has no edges at all. Here is the empty graph on 5 vertices: