MATH 1007 Lecture Notes | Western University

MATH1007 lecture notes:

Week 1 lecture part a:

Graphs:

Directed and undirected:


Graphs: these are a kind of data structure.

They are made up of:

 Nodes/vertices (dots)
 Edges (lines connecting the dots)

Undirected graph:


- Edges

- nodes

,Items within undirected graphs:

- Edges can cross one another (go through lines)
- They can be looped (go back to itself)
- Multiple edges can join 2 nodes

Example using a real life graph:




- Uses nodes/edges to connect kevin bacon to a range of
actors through an undirected graph
- In the fewest no. of steps

Example of nodes/edges in use:

 Vertices = actors; edges = “acted in a movie with”
 Vertices = (train) stations; edges = connects to
 Species of evolution:
- Vertices = species; edges = “evolved from/to”
- Vertices = species; edges = “eats”
- Vertices = people; edges = “is a child of”
 Decision tree

, - Vertices = questions in the decision tree; edges = what
to do next


NOTE: you can have a range of different edges between
specific vertices

Some graphs and/or edges will have arrows and
some wont

These are either undirected or directed graphs

Arrows = directed
No arrows = undirected




Directed graph:



- You can have multiple arrows with
the same source of target.