Chapter 5 Terms

Question 1

The Konigsberg Puzzle

Answer 1

• Unsolvable bridge puzzle

Question 2

Think of graphs as __________.

Answer 2

• Connections

Question 3

Graph Theory

Answer 3

• Illustrates and analyzes connections

Question 4

Graph

Answer 4

• A set of points and line segments that connect the vertices

Question 5

Vertices

Answer 5

• The points on a graph

Question 6

Edges

Answer 6

• The line segments that connect the vertices

Question 7

Null Graph

Answer 7

• Vertices are totally disconnected . . .

Question 8

Connected Graph

Answer 8

• Where each vertices is touching another one .-.-.

Question 9

Not Connected Graph

Answer 9

• Each vertical is touching another but they are not connected . .-. .-.

Question 10

A Complete Graph

Answer 10

• Every possible edge is drawn

Question 11

To See if Graphs Are Equivalent

Answer 11

• Count the vertices
• Count the edges
• Write down the names of the connections

Question 12

Path

Answer 12

• Movement from one vertex to another via edges

Question 13

Closed Path

Answer 13

• When a path ends where it started

- AKA: circuit

Question 14

Euler Circuit

Answer 14

• A circuit that uses every edge but never the same edge twice

Question 15

Degree

Answer 15

• The number of edges coming from a vertex

Question 16

An euler circuit is possible if…

Answer 16

• The no. of edges coming from every vertex is even

Question 17

Euler Path

Answer 17

• A route that uses every edge but you do not have to end up where you started
• Will start and end at the ODD verticals

Question 18

A euler path is possible if…

Answer 18

• If two (and only two) verticals are odd

Question 19

Hamiltonian Circuit

Answer 19

• The path that visits each vertex once and returns to the starting vertex, without visiting any vertex twice

Question 20

A Hamiltonian circuit exists if…

Answer 20

• Every vertex has a degree of at least n/2

- “n” = the number of verticals

Question 21

Weighted Graph

Answer 21

• A graph in which each edge is associated with a value

Question 22

Shortcut algorithms only apply to…

Answer 22

• Complete graphs

Question 23

The Greedy Algorithm Steps

Answer 23

1. Choose a vertex and travel across the connecting edge with the smallest weight
2. Reach the next vertex and travel to an unvisited one by using the edge with the smallest weight
3. Continue
4. Get to every vertex once
5. Return to where you started

Question 24

Edge-Picking Algorithm Steps

Answer 24

1. Mark edge of smallest weight
2. Mark edge of next smallest weight
   
   • Do not complete a circuit
   • Do not mark an edge more that twice
3. Continue until you cannot make any edges

Question 25

Planar Graph

Answer 25

• A graph that can be drawn so that no edges intersect each other

Question 26

Planar Drawing

Answer 26

• A graph that is drawn in such a way that no edges touch

Question 27

Steps to Identify a Planar Graph

Answer 27

1. Name the vertices
2. Find a Hamiltonian Path
3. Make a basic loop of these vertices
4. Draw in the remaining edges
   * If all else fails, guess and check

Question 28

Steps to Identify a Non-planar Graph

Answer 28

1. Name the vertices
2. Find a Hamiltonian Path
3. Make a basic loop of these vertices
4. Draw in the remaining edges
   * If all else fails, guess and check

Question 29

Euler’s Formula

Answer 29

v + f = e + 2

Question 30

Steps to Determine How Many Colors Are Needed to Color in a Graph

Answer 30

1. Create a graph
2. Erase the boundaries
3. Determine the number of colors needed so that no boundaries share a color

Question 31

Ever PLANAR graph is 4-colorable

Answer 31

• Well, that’s a cool fact!

Question 32

What do these words mean:

• 2-colorable
• 3-colorable
• 4-colorable

Answer 32

• If the map uses 2 colors
• If the map uses 3 colors
• If the map uses 4 colors

Question 33

Chromatic Number

Answer 33

• The number of colors needed for a non-planar graph

Question 34

A graph is 2-colorable if…

Answer 34

• It has no circuits that consist of an odd number of vertices