Graph Theory

Question 0

Edge

Answer 0

Line Segments or curves that start and end at vertices.

Question 1

Graph

Answer 1

Consists of a finite set of vertices(points) and line segments or edges(curves). Edges start and end at vertices.

Question 2

Equivalent Graph

Answer 2

1. Same number of vertices and edges.

2. Check for adjacent vertices connected in the same way.

Question 3

Adjacent Vertices

Answer 3

Two vertices with an edge connecting them.

Question 4

Degree of a Vertex

Answer 4

Found by counting the total number of edges at the vertex. Loops add two.

Question 5

Loop

Answer 5

Edge which connects a vertex to itself. Degree is 2.

Question 6

Path

Answer 6

1. A route in a graph sequence of adjacent vertices.
2. Written as a list of vertices.
3. Using an edge only once.

Question 7

Circuit

Answer 7

A path that begins and ends at the same vertex

Question 8

Connected Graph

Answer 8

Every pair of vertices has a path that contains them. You can travel from any vertex to any other vertex in the graph.

Question 9

Bridge

Answer 9

An edge when removed changes the graph from connected to disconnected.

Question 10

Euler Path

Answer 10

A path that travels through EVERY edge of a graph once and only once.

Question 11

Euler Circuit

Answer 11

A circuit using EVERY edge exactly once. Must begin and end at the same vertex.

Question 12

Euler’s Theorem

Answer 12

The number of odd vertices determines if a graph has Euler paths and Euler circuits.
For Connected graphs:
No odd -> at least on Euler Circuit/Path
2 -> No Euler Circuit, 1 or more Euler paths
greater than 2 -> No Euler paths/circuits

Question 13

Fleury’s Algorithm

Answer 13

Helps to find Euler Paths and Circuits.

1) If 2 odd vertices(exactly) choose one odd to start the path and end at the other odd.
2) If no odd, then an Euler circuit, start at any vertex
3) Number the edges as you trace through the graph. After you travel over an edge dot that edge. Do not choose a bridge if you have the choice. Only travel over the bridge if there’s no other alternative.

Question 14

Components

Answer 14

Pieces of a disconnected Graph

Question 15

Traveling Salesperson Problem

Answer 15

The problem to find the Hamilton Circuit with the optimal solution, that is to say, with the smallest sum of weights.

Question 16

Complete Graph

Answer 16

A graph that has an edge between each pair of vertices.

Question 17

Number of Hamilton Circuits in a complete graph?

Answer 17

(n-1)! where n=vertices

Question 18

Neighbors

Answer 18

Two vertices connected by an edge. In a complete graph all vertices are neighbors.

Question 19

Weighted Graph

Answer 19

A graph whose edges have numbers that can be summed.

Question 20

Nearest Neighbor Method

Answer 20

1. Use a complete weighted graph
2. Identify the starting vertex
3. Choose edge with smallest weight. Move along edge to second vertex.
4. Choose next connected edge with smallest weight that does not lead to a vertex already visited.
5. Continue steps until all vertices are visited
6. Return to the starting point
7. Sum up weights

Question 21

Brute Force Method

Answer 21

1. Model problem wit a complete weighted graph
2. Make a list of all possible Hamilton Circuits.
3. Determine the sum of the weights of the edges for each of the Hamilton Circuits.
4. The Hamilton Circuit with the smallest weight sum is the optimal solution

Question 22

Tree

Answer 22

Connected Graph. No Circuits. One and only one path joining any two vertices. Every Edge is a bridge. N vertices, has n-1 edges.

Question 23

Minimal Spanning Tree

Answer 23

Spanning tree with the smallest possible total weight.

Question 24

Kruskal’s Algorithm

Answer 24

Used to find a minimal spanning tree of a connected, weighted graph.

1. Draw all Vertices
2. List the weights of the edged in order from smallest to largest.
3. Add in edge with the smallest weight
4. Continue to add acceptable edges that do not form a circuit. Stop when all vertices are connected.