Brainscape's Knowledge GenomeTM

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


See full index

D1 > Graphs and Networks > Flashcards

Graphs and Networks Flashcards

1
Q

What is a complete graph?

A

A graph where each node is connected by one arc to each other node

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

What is a node?

A

The blobs/dots

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

What is an arc?

A

The lines

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

What is a vertex?

A

The blobs/dots

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

What is an edge?

A

The lines

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

What are two terms for the lines in a graph?

A

Arcs and Edges

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

What are two terms for the blobs/dots in a graph?

A

Nodes and Vertices

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

What is a trail?

A

A walk where no edge appears more than once

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

What is a path?

A

A trail in which no vertices are 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 closed path that finishes at the same vertex that it started at

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

What classifies as a connected graph?

A

When all vertices are connected

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

What is a simple graph?

A

A graph with no loops, and no more than one edge connecting a pair of vertices

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

What is the degree/order of a vertex?

A

The number of edges connected to it

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

What is a digraph?

A

A graph with edges that have a specified direction (through arrows). Orders have no meaning in these graphs.

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

What is a tree?

A

A connected graph with no cycles

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

What is a network?

A

A graph with weights (numbers) associated with the edges

17
Q

Define a Eulerian graph

A

A connected graph with only even orders.

18
Q

Define a semi-Eulerian graph

A

A connected graph with only two odd orders

19
Q

Explain why an Eulerian graph can only have nodes of even order

A

In a closed trail containing every arc once, each time a node occurs it has an arc going in and an arc going out. Each node is therefore at the end of an even number of arcs, and therefore has an even order.

20
Q

What is Kn used for and what does it show?

A

It is the notation for a complete graph with n nodes

21
Q

What is a bipartite graph?

A

Two sets of nodes, with arcs only connecting one to the other and not connecting nodes within one set

22
Q

Analyse Kr,s in terms of being Eulerian and semi-Eulerian

A

If r and s are both even, it will be Eulerian. If r and s = 1 the graph is semi-Eulerian. If r or s = 2 and the other is an odd number, the graph is semi Eulerian.

23
Q

What does Kr,s show.

A

A bipartite graph, with r showing the number of nodes in one set and s showing the other.

24
Q

What is the total number of arcs in a Kr,s graph?

A

r x s

25
Q

What is the order of a Kn graph?

A

n-1

D1 (2 decks)

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