Brainscape's Knowledge GenomeTM

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


See full index

further maths > Graphs And Networks > Flashcards

Graphs And Networks Flashcards

1
Q

What does a graph consist of?

A

Vertices and nodes

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

What are nodes connected to?

A

Arcs

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

What is a graph named when it has a number associated with each edge?

A

A weighted graph or network

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

What is a subgraph?

A

Part of an original graph.

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

What is the degree of a vertex?

A

Number of arcs incident to it

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

What is another word for the degree of a vertex?

A

Valency or order

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

What is a walk?

A

A route through a graph along edges from one vertex to another

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

What is a path?

A

A walk in which no node is visited more than once.

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

What is a trail?

A

A walk in which no arc is visited more than once?

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

What is a cycle?

A

A walk in which the end node is the same as the start node

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

What is a Hamilton cycle?

A

A cycle which includes every node

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

What makes two nodes connected?

A

When an arc joins them

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

What makes a graph connected?

A

If all vertices are connected

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

What is a loop?

A

An arc that starts and finishes at the same node

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

What is a simple graph?

A

Where there are no loops and only one arc connects a pair of nodes

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

What is a graph called if it has directions associated with the arcs?

A

A digraph

17
Q

What is Euler’s handshaking lemma?

A

That any undirected graph has a some of degrees equal to 2x the edges. This means the number of odd nodes must be even.

18
Q

What is a tree?

A

A connected graph with no cycles

19
Q

What is a spanning tree?

A

A subgraph which includes all the vertices of the original graph.

20
Q

What is a complete graph?

A

A graph in which all nodes connect to all other nodes once

21
Q

What is an isomorphic graph?

A

Graphs which show the same information but are formed differently.

22
Q

What does each unit in an adjacency matrix represent?

A

The number of arcs joining a pair of nodes

23
Q

What does each unit represent in a distance matrix?

A

The weight of each arc

further maths (7 decks)

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