# 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