CS 2800: Discrete Math Sept. 26, 2011LectureLecturer: David Kempe Scribe: Eunsol & June1 Directed v. Undirected GraphsToday we introduced directed and undirected graphs. Graphs are a very powerful representation in computerscience, as almost anything can be represented by graphs. Will provide examples of each kind and exploretypes of questions that can be answered.1.1 Examples of Undirected GraphsUndirected graphs have edges that represent symmetric relationships. Ie, if you are friends with someone,then they are friends with you. Examples naturally follow as:1. Friendship Networks2. Collaboration Networks3. Roads connecting cities4. Mathematical models5. Computer Networks1.2 Examples of Directed GraphsDirected graphs have edges that do not represent symmetric relationships. Eg, if Jane is better at chess thanBob, then Bob is not better at chess than Jane and the edge will be directed to represent that. Examplesfollow as:1. Sent Emails/ dialed phone calls2. Transportation Networks - airlines(jet stream), trains(one way tracks), etc3. Infection and Transmission of Disease - spread of epidemics4. Finite State Machines5. Predator and Prey Relationships6. Boss HierarchyNote: Any undirected graph can be turned into a directed graph, just represent each edge in the undirectedgraph with two directed edges in a directed graphNote: Depending on what you are representing, certain constraints will be properties of the representativegraph. For example, in predator-prey graphs, you would not expect a triangle. In a boss hierarchy graph,you would expect the graph to be a tree (ie, contain no cycles).11.3 QuestionsFor each of graphs, we can pose some interesting questions:Questions for undirected graphs:· Friendships: Who are the most influential people?· Collaboration networks: What are the most useful collaborations?· Roads between cities: What is the quickest path between city A and city B?· Mathematical models: How does an earthquake wave travel through the earth?· Computer Networks: How will your ip packet be routed?Questions for directed graphs:· Emails/phone calls: How does information travel?· Transportation networks - airlines, trains, etc: How should the planes be used to cover as many destinationsas possible?· Infection and transmission of disease - epidemics: If an epidemic, like swine flu, is starting, how can wechange the graph to minimize the infections?· Finite State Machines: What is the set of all possible solutions?· Predator and prey relationship: When will an animal’s food supply disappearing?· Boss hierarchy: How much redundancy is in a company’s management system?While these questions are application specific, they are, in essense, also examples of abstract cs problems.The following questions are not directly associated with a physical problem, but their solutions are handyin more advanced cs topics:· Cover a graph. Find a cover set such that for every node, at least one of its neighbors is in the cover set.· Find the shortest path that visits all nodes.· Color a map with as few colors as possible, such that no two neighboring countries have the same color.There is an advantage to studying abstract problems. Often times solving specific application problemsjust involves breaking down and transforming the application to fit into already studied abstract problemsand their solutions.Definition 1. Graph, Nodes, and EdgesA graph G = (V, E) consists of V , a set of nodes, and E, a set of edges. Where if nodes u, v ∈ V areconnected in the graph, there there exists edge e = (u, v) ∈ E.Corresponding to wether or not the graph G is un/directed, edges can be directed or undirected. Whendirected, e = (u, v) and e = (v, u) are different. When the graph is undirected, the two are equivalent, andif one direction exists in the graph, the other direction is implied.You may come across many more ways to name edges and nodes, especially when working on applications.However, the widely accepted convention is to name these as nodes and edges.convention alternativesnodes vertices, points, people, citiesedges lines, arcs, friendships, roads2So we have built up nodes and edges to create graphs, but we can attach more information. Edgescan have weights. For example in building a graph of cities and their connecting roads, the weights cancorrespond to distance between cities. For nodes, we can attach properties to the nodes, such as city size.Often times the more information the more involved the questions we can ask.Graphs have to be built in a way that reflects the problem. Suppose we have the issue of finding whichsets of chemicals produce dramatic reactions. We could take all chemicals as nodes and add an edge ifthe two connecting chemicals react. But chemical reactions are not linear. If I find a set of 3 chemicalsthat all pairwise react, the combination of all 3 may not cause a reaction. Similarly, there exists sets ofchemicals that will not react until a final ingrediant is added. Having a graph of the pairwise reactionswill not account for these. An immediate response is, well, build a graph to represent all combinations ofchemicals (a hypergraph). However, this should only be an absolute last resort(June: ”Personally, I havenever had to go that extreme.”) The caution is that, while intriguing, they quickly grow beyond computableand comprehensible bounds.A more likely complexity with graphs are self-edges.Definition 2. Self-edge, is an edge from a node, u, to itself. Ie., e = (u, u).A common example of self-edges is a website that links to itself. Consider page-rank, used to sort websitesreturned in Google searches. Page rank is roughly ranking websites by the number of pages that link to saidwebsite. Self-edges are easy to create and bump a primative page rank algorithm into more highly valuingwebsites with self-edges.Another complexity that can occur with the edges of a graph are multiple copies of an edge:Definition 3. Multigraph, if we allow multiple copies of edges and the number of copies is called the multi-plicity of the graph.In multigraph, there can be multiple edges connecting the same pair of nodes. Ie., e1= (u, v), e2= (u, v),e3= (u, v) are distinct, often by having different weights. In most cases, we implicitly assume graphs arenot multigraph.Often times the algorithms we can run over graphs depend on what type of graph we are dealing with,multi/non-multi, directed etc. We now provide some definitions that allow us to clarify in future what