CS100R - Cornell University

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

  • The Rhetorical Triangle - Quia

    The Rhetorical Triangle - Quia

    Final thoughts + Remember that the rhetorical triangle is not a recipe or a guideline for writing; it is a way of looking at a situation. + Rhetorical situation is a specific (given) moment in which you ca use the...
  • Discover Colorado Beth Oehlerts, Colorado State University Libraries,

    Discover Colorado Beth Oehlerts, Colorado State University Libraries,

    Events=>Disaster: Wichita State University Plane Crash . October 2,1970. A Martin 404 twin-engine aircraft took off from Wichita, Kansas, carrying the Wichita State University (WSU) football team, coaches, and VIP supporters. Pilot Danny Crocker and copilot Ronald Skipper did not...
  • Cultural and symbolic dynamics

    Cultural and symbolic dynamics

    The basic economy of these systems has, in spite of its ideographic character, structural similarities with the alphabetic systems. In Japan and Korea mixed systems were created. In Japan phonetic syllables are designed by writing symbols and completed by Chinese...
  • The Bill of Rights & The Rights and Responsibilities of ...

    The Bill of Rights & The Rights and Responsibilities of ...

    Why was the Bill of Rights added to the U.S. Constitution? In several states, ratification (approval) for the Constitution was only obtained when Federalist supporters promised to add a Bill of Rights to guarantee individual rights. Anti-Federalists like Patrick Henry...
  • Analysis and Synthesis Algorithms 1 - csit-sun.pub.ro

    Analysis and Synthesis Algorithms 1 - csit-sun.pub.ro

    Antifuse-based FPGA fabrics: Actel. Flash-based FPGAs Antifuses Permanently programmed. Make a connection with electrical signal. More reliable than breaking a connection.
  • Considerations and Pitfalls in Geriatric Trauma

    Considerations and Pitfalls in Geriatric Trauma

    CONSIDERATIONS AND PITFALLS IN GERIATRIC TRAUMA ... when number of comorbid problems increase PITFALLS IN MANAGEMENT Pre-Hospital and initial resuscitation follows PHTLS and ATLS guidelines When checking airway remove and check for dental prosthesis during EMS Cervical spine protection indicated...
  • POSTMODERN ARTIST CASSANDRA VILLAVICENCIO MS.WATSON SEPTEMBER 23RD, 2016

    POSTMODERN ARTIST CASSANDRA VILLAVICENCIO MS.WATSON SEPTEMBER 23RD, 2016

    Ana put a beard on her face made from her husbands beard hair. This was used to represent the male image in her eyes. This was created to show the opposite perspective other than just the females. Piece #1. This...
  • Language learning in humans and machines: making connections ...

    Language learning in humans and machines: making connections ...

    2 for training: 24min, 490 English word types. Arapaho (~1000 speakers) 8 narratives, several speakers (40min) 1 for training: 18min, 233 English word types. No re-tuning of hyperparameters, except threshold for returning matches. National Institute for Japanese Language and Linguistics...