Graphs Flashcards Preview

Paper 1 - Computer Science > Graphs > Flashcards

Flashcards in Graphs Deck (17)
Loading 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


What is a dense graph?

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


What are some applications of graphs?

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
- web pages and links