Chapter 9 - Graphs and Trees Flashcards

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

What is a graph?

A

A mathematical structure that models the relationship between pairs of objects.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is graph theory?

A

The underlying mathematical principles behind the use of graphs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an arc?

A

A join or relationship between two nodes - also known as an edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a vertex/vertices?

A

An object in a graph - also known as a node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a weighted graph?

A

A graph that has a data value labelled on each edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is an undirected graph?

A

A graph where the relationship between vertices is two way.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a directed graph?

A

A graph where the relationship between vertices is one way.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is latency?

A

The time delay that occurs when transmitting data between devices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Can you name three of the seven uses of graphs?

A
Human networks
Transport networks
The internet and web
Computer science
Medical research
Project management
Game theory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is an adjacency list?

A

A data structure that stores a list of nodes with their adjacent nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is an adjacency matrix?

A

A data structure set-up as a two dimensional array or grid that shows whether there is an edge between each pair of nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a tree?

A

A data structure similar to a graph, with no loops.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a node?

A

An object in a graph - also known as a vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is an edge?

A

A join of relationship between nodes - also known as an arc.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define root.

A

The starting node in a rooted tree structure from which all other nodes branch off.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define parent.

A

A type of node in a tree where there are further nodes below it.

17
Q

What is a child?

A

A node in a tree that has nodes above it in the hierarchy.

18
Q

What is a leaf?

A

A node that does not have any other nodes beneath it.

19
Q

What is a binary tree?

A

A tree where each node can only have up to two child nodes attached to it.