CS101 - Discrete Math

Robert Batzinger
Dec 2 17

Unit 5 - Graphs

Unit 5
Graphs

\[ \]

Contents

Calculating the chromatic number

Problem Definition

Given:

  • Every countries has been colored
  • Countries that share a border cannot have the same color.

What is the minium number of colors needed to color a map?

Problem Illustraton

graphs

Problem Label

coloredgraph

Connectivity Graph

/ A B C D E F G H I J K L M
A 1 1 1 1 1
B 1 1 1 1 1
C 1 1 1 1 1 1
D 1 1 1 1 1 1 1
E 1 1 1 1 1 1
F 1 1 1 1
G 1 1 1 1 1 1
H 1 1 1 1 1
I 1 1 1 1 1
J 1 1 1 1 1 1 1 1
K 1 1 1 1
L 1 1 1 1 1 1
M 1 1 1 1

Color List

Color ID 1 2 3 4 5 6 7
Color Red Orange Yellow Green Aqua Blue Purple
Color abbrev R O Y G A B P

Connectivity Graph

/ A B C D E F G H I J K L M
A [R] O Y O Y
B R [O] Y R Y
C R O [Y] O R G
D R Y [O] Y G Y R
E O Y [R] G Y O
F R O [Y] R
G Y O R [G] Y O
H O R [Y] O R
I O G [Y] O R
J R G Y Y [O] R R Y
K Y O [R] Y
L O Y Y O [R] Y
M O R R [Y]

Colored Map

coloredmap

Colored Graph

coloredgraph

Four Color Theorem

Given:

  • G is a planar graph

Then:

chromatic number of G is less than or equal to 4

\[ \]

Therefore:

(Any map can be colored with 4 or fewer colors.)

Challenge: Chromatic Number

Graphs*

  • Red: 6
  • Green: 3
  • Blue: 3

Establish a conflict-free schedule

Conflicts list for 10 crs

  • A: D I
  • C: E F I
  • D: A B F
  • E: H I
  • F: I
  • G: J
  • H: E I J
  • I: A B C E F H
  • J: B G H

Equivalent Graph

schedule

Tournament: all pairs of friends

  • 5 rounds required

six friends

  • 5 rounds required

five friends

Identifying planar graphs

Euler's Formula

\[ \huge v - e + f = 2 \]

  • v: vertices
  • e: edges
  • f: faces (including the outside)

plot of chunk unnamed-chunk-1

Check for Simularity

graphs

Simularity answers

graphs

Check for Planar Graph

Euler Path and Circuit

Definition

Euler circuit: if and only if the degree of every vertex in the graph is even.

Euler path: if and only if there are at most two vertices in the graph with odd degree.

Konigsberg Bridge

Bridge

Bridge

Bridge

Bridge

Hamilton Path

floor

floor

Hamilton Circuit

floor

floor