Brainscape's Knowledge GenomeTM

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


See full index

MATH 1060 > Unit 1 Test - Graph Theory > Flashcards

Unit 1 Test - Graph Theory Flashcards

1
Q

Graph definition

A

A collection of dots and lines or curves connecting pairs of vertices

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

Vertex definition

A

Dots

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

Edge definition

A

Lines or curves connecting vertices

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

Loop definition

A

An edge that connects a vertex to itself

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

Degree/valence of a vertex meaning

A

Number of edges meeting at that vertex

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

Path definition

A

A sequence of vertices connected by edges

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

Circuit definition

A

A closed path, meaning a path that starts and ends at the same vertex

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

Connected graph definition

A

Any two vertices have a path connecting them

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

Weight of an edge meaning

A

The “cost” of the edge

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

Euler path definition

A

A path that uses every path exactly once

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

Euler circuit definition

A

A circuit that’s also an Euler path

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

How can you know if a graph has an Euler circuit?

A

All vertices have even degrees

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

Fleury’s Algorithm

A

Verify the existence of the Euler path or circuit, then start at any vertex (circuit) or a vertex of odd degree (path) and choose any edge leaving that vertex, assuming that deleting that edge doesn’t separate the graph. Add that edge to the circuit/path and delete it from the graph, continuing until complete.

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

Eulerization definition

A

The process of adding edges to adjacent vertices to create an Euler circuit

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

Efficient Eulerization

A

Minimizing the number of duplicated edges

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

Chinese Postman Problem

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

Euler Circuit Theorem

A

If G is connected and all its vertices have even degree/valence, then G has an Euler circuit (and vice versa)

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

Euler Path Theorem

A

If G is connected and exactly two vertices have odd degree, then G has an Euler path and no Euler circuit, and if G has more than 2 vertices with odd degree, then G does not have an Euler path

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

Valence Theorem

A

For any graph G, the total number of vertices with odd valence is either zero or an even number

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

Digraph/Directed graph definition

A

A graph in which each edge has an arrow that indicates the edge’s direction

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

Weighted graph definition

A

A graph in which each edge has a number associated with the edge

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

Weight of a graph definition

A

The total number of the weight of each edge

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

Hamiltonian Path

A

A path where each vertex is used only once.

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

Hamiltonian Circuit

A

A path where each vertex is used only once, other than the start and end vertex

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

Traveling Salesman Problem

A

FInding a Hamiltonian circuit of smallest total weight

26
Q

Traveling Salesman Problem examples

A

Salesman based in one city traveling to each city in territory once, airport limo picking up customers and taking to airport, technician serving each of a bank’s network of ATMs, postal worker delivering mail to each drop-off box, etc.

27
Q

Brute force algorithm definition

A

Find all possible H. circuits and choose the one of smallest weight (time-consuming and inefficient)

28
Q

Complete graph definition

A

A graph such that any two distinct vertices are joined by one edge (n vertices, denoted Kn)

29
Q

Fundamental Principle of Counting

A

Suppose that we have n stages and at stage i there are ai distinct choices that can be made. Then the total number of choices is… a1 x a2 x a3 …. an

30
Q

Number of possible Hamiltonian circuits in a complete graph if start vertex matters

A

n!

31
Q

Number of possible Hamiltonian circuits in a complete graph if start vertex doesn’t matter

A

(n-1)!

32
Q

Number of possible Hamiltonian circuits in a complete graph if start vertex doesn’t matter and direction doesn’t matter

A

(n-1)! / 2

33
Q

What types of graphs will never have Hamiltonian circuits?

A

Bipartite graphs and n x m rectangular graphs with n and m both being odd (# vertices)

34
Q

Greedy algorithms definition

A

Algorithms that are locally but not necessarily globally optimal

35
Q

Heuristic algorithms definition

A

Algorithms that will produce a solution relatively quickly, but with no guarantee that the solution is optimal

36
Q

Nearest Neighbor Algorithm definition

A

Select a starting point, move to the closest unvisited vertex by edge of smallest weight, and repeat until the circuit is completed

37
Q

Does the NNA always give a Hamiltonian circuit of smallest weight?

A

No, it may or may not

38
Q

Repeated Nearest Neighbor Algorithm

A

Do the NNA for each vertex, then choose the circuit of smallest weight

39
Q

Sorted Edges Algorithm definition

A

Select the cheapest unused edge in the graph and repeat unless adding the edge makes a circuit not containing all vertices or adding the edge gives a vertex degree 3

40
Q

Hamiltonian circuits/paths real-world applications

A

Road trips/sightseeing, worker checking sites, etc.

41
Q

Spanning tree definition

A

A connected graph using all vertices in which there are no circuits

42
Q

Subgraph definition

A
43
Q

Minimum cost spanning tree definition

A

A spanning tree of smallest weight or cost

44
Q

Kruskal’s Algorithm

A

Select the cheapest unused edge in the graph, repeat unless adding the edge would create a circuit, and repeat until a spanning tree is formed (similar to sorted edges)

45
Q

Does Kruskal’s Algorithm always give a minimal cost spanning tree?

A

No, it does not always

46
Q

Prim’s Algorithm

A

Remove all loops and parallel edges of highest weight, choose any vertex, select an outgoing edge of lowest cost, and repeat for any previously included vertex unless including an edge forms a cycle (similar to NNA)

47
Q

Does Prim’s Algorithm always give a minimal cost spanning tree?

A

No, it doesn’t always

48
Q

Spanning tree real-world applications

A

Utility lines (water, telephones, electric wiring)

49
Q

Spanning tree number of edges

A

A tree with n vertices has n-1 edges

50
Q

How many spanning trees exist?

A

Complete graph Kn has n ^n-2 spanning trees

51
Q

Minimal cost spanning tree real-world applications

A

Connectivity (utility lines, water pipes, internet cables, etc.), facial recognition software, etc.

52
Q

Vertex coloring definition

A

What’s the fewest number of colors needed to not have two vertices have the same color

53
Q

Chromatic number of a graph

A

The fewest number of colors needed to color each vertex so that no adjacent vertices have the same color (shown X(G))

54
Q

Brook’s Theorem

A

For any graph G, X(G) <= delta (G) unless G is a complete graph or a circuit with an odd number of vertices in which case X(G) = delta (G) + 1

55
Q

Graph coloring real-world application

A

Avoiding conflict

56
Q

What is the lower bound of the chromatic number?

A

Subgraphs (does it contain k3?, k4?, k5?, etc.)

57
Q

What is the upper bound of the chromatic number?

A

The largest degree of any vertice

58
Q

What is the chromatic number for complete graphs?

A

Kn = n

59
Q

What is the chromatic number for tree graphs?

A

2

60
Q

What is the chromatic number for bipartite graphs?

A

2

61
Q

What is the chromatic number for circuit graphs with even vertices?

A

2

62
Q

What is the chromatic number for circuit graphs with odd vertices?

A

3

MATH 1060 (3 decks)

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