Chapter 3 Graphs Our focus in this book is on problems with a discrete avor Just as continuous mathematics is concerned with certain basic structures such as real numbers vectors and matrices discrete mathematics has developed basic combinatorial structures that lie at the heart of the subject One of the most fundamental and expressive of these is the graph The more one works with graphs the more one tends to see them ev erywhere Thus we begin by introducing the basic de nitions surrounding graphs and list a spectrum of different algorithmic settings where graphs arise naturally We then discuss some basic algorithmic primitives for graphs be ginning with the problem of connectivity and developing some fundamental graph search techniques 3 1 Basic De nitions and Applications Recall from Chapter 1 that a graph G is simply a way of encoding pairwise relationships among a set of objects it consists of a collection V of nodes and a collection E of edges each of which joins two of the nodes We thus represent an edge e E as a two element subset of V e u v for some u v V where we call u and v the ends of e Edges in a graph indicate a symmetric relationship between their ends Often we want to encode asymmetric relationships and for this we use the closely related notion of a directed graph A directed graph G cid 3 consists of a set of nodes V and a set of directed edges E cid 3 Each e cid 3 E cid 3 is an ordered pair u v in other words the roles of u and v are not interchangeable and we call u the tail of the edge and v the head We will also say that edge e cid 3 leaves node u and enters node v 74 Chapter 3 Graphs When we want to emphasize that the graph we are considering is not directed we will call it an undirected graph by default however the term graph will mean an undirected graph It is also worth mentioning two warnings in our use of graph terminology First although an edge e in an undirected graph should properly be written as a set of nodes u v one will more often see it written even in this book in the notation used for ordered pairs e u v Second a node in a graph is also frequently called a vertex in this context the two words have exactly the same meaning Examples of Graphs Graphs are very simple to de ne we just take a collec tion of things and join some of them by edges But at this level of abstraction it s hard to appreciate the typical kinds of situations in which they arise Thus we propose the following list of speci c contexts in which graphs serve as important models The list covers a lot of ground and it s not important to remember everything on it rather it will provide us with a lot of useful ex amples against which to check the basic de nitions and algorithmic problems that we ll be encountering later in the chapter Also in going through the list it s useful to digest the meaning of the nodes and the meaning of the edges in the context of the application In some cases the nodes and edges both corre spond to physical objects in the real world in others the nodes are real objects while the edges are virtual and in still others both nodes and edges are pure abstractions 1 Transportation networks The map of routes served by an airline carrier naturally forms a graph the nodes are airports and there is an edge from u to v if there is a nonstop ight that departs from u and arrives at v Described this way the graph is directed but in practice when there is an edge u v there is almost always an edge v u so we would not lose much by treating the airline route map as an undirected graph with edges joining pairs of airports that have nonstop ights each way Looking at such a graph you can generally nd them depicted in the backs of in ight airline magazines we d quickly notice a few things there are often a small number of hubs with a very large number of incident edges and it s possible to get between any two nodes in the graph via a very small number of intermediate stops Other transportation networks can be modeled in a similar way For example we could take a rail network and have a node for each terminal and an edge joining u and v if there s a section of railway track that goes between them without stopping at any intermediate terminal The standard depiction of the subway map in a major city is a drawing of such a graph 2 Communication networks A collection of computers connected via a communication network can be naturally modeled as a graph in a few 3 1 Basic De nitions and Applications 75 different ways First we could have a node for each computer and an edge joining u and v if there is a direct physical link connecting them Alternatively for studying the large scale structure of the Internet people often de ne a node to be the set of all machines controlled by a single Internet service provider with an edge joining u and v if there is a direct peering relationship between them roughly an agreement to exchange data under the standard BGP protocol that governs global Internet routing Note that this latter network is more virtual than the former since the links indicate a formal agreement in addition to a physical connection In studying wireless networks one typically de nes a graph where the nodes are computing devices situated at locations in physical space and there is an edge from u to v if v is close enough to u to receive a signal from it Note that it s often useful to view such a graph as directed since it may be the case that v can hear u s signal but u cannot hear v s signal if for example u has a stronger transmitter These graphs are also interesting from a geometric perspective since they roughly correspond to putting down points in the plane and then joining pairs that are close together Information networks The World Wide Web can be naturally viewed as a directed graph in which nodes correspond to Web pages and there is an edge from u to v if u has a hyperlink to v The directedness of the graph is crucial here many pages for example link to popular news sites but these sites clearly do not reciprocate all these links The structure of all these hyperlinks can be used by algorithms to try inferring the most important pages on the Web a technique employed by most current search engines The hypertextual structure of the Web is anticipated by a number of information networks that predate the Internet by many decades These include …