Graphs Flashcards
What does a graph consist of?
A number of nodes/vertices and edges/arcs
What is an undirected graph?
A graph where the edges are bidirectional
What is an directed graph/digraph?
Where the edges in a graph are all one way
What are the two ways graphs can be represented?
- Adjacency lists
- Adjacency matrix
How do we know a graph is undirected by looking at an adjacency matrix?
The matrix is symmetrical
How is an unweighted graph shown in an adjacency matrix?
1’s represent where there is an edge between nodes
0’s represent where there is no connection between nodes
When would be the most appropriate to use a an adjacency matrix?
- When the graph is dense
- When edges are frequently added
- If the data is regularly tested
When would be the most appropriate to use a an adjacency list?
- When the graph is sparse
- When the data is frequently changed
How can an adjacency list be implemented?
By creating a list of dictionaries. The key being the node and the value, the edge weight.
How can an adjacency matrix be implemented?
By creating a two dimensional array
What is the degree of a vertex?
The number of neighbours it has
What is a graph?
A mathematical structure that models the relationship between pairs of objects
What does adjacency mean?
It means next to
What is a simple graph?
An undirected graph that has no loops and no more than one edge between any two vertices
What is a sparse graph?
Where the number of nodes is larger than the number of edges
