Graphs • Definition ○ A graph G = (V, E) consists of § a nonempty set V of vertices (or nodes) § and a set E of edges. ○ Each edge has either one or two vertices associated with it, called its endpoints. ○ An edge is said to connect its endpoints. • Example ○ This is a graph with four vertices and five edges. • Remarks ○ The graphs we study here are unrelated to graphs of functions studied in Chapter 2. ○ We have a lot of freedom when we draw a picture of a graph. ○ All that matters is the connections made by the edges, not the particular geometry depicted. ○ For example, the lengths of edges, whether edges cross, how vertices are depicted, and so on, do not matter ○ A graph with an infinite vertex set is called an infinite graph. ○ A graph with a finite vertex set is called a finite graph. We (following the text) restrict our attention to finite graphs. Graph Terminology • In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices. • Multigraphs may have multiple edges connecting the same two vertices. • When m different edges connect the vertices u and v, we say that {u,v} is an edge of multiplicity m. • An edge that connects a vertex to itself is called a loop. • A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices. • Example ○ This pseudograph has both multiple edges and a loop. Directed Graphs • Definition: ○ An directed graph (or digraph) G = (V, E) consists of § a nonempty set V of vertices (or nodes) § and a set E of directed edges (or arcs). ○ Each edge is associated with an ordered pair of vertices. ○ The directed edge associated with the ordered pair (u,v) is said to start at u and end at v. • Remark: ○ Graphs where the end points of an edge are not ordered are said to be undirected graphs. Some Terminology (continued) • Definition ○ A simple directed graph has no loops and no multiple edges. • Example ○ This is a directed graph with three vertices and four edges. • Definition ○ A directed multigraph may have multiple directed edges. ○ When there are m directed edges from the vertex u to the vertex v, ○ We say that (u,v) is an edge of multiplicity m. • Example ○ In this directed multigraph the multiplicity of (a,b) is 1 and the multiplicity of (b,c) is 2. Graph Models: Computer Networks • When we build a graph model, we use the appropriate type of graph to capture the important features of the application. • We illustrate this process using graph models of different types of computer networks. • In all these graph models, the vertices represent data centers and the edges represent communication links. • To model a computer network where we are only concerned whether two data centers are connected by a communications link, we use a simple graph. • This is the appropriate type of graph when we only care whether two data centers are directly linked (and not how many links there may be) and all communications links work in both directions. • To model a computer network where we care about the number of links between data centers, we use a multigraph. • To model a computer network with diagnostic links at data centers, we use a pseudograph, as loops are needed. • To model a network with multiple one-way links, we use a directed multigraph. • Note that we could use a directed graph without multiple edges if we only care whether there is at least one link from a data center to another data center. Graph Terminology: Summary • To understand the structure of a graph and to build a graph model, we ask these questions: ○ Are the edges of the graph undirected or directed (or both)? ○ If the edges are undirected, are multiple edges present that connect the same pair of vertices? ○ If the edges are directed, are multiple directed edges present? ○ Are loops present? Other Applications of Graphs • We will illustrate how graph theory can be used in models of: ○ Social networks ○ Communications networks ○ Information networks ○ Software design ○ Transportation networks ○ Biological networks • It’s a challenge to find a subject to which graph theory has not yet been applied. • Can you find an area without applications of graph theory? Examples of Collaboration Graphs • The Hollywood graph models the collaboration of actors in films. ○ We represent actors by vertices and we connect two vertices if the actors they represent have appeared in the same movie. ○ We will study the Hollywood Graph in Section 10.4 when we discuss Kevin Bacon numbers. • An academic collaboration graph models the collaboration of researchers who have jointly written a paper in a particular subject. ○ We represent researchers in a particular academic discipline using vertices. ○ We connect the vertices representing two researchers in this discipline if they are coauthors of a paper. ○ We will study the academic collaboration graph for mathematicians when we discuss Erdős numbers in Section 10.4. Transportation Graphs • Graph models are extensively used in the study of transportation networks. • Airline networks can be modeled using directed multigraphs where ○ airports are represented by vertices ○ each flight is represented by a directed edge from the vertex representing the departure airport to the vertex representing the destination airport • Road networks can be modeled using graphs where ○ vertices represent intersections and edges represent roads. ○ undirected edges represent two-way roads and directed edges represent one-way roads. Biological Applications • Graph models are used extensively in many areas of the biological science. • We will describe two such models, one to ecology and the other to molecular biology. • Niche overlap graphs model competition between species in an ecosystem • Vertices represent species and an edge connects two vertices when they represent species who compete for food resources. • Example: This is the niche overlap graph for a forest ecosystem with nine species. • We can model the interaction of proteins in a cell using a protein interaction network. • In a protein interaction graph, vertices represent proteins and vertices are connected by an edge if the proteins they represent interact. • Protein interaction graphs can be huge and can contain more than 100,000 vertices, each representing a different protein, and more than 1,000,000 edges, each representing an interaction between proteins • Protein interaction graphs are often split into smaller graphs, called modules, which represent the interactions between proteins involved in a particular function. • Example: This is a module of the protein interaction graph of proteins that degrade RNA in a human cell.
