Courses

# Graphs and Graph Algorithms - PowerPoint Presentation, Algorithms, Engg. Notes | EduRev

## : Graphs and Graph Algorithms - PowerPoint Presentation, Algorithms, Engg. Notes | EduRev

``` Page 1

1

CSE 421: Intro Algorithms

Autumn 2012

Graphs and Graph Algorithms

Page 2

1

CSE 421: Intro Algorithms

Autumn 2012

Graphs and Graph Algorithms

Goals

Graphs: defns, examples, utility, terminology

Representation: input, internal

Three Algorithms:

Connected components

Bipartiteness

Topological sort

2

Page 3

1

CSE 421: Intro Algorithms

Autumn 2012

Graphs and Graph Algorithms

Goals

Graphs: defns, examples, utility, terminology

Representation: input, internal

Three Algorithms:

Connected components

Bipartiteness

Topological sort

2

4

Objects & Relationships

The Kevin Bacon Game:

Obj: Actors

Rel: Two are related if they've been in a movie together

Exam Scheduling:

Obj: Classes

Rel: Two are related if they have students in common

Traveling Salesperson Problem:

Obj: Cities

Rel: Two are related if can travel directly between them

Page 4

1

CSE 421: Intro Algorithms

Autumn 2012

Graphs and Graph Algorithms

Goals

Graphs: defns, examples, utility, terminology

Representation: input, internal

Three Algorithms:

Connected components

Bipartiteness

Topological sort

2

4

Objects & Relationships

The Kevin Bacon Game:

Obj: Actors

Rel: Two are related if they've been in a movie together

Exam Scheduling:

Obj: Classes

Rel: Two are related if they have students in common

Traveling Salesperson Problem:

Obj: Cities

Rel: Two are related if can travel directly between them

5

Graphs

An extremely important formalism for
representing (binary) relationships

Objects: "vertices," aka "nodes"

Relationships between pairs: "edges," aka
"arcs"

Formally, a graph G = (V, E) is a pair of sets,
V the vertices and E the edges

Page 5

1

CSE 421: Intro Algorithms

Autumn 2012

Graphs and Graph Algorithms

Goals

Graphs: defns, examples, utility, terminology

Representation: input, internal

Three Algorithms:

Connected components

Bipartiteness

Topological sort

2

4

Objects & Relationships

The Kevin Bacon Game:

Obj: Actors

Rel: Two are related if they've been in a movie together

Exam Scheduling:

Obj: Classes

Rel: Two are related if they have students in common

Traveling Salesperson Problem:

Obj: Cities

Rel: Two are related if can travel directly between them

5

Graphs

An extremely important formalism for
representing (binary) relationships

Objects: "vertices," aka "nodes"

Relationships between pairs: "edges," aka
"arcs"

Formally, a graph G = (V, E) is a pair of sets,
V the vertices and E the edges

6

Undirected Graph   G = (V,E)

1
2
10
9
8
3
4
5
6
7
11
12
13
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!