Unit 1 Test - Graph Theory

Question 1

Graph definition

Answer 1

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

Question 2

Vertex definition

Answer 2

Dots

Question 3

Edge definition

Answer 3

Lines or curves connecting vertices

Question 4

Loop definition

Answer 4

An edge that connects a vertex to itself

Question 5

Degree/valence of a vertex meaning

Answer 5

Number of edges meeting at that vertex

Question 6

Path definition

Answer 6

A sequence of vertices connected by edges

Question 7

Circuit definition

Answer 7

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

Question 8

Connected graph definition

Answer 8

Any two vertices have a path connecting them

Question 9

Weight of an edge meaning

Answer 9

The “cost” of the edge

Question 10

Euler path definition

Answer 10

A path that uses every path exactly once

Question 11

Euler circuit definition

Answer 11

A circuit that’s also an Euler path

Question 12

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

Answer 12

All vertices have even degrees

Question 13

Fleury’s Algorithm

Answer 13

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.

Question 14

Eulerization definition

Answer 14

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

Question 15

Efficient Eulerization

Answer 15

Minimizing the number of duplicated edges

Question 16

Chinese Postman Problem

Question 17

Euler Circuit Theorem

Answer 17

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

Question 18

Euler Path Theorem

Answer 18

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

Question 19

Valence Theorem

Answer 19

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

Question 20

Digraph/Directed graph definition

Answer 20

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

Question 21

Weighted graph definition

Answer 21

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

Question 22

Weight of a graph definition

Answer 22

The total number of the weight of each edge

Question 23

Hamiltonian Path

Answer 23

A path where each vertex is used only once.

Question 24

Hamiltonian Circuit

Answer 24

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

Question 25

Traveling Salesman Problem

Answer 25

FInding a Hamiltonian circuit of smallest total weight

Question 26

Traveling Salesman Problem examples

Answer 26

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.

Question 27

Brute force algorithm definition

Answer 27

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

Question 28

Complete graph definition

Answer 28

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

Question 29

Fundamental Principle of Counting

Answer 29

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

Question 30

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

Answer 30

n!

Question 31

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

Answer 31

(n-1)!

Question 32

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

Answer 32

(n-1)! / 2

Question 33

What types of graphs will never have Hamiltonian circuits?

Answer 33

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

Question 34

Greedy algorithms definition

Answer 34

Algorithms that are locally but not necessarily globally optimal

Question 35

Heuristic algorithms definition

Answer 35

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

Question 36

Nearest Neighbor Algorithm definition

Answer 36

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

Question 37

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

Answer 37

No, it may or may not

Question 38

Repeated Nearest Neighbor Algorithm

Answer 38

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

Question 39

Sorted Edges Algorithm definition

Answer 39

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

Question 40

Hamiltonian circuits/paths real-world applications

Answer 40

Road trips/sightseeing, worker checking sites, etc.

Question 41

Spanning tree definition

Answer 41

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

Question 42

Subgraph definition

Question 43

Minimum cost spanning tree definition

Answer 43

A spanning tree of smallest weight or cost

Question 44

Kruskal's Algorithm

Answer 44

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)

Question 45

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

Answer 45

No, it does not always

Question 46

Prim's Algorithm

Answer 46

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)

Question 47

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

Answer 47

No, it doesn't always

Question 48

Spanning tree real-world applications

Answer 48

Utility lines (water, telephones, electric wiring)

Question 49

Spanning tree number of edges

Answer 49

A tree with n vertices has n-1 edges

Question 50

How many spanning trees exist?

Answer 50

Complete graph Kn has n ^n-2 spanning trees

Question 51

Minimal cost spanning tree real-world applications

Answer 51

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

Question 52

Vertex coloring definition

Answer 52

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

Question 53

Chromatic number of a graph

Answer 53

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

Question 54

Brook's Theorem

Answer 54

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

Question 55

Graph coloring real-world application

Answer 55

Avoiding conflict

Question 56

What is the lower bound of the chromatic number?

Answer 56

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

Question 57

What is the upper bound of the chromatic number?

Answer 57

The largest degree of any vertice

Question 58

What is the chromatic number for complete graphs?

Answer 58

Kn = n

Question 59

What is the chromatic number for tree graphs?

Answer 59

2

Question 60

What is the chromatic number for bipartite graphs?

Answer 60

2

Question 61

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

Answer 61

2

Question 62

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

Answer 62

3