Brainscape's Knowledge GenomeTM

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


See full index

Decisions > Chapter 2 > Flashcards

Chapter 2 Flashcards

1
Q

What is a graph?

A

A series of points connected by lines

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

What is a weighted graph

A

A graph with numbers associated to each edge

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

What is a vertex/node

A

A point in a graph

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

What is an edge/arc

A

A line segment joining vertices

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

What is a vertex set

A

A lost if vertices

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

What is the edge set

A

A lost of all the edges

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

What is a sub graph?

A

A part of the original graph

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

What is the degree/order of a vertex?

A

How many edges are incident to it

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 the graph from 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 where 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 where 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 where the end we’re is the same as the start one and no 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 which includes ever vertex

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

When are two vertices connected?

A

When two vertices are connected

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

When is. A grain connected?

A

When 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 which starts and ends at the same vertex

17
Q

What is a simple graph?

A

A graph with no loops which is connected

18
Q

What is a directed graph?

A

When the edges have a direction

19
Q

In an undirected graph what is the sum of degrees of the vertices equal to?

A

2x number if edges

20
Q

What is euler’s handshaking lemma ?

A

The number of odd vertices must be even

21
Q

What is a tree?

A

A connected graph with no cycles

22
Q

What is a spanning tree?

A

A tree which cintains all vertices

23
Q

What is a complete graph?

A

A graph where every vertex is direct,y. Connected to each other vertex by a single edge

24
Q

What is an isomorphic graph?

A

A graph with the same information which can be drawn differently

25
Q

What is a planar graph?

A

A planar graph can be drawn j. A plane with no two edges meeting

26
Q

What is the planetary algorithm?

A

Identify a Hamiltonian cycl
Draw a polygon with vertices to match those in the HC
Draw edges inside the polygon
Make a note if the edges inside
If they can’t be drawn without crossing draw them outside and label them outside
If all the edges can be drawn it is planar

Decisions (2 decks)

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