Brainscape's Knowledge GenomeTM

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


See full index

a level further maths decision > Chapter 2 Graphs and Networks > Flashcards

Chapter 2 Graphs and Networks Flashcards

1
Q

What is a graph?

A

A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs)

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

What is a graph where each edge has a numbers associated with it called?

A

Weighted graph or a Network

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

What is a weighted graph/network?

A

A graph withy numbers associated with each edge

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

In a weighted graph, what are the numbers usually called?

A

Its weight

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

What is a vertex?

A

A point in the graph

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

What are vertices sometimes called?

A

Nodes

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

What is an edge?

A

A line segment joining vertices

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

What is the other word for edge?

A

Arc

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

What do you need to be careful about with networks?

A

They aren’t usually drawn to scale
As a result the shortest path may not be the obvious path

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

That is the list of vertices called?

A

Vertex set

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

What is the list of edges called?

A

The edge set

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

What is the vertex set?

A

The list of vertices

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

What is the edge set?

A

The list of edges

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

What is a subgraph?

A

A subgraph is part of the original graph

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

When is a vertex and an edge incident?

A

If they are connected

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

What is the degree of a vertex?

A

The number of edges incident to a particular vertex

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

What are the other ways to say degree of a vertex?

A

Valency of a vertex
Order of a vertex

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

What does even degree mean?

A

The vertex has an even number of incident edges
The degree of vertex will be an even number

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

What deos odd degree mean?

A

The vertex has an odd number of incident edges
The degree of vertex will be an odd number

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

What phrase can be used to say: The vertex has an even number of incident edges?

A

Even degree

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

What phrase can be used to say: The vertex has an odd number of incident edges?

A

Odd degree

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

What is a walk?

A

A walk is a route through a graph along edges from 1 vertex to the next

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

What is a path?

A

A path is 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
24
Q

What is a trail?

A

A trail is 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
25
Q

What is a cycle?

A

A cycle is a path in which the end vertex is the same as the start vertex

26
Q

What is a hamiltonian cycle?

A

A hamiltonian cycle is a cycle that includes every vertex

27
Q

What is the difference between a path and a trail?

A

A path doesn’t visit any node more than once
A trail doesn’t visit any edge more than once

28
Q

What does it mean if 2 vertices are connected?

A

2 vertices are connected if there is a path between them

29
Q

What does it mean if a graph is connected?

A

A graph is connected if there is at least 1 path joining any 2 vertices in the graph

30
Q

What is a loop?

A

A loop is an edge that starts and finishes at the same vertex

31
Q

What is a simple graph?

A

A simple graph is a graph in which there are no loops and there is at most 1 edge connecting any pair of vertices

32
Q

What is a directed graph?

What is it often abbreviated to?

A

A graph in which the edges have a direction associated with them

Digraph

33
Q

What do you know about degrees of vertices in a undirected graph?

A

The sum of the degrees of the vertices = 2 x the number of edges

34
Q

What do you know about the number of odd vertices?

What is this result known as?

A

There must be an even amount of odd vertices

This result is known as Euler’s handshaking lemma

35
Q

What is a lemma?

A

A lemma is a mathematical fact used as a stepping stone to more important results

36
Q

What are the special graphs that you need to know?

A

A tree
A spanning tree
A complete graph
Isomorphic graphs

37
Q

What is a tree?

A

A tree is a connected graph with no cycles

38
Q

What is a spanning tree?

A

A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree

39
Q

What is a complete graph?

A

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

40
Q

What is an isomorphic graph?

A

Isomorphic graphs are graphs which show the same information but may be drawn differently

41
Q

What is the special notation for complete graphs?

A
42
Q

What do you know must be true for isomorphic graphs?

A

They must have the same number of vertices of the same degrees
These vertices must also be connected together in the same way

43
Q

What can you use to represent graphs and networks?

A

Adjacent matrices

44
Q

What does an adjacent matrix do?

A

Provided information about the connections between the vertices in a graph

45
Q

If you have a adjacent matrix which has all 0s in its leading diagonal what do you know is true?

A

There are no loops

46
Q

If you have a adjacent matrix which has a number greater than 1 what do you know is true?

A

Those 2 points share more than 1 arc between them

47
Q

What is a matrix associated with a weight graph called?

A

A distance matrix

48
Q

When do you use a distance matrix?

A

When you have a network

49
Q

What do you know about a distance matrix of a non directed network?

A

It will be symmetrical around the matrices leading diagonal

50
Q

What do you do in the distance matrix if there is no edge between 2 vertices?

A

You put a dash

51
Q

What is a planar graph?

A

A planar graph is a graph that can be drawn in a place such that no 2 edges meet except at a vertex

52
Q

Give an example of a planar graph?

A
53
Q

What fact does the planetary algorithm rely on?

A

That there is a hamiltonian cycle

54
Q

State the planetary algorithm

A
55
Q

What really helps when implementing the planetary algorithm?

A

Draw a regular polygon

56
Q

How does the planetary algorithm generally work?

A

Generally this works by: if edges crosses inside the hamiltonian cycle then they will both cross outside it. So the algorithm tries to separate all edges into a category that the cross or they don’t. Therefore 1 of each pair can be directed outside the nodes

57
Q

What does a completed planetary algorithm question look like?

A

A completed answer should be the table of edges
You only draw the isomorphic graph is asked

58
Q

What will stop the planetary algorithm?

A

There not being a hamiltonian cycle
There being 2 outside edges crossing

59
Q

What happens if there ate 2 outside edges crossing?
Why?

A

The graph isn’t planar
For there to be 2 outside edges crossing then if they are inside they will cross an inside edge by definition. So there is no possible solution

60
Q

What happens for the simplex algorithm if there isn’t a hamiltonian cycle?

A

The algorithm is inconclusive

a level further maths decision (9 decks)

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