Brainscape's Knowledge GenomeTM

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


See full index

Discrete Mathematics > Exam 4 > Flashcards

Exam 4 Flashcards

1
Q

A vertex with no edges

A

Isolated Vertex

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

More than one edge connecting two vertices

A

Parallel Edges

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

The number of times that a vertex is an endpoint

A

Degree of a vertex

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

A graph with no loops or parallel edges

A

Simple Graph

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

A graph that can be partitioned into 2 sets for which every edge connects vertices in different sets

A

Bipartite Graph

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

The complete bipartite graph on m,n

A

Kmn

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

A maximal connected subgraph

A

Connected Component

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

A finite alternating sequence of adjacent vertices and edges

A

Walk

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

A walk that does not contain a repeated edge

A

Path

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

A path that does not contain a repeated vertex

A

Simple Path

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

A walk that begins and ends on the same vertex

A

Closed Walk

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

A closed walk that does not contain a repeated edge

A

Circuit

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

Graphs with a 1-1 function such that vertices x and y are joined by an edge and so are f(x) and f(y)

A

Isomorphic

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

1-1 function between two graphs

A

Isomorphism

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

A property of a graph that doesn’t change under isomorphism

A

Invariant

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

A circuit that does not have any other repeated vertex except the first and last

A

Simple Circuit

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

Circuit which contains every vertex and every edge

A

Euler Circuit

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

If a graph has an Euler circuit then every vertex has an _____ degree

A

Even (degree of every vertex in _______)

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

If every vertex is even and the graph is connected, then the graph has _____________

A

An Euler Circuit (what does this say about connectedness and degrees?)

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

A sequence of adjacent edges and vertices that starts at v, ends at w, and passes through every vertex and along every edge exactly once

A

Euler Path

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

Connected graph that has no non-trivial circuits

A

Tree

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

for a tree, the number of edges = __________

A

The # of vertices in the tree -1

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

A ________ is contained in a tree

A

Circuitless Graph (is contained in what?)

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

connected AND e=v-1
connected AND circuitless
circuitless AND e=v-1

A

Properties of a tree

25
Q

A subgraph of a graph that is a tree which includes every vertex

A

Spanning Tree

26
Q

Graph with numeric weights attached to the edges

A

Weighted Graph

27
Q

Spanning tree of the least possible weight

A

Minimal Spanning Tree

28
Q

Algorithm which adds vertices of lowest possible value that do not close circuits

A

Kruskal’s

29
Q

Algorithm that starts with a single vertex, then adds an edge and vertex at each step of minimal weight and does not close a circuit

A

Prim’s

30
Q

Isolated Vertex

A

A vertex with no edges

31
Q

Parallel Edges

A

More than one edge connecting two vertices

32
Q

Degree of a vertex

A

The number of times that a vertex is an endpoint

33
Q

Simple Graph

A

A graph with no loops or parallel edges

34
Q

Bipartite Graph

A

A graph that can be partitioned into 2 sets for which every edge connects vertices in different sets

35
Q

Kmn

A

The complete bipartite graph on m,n

36
Q

Connected Component

A

A maximal connected subgraph

37
Q

Walk

A

A finite alternating sequence of adjacent vertices and edges

38
Q

Path

A

A walk that does not contain a repeated edge

39
Q

Simple Path

A

A path that does not contain a repeated vertex

40
Q

Closed Walk

A

A walk that begins and ends on the same vertex

41
Q

Circuit

A

A closed walk that does not contain a repeated edge

42
Q

Isomorphic

A

Graphs with a 1-1 function such that vertices x and y are joined by an edge and so are f(x) and f(y)

43
Q

Isomorphism

A

1-1 function between two graphs

44
Q

Invariant

A

A property of a graph that doesn’t change under isomorphism

45
Q

Simple Circuit

A

A circuit that does not have any other repeated vertex except the first and last

46
Q

Euler Circuit

A

Circuit which contains every vertex and every edge

47
Q

Even (degree of every vertex in _______)

A

If a graph has an Euler circuit then every vertex has an _____ degree

48
Q

An Euler Circuit (what does this say about connectedness and degrees?)

A

Connected, every vertex has even degree

49
Q

Euler Path

A

A sequence of adjacent edges and vertices that starts at v, ends at w, and passes through every vertex and along every edge exactly once

50
Q

Tree

A

Connected graph that has no non-trivial circuits

51
Q

The # of vertices in the tree -1

A

Number of edges in a tree

52
Q

Circuitless Graph (is contained in what?)

A

A tree

53
Q

Properties of a tree

A

connected AND e=v-1
connected AND circuitless
circuitless AND e=v-1

54
Q

Spanning Tree

A

A subgraph of a graph that is a tree which includes every vertex

55
Q

Weighted Graph

A

Graph with numeric weights attached to the edges

56
Q

Minimal Spanning Tree

A

Spanning tree of the least possible weight

57
Q

Kruskal’s

A

Algorithm which adds vertices of lowest possible value that do not close circuits

58
Q

Prim’s

A

Algorithm that starts with a single vertex, then adds an edge and vertex at each step of minimal weight and does not close a circuit

Discrete Mathematics (1 decks)

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