1.4.2. Graphs

Question 1

What is a graph?

Answer 1

Set of vertices or nodes connected by edges or arcs
Edges may be one way or two way

Question 2

What is a digraph of directed graph?

Answer 2

When edges in graph are all one way

Question 3

What does it mean for an edge to be adjacent?

Answer 3

If 2 vertices are connected by an edge they are adjacent

Question 4

How are undirected graphs drawn?

Answer 4

Order of pairs in edges don’t matter as edges go both ways
So drawn using straight lines with no arrowheads between vertices

Question 5

Difference between directed and undirected

Answer 5

Undirected edges go in both directions (no order or direction is specified)

Directed graphs - edges specify direction - order of edges matter

Question 6

How are directed graphs drawn!

Answer 6

Edges drawn using arrowheads MISS

Question 7

What does it mean by a graphs is weighted?

Answer 7

Each edge has a value representing a cost or relationship between vertices
Value can represent many things depending on context (time, distance money etc)

Question 8

What is a directed graph?

Answer 8

Notes

Question 9

Advantages

Answer 9

Very convenient
Very easy to work with
Adding edges is v simple

Question 10

Disadvantages for adjacent matrices

Answer 10

Large amounts of memory space can be wasted in graphs with many nodes but only a few edges as most of cells will be empty

Using static 2 dimensional arrays can be difficult to make changes adding and deleting nodes etc