# Introduction to Graph Algorithms

This article provides an introduction to graph algorithms, including a definition of what a graph is and an overview of common terms. It also includes information on an upcoming exam and assignment for a CS1114 course taught by Prof Noah Snavely at Cornell University.

• Uploaded on | 0 Views
• cristal

## About Introduction to Graph Algorithms

PowerPoint presentation about 'Introduction to Graph Algorithms'. This presentation describes the topic on This article provides an introduction to graph algorithms, including a definition of what a graph is and an overview of common terms. It also includes information on an upcoming exam and assignment for a CS1114 course taught by Prof Noah Snavely at Cornell University.. The key topics included in this slideshow are Graph algorithms, vertices, edges, CS1114, exam preparation,. Download this presentation absolutely free.

## Presentation Transcript

1. Graph algorithms Prof. Noah Snavely CS1114 http://www.cs.cornell.edu/courses/cs1114

2. 2 Administrivia Assignment 2 is out Second part due this Friday by 5pm Signup slots are up First prelim will be next week Thursday, March 2, in class

3. 3 What is a graph? Loosely speaking, a set of things that are paired up in some way Precisely, a set of vertices V and edges E Vertices sometimes called nodes An edge (or link) connects a pair of vertices V1 V2 V3 V4 V5 V = { V1, V2, V3, V4, V5 } E = { (V1,V3), (V2,V5), (V3,V4) }

4.

5.

7. 7 Hamiltonian & Eulerian cycles Two questions that are useful for problems such as mailman delivery routes Hamiltonian cycle: A cycle that visits each vertex exactly once (except the start and end) Eulerian cycle: A cycle that uses each edge exactly once

8. Hamiltonian & Eulerian cycles 8 V5 V1 V2 V4 V3 V10 V6 V7 V9 V8 Is it easier to tell if a graph has a Hamiltonian or Eulerian cycle?

9. Travelling Salesman Problem For a complete, weighted graph Find the cycle that visits all vertices with the lowest total cost 9

10. 10 Planarity testing A graph is planar if you can draw it without the edges crossing Its OK to move the edges or vertices around, as long as edges connect the same vertices V1 V2 V3 V4 V5

11. 11 Is this graph planar? V1 V2 V3 V4 V5 V6 Can you prove it?

12. 12 Four-color theorem Any planar graph can be colored using no more than 4 colors

13. Small world phenomenon (Six degrees of separation) How close together are nodes in a graph (e.g., whats the average number of hops connecting pairs of nodes?) 13 Milgrams small world experiment: Send postcard to random person A in Omaha; task is to get it to a random person B in Boston If A knows B, send directly Otherwise, A sends to someone A knows who is most likely to know B People are separated by 5.5 links on average

14. 14 Connected components Even if all nodes are not connected, there will be subsets that are all connected Connected components Component 1: { V1, V3, V5 } Component 2: { V2, V4 } V5 V4 V1 V3 V2

15.

16. 16 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 A C B D F E H G

17. 17 Finding blobs 1. Pick a 1 to start with, where you dont know which blob it is in When there arent any, youre done 2. Give it a new blob color 3. Assign the same blob color to each pixel that is part of the same blob

18. 18 Finding components 1. Pick a 1 to start with, where you dont know which component it is in When there arent any, youre done 2. Give it a new component color 3. Assign the same component color to each pixel that is part of the same component Basic strategy: color any neighboring 1s, have them color their neighbors, and so on