# Graphs Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What does a graph consist of?

A

A number of nodes/vertices and edges/arcs

2
Q

What is an undirected graph?

A

A graph where the edges are bidirectional

3
Q

What is an directed graph/digraph?

A

Where the edges in a graph are all one way

4
Q

What are the two ways graphs can be represented?

A

5
Q

How do we know a graph is undirected by looking at an adjacency matrix?

A

The matrix is symmetrical

6
Q

How is an unweighted graph shown in an adjacency matrix?

A

1’s represent where there is an edge between nodes

0’s represent where there is no connection between nodes

7
Q

When would be the most appropriate to use a an adjacency matrix?

A
• When the graph is dense
• When edges are frequently added
• If the data is regularly tested
8
Q

When would be the most appropriate to use a an adjacency list?

A
• When the graph is sparse

- When the data is frequently changed

9
Q

How can an adjacency list be implemented?

A

By creating a list of dictionaries. The key being the node and the value, the edge weight.

10
Q

How can an adjacency matrix be implemented?

A

By creating a two dimensional array

11
Q

What is the degree of a vertex?

A

The number of neighbours it has

12
Q

What is a graph?

A

A mathematical structure that models the relationship between pairs of objects

13
Q

A

It means next to

14
Q

What is a simple graph?

A

An undirected graph that has no loops and no more than one edge between any two vertices

15
Q

What is a sparse graph?

A

Where the number of nodes is larger than the number of edges

16
Q

What is a dense graph?

A

Where the number of edges is larger than the number of nodes

17
Q

What are some applications of graphs?

A

Graphs can be used to represent:

• Computer networks, nodes representing devices and weighted edges representing the bandwidth between them
• States in a finite state machine