# CS100R - Cornell University

Graph problems Prof. Ramin Zabih http://cs100r.cs.cornell.edu Administrivia Assignment 2 is due Friday Working Roombas are on the way (?) Quiz 3 on Tuesday 9/25 Coverage through next lecture Optional lecture topics are ready First one will be RDZ talking about graphs Graph questions are favorites for interviewers (at places like Google and Microsoft) 2 Some major graph problems Graph coloring Ensuring that radio stations dont clash Graph connectivity How fragile is the internet? Graph cycles Helping FedEx/UPS/DHL plan a route Planarity testing Connecting computer chips on a motherboard Graph isomorphism Is a chemical structure already known? 3 How to represent graphs? The adjacency matrix A is n by n

We will give each vertex a number 1..n A(r,c) == 1 when there is an edge between vertex r and vertex c Note that A(r,c) == A(c,r) 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0

1 0 0 0 1 0 0 0 V5 V3 V1 V4 V2 4 Graph coloring problem Given a graph and a set of colors {1..k} We want to assign each vertex a color Two adjacent vertices have different colors V5 V3 V1 V4 V2

5 Radio frequencies via coloring Make a graph where a station is a vertex Put an edge between two stations that clash I.e., if their signal areas overlap Any coloring is a non-clashing layout Can you prove this? What about vice-versa? C5 C3 C1 C4 C2 6 Verifying vs. finding One theme weve seen is that it can be easy to verify you have the right answer I.e., prove that your candidate is the solution Example: sorting If this is easy, there is a dumb algorithm Guess and verify Or: try everything Its not always easy to verify that an answer is correct Example: is this graph 4-colorable? 7 Graphs and paths Can you get from vertex V to vertex W?

Is there a route from one city to another? More precisely, is there a sequence of vertices {V,V1,V2,,Vk,W} such that every adjacent pair has an edge between them This is called a path A cycle is a path from V to V A path is simple if no vertex appears twice 8 Graph connectivity For any pair of nodes, is there a path between them? Basic idea of the Internet: you can get from any computer to any other computer This pair of nodes is called connected A set of nodes is connected if all pairs are A graph is connected if all nodes are connected Related question: if I remove an arbitrary node, is the graph still connected? Is the Internet intact if any 1 computer fails? 9 Connected components Even if all nodes are not connected, there will be subsets that are all connected Connected components V2 V1 V5 V4

V3 All nodes are connected Is this sufficient? Why not? 10 Blobs are components! A 0 0 0 0 0 0 0 B 0 0 0 0 0 0

0 0 0 C 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 D 0 0 0 0 0 0 0 0

E F G 0 0 0 0 0 0 0 H 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 C A B D F E G H 11

## Recently Viewed Presentations

• An ordinary 100 watt electric light bulb uses 100 joules of energy every second! EP = mgh height object raised (m) gravity (9.8 m/sec2) PE (joules) mass of object (g) EK = ½ mv2 mass of object (kg) velocity (m/sec)...
• Beck. Ellis. Beck developed a therapy to challenge the negative triad (beliefs) of the client. First, the client will be assessed to discover the severity of their condition. The therapist will establish a baseline (or starting point), prior to treatment,...
• Nurse Planner - RN with BSN accountable for planning, implementation, & evaluation of Continuing Nursing Education (CNE) activities. Primary Nurse Planner - RN with BSN accountable for provider unit operations and liaison with accredited approver. Approved Provider Unit - the...
• Teachable Unit: Population Growth Preclass Learning Outcome(s) Know how to define a population. Know that density is one way of measuring changes in a population. Activity/assessment Reading/lecture on population Clicker question or online quiz for self-assessment Time Pop.
• MapReduce Algorithm Design Patterns. In-mapper combining, where the functionality of the combiner is moved into the mapper. The related patterns "pairs" and "stripes" for keeping track of joint events from a large number of observations.
• * * Alcatel-Lucent AT&T Bigband Networks CableLabs Cisco Systems DTS Ericsson ETRI Huawei IneoQuest Technologies Intel JDSU Juniper LG Electronics Microsoft Motorola Nagravision NEC Corporation of America Nielsen Company Nokia Siemens Networks Philips Consumer Electronics Qwest RGB Networks Rogers Wireless...
• Tips for Participating in an Elluminate Live! Session. Get your computer audio-ready and test your audio immediately after logging in. Always follow the moderator's lead; Stay focused on the content . Wait for moderator's prompt/permission to speak audibly. Also, use...
• กรอบการประเมินผลตัวชี้วัด การพัฒนาคุณภาพการบริหารจัดการภาครัฐ สำหรับสถาบันอุดมศึกษา ปีงบประมาณ พ.ศ. 2553 * * * * 2551 2550 น้ำหนัก ...