Chapter 9 - Graphs and Trees Flashcards
What is a graph?
A mathematical structure that models the relationship between pairs of objects.
What is graph theory?
The underlying mathematical principles behind the use of graphs.
What is an arc?
A join or relationship between two nodes - also known as an edge.
What is a vertex/vertices?
An object in a graph - also known as a node.
What is a weighted graph?
A graph that has a data value labelled on each edge.
What is an undirected graph?
A graph where the relationship between vertices is two way.
What is a directed graph?
A graph where the relationship between vertices is one way.
What is latency?
The time delay that occurs when transmitting data between devices.
Can you name three of the seven uses of graphs?
Human networks Transport networks The internet and web Computer science Medical research Project management Game theory
What is an adjacency list?
A data structure that stores a list of nodes with their adjacent nodes.
What is an adjacency matrix?
A data structure set-up as a two dimensional array or grid that shows whether there is an edge between each pair of nodes.
What is a tree?
A data structure similar to a graph, with no loops.
What is a node?
An object in a graph - also known as a vertex.
What is an edge?
A join of relationship between nodes - also known as an arc.
Define root.
The starting node in a rooted tree structure from which all other nodes branch off.
