Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Further Maths - Decision > Decision C2 - Graphs and networks > Flashcards

Decision C2 - Graphs and networks Flashcards

1
Q

What is a graph?

A

A graph consists of points which are connected by lines

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are points also referred to as?

A

Vertices or nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are lines also referred to as?

A

Edges or arcs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a weighted graph?

A

A graph with a number associate with each edge (it’s weight)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a weighted graph also known as?

A

A network

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a subgraph?

A

A graph each of whose vertices and edges belong to the original graph. It is part of the original graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the degree of a vertex?

A

The number of edges incident to it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the degree of a vertex also known as?

A

Valency or order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a walk?

A

A route through a graph along edges from one vertex to the next

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a path?

A

A walk in which no vertex is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a trail?

A

A walk in which no edge is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a cycle?

A

A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a hamiltonian cycle?

A

A cycle that includes every vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What makes two vertices connected?

A

If there is a path between them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What makes a graph connected?

A

If all it’s vertices are connected

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a loop?

A

An edge that starts and finishes at the same vertex

17
Q

What is a simple graph?

A

A graph with no loops and at most one edge connecting any pair of vertices

18
Q

What are directed graphs also known as?

A

Digraph

19
Q

What makes a graph a directed graph?

A

If they have a direction associated with them

20
Q

What is Euler’s handshaking lemma?

A

In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges. As a result, the number of odd nodes must be even

21
Q

What is a tree?

A

A connected graph with no cycles

22
Q

What is a spanning tree of a graph?

A

A subgraph which includes all the vertices of the original graph and is also a tree

23
Q

What is a complete graph?

A

A graph in which every vertex is directly connected by a single edge to each of the other vertices

24
Q

What is an isomorphic graph?

A

Graphs which show the same information but mat be drawn differently

25
Q

Describe an adjacency matrix

A

Each entry in an adjacency matrix describes the number of arcs joining the corresponding vertices

26
Q

Describe a distance matrix

A

Each entry represents the weight of each arc, not the number of arcs

27
Q

What is a planar graph?

A

One that can be drawn such that no 2 edges meet except at a vertex

28
Q

When is it appropriate to use the planarity algorithm?

A

When it contains a hamiltonian cycle

Further Maths - Decision (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions