Graphs Flashcards Preview

Paper 1 - Computer Science > Graphs > Flashcards

Flashcards in Graphs Deck (17)
Loading flashcards...
1

What does a graph consist of?

A number of nodes/vertices and edges/arcs

2

What is an undirected graph?

A graph where the edges are bidirectional

3

What is an directed graph/digraph?

Where the edges in a graph are all one way

4

What are the two ways graphs can be represented?

- Adjacency lists
- Adjacency matrix

5

How do we know a graph is undirected by looking at an adjacency matrix?

The matrix is symmetrical

6

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

7

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

8

When would be the most appropriate to use a an adjacency list?

- When the graph is sparse
- When the data is frequently changed

9

How can an adjacency list be implemented?

By creating a list of dictionaries. The key being the node and the value, the edge weight.

10

How can an adjacency matrix be implemented?

By creating a two dimensional array

11

What is the degree of a vertex?

The number of neighbours it has

12

What is a graph?

A mathematical structure that models the relationship between pairs of objects

13

What does adjacency mean?

It means next to

14

What is a simple graph?

An undirected graph that has no loops and no more than one edge between any two vertices

15

What is a sparse graph?

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

16

What is a dense graph?

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

17

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