Math Forum - Problems Library - Discrete Math, Combinatorics

_____________________________________
diamond Library of Math Forum Problems

Primary Math Fundamentals Pre-Algebra
Algebra Geometry Discrete Math Trig/Calculus
_____________________________________
(membership required) || Become a Member || Learn about Membership
_____________________________________

TOPICS
space

This page:
  graph theory checkmark



About Levels
of Difficulty

Discrete Math
  combinatorics
  graph theory
  logic
  patterns/recursion
  proof
  social choice
  traveling sales
  trees
  vertex coloring
  miscellaneous

Browse all
Discrete Math
Problems

Discrete Math
Home

About the
PoW Library

Discrete Math: Graph Theory

Graph theory is a very large topic within discrete mathematics. Graph theory involves working with diagrams that consist of points, called vertices, and line segments, called edges. A few of the topics within graph theory include critical paths (Mud Slides and Critical Paths), minimal cost spanning trees (Minimal Minnie's Cost), Euler paths/circuits (The West Nile Virus Carrying Mosquito Problem), and vertex coloring (Beds of Flowers).

The problems below include these types of problems, as well as other problems that involve graphs.

For background information elsewhere on our site, explore the High School Discrete Math area of the Ask Dr. Math archives. To find relevant sites on the Web, browse and search Discrete Mathematics in our Internet Mathematics Library.


Access to these problems requires a Membership.

Beds of Flowers - Dona Coffey
Discrete Math, difficulty level 2. Dona wants to separate her types of flowers and the colors of her flowers into separate beds. How many beds will she have to dig? ... more>>

Binary Trees - Steve Maurer
Discrete Math, difficulty level 3. Given the definition of binary trees, students discover the relation between interior vertices and leaves and prove that relation. ... more>>

Changing Places - Ethel Breuche
Discrete Math, difficulty level 3. This puzzle requires you to swap chips on an unusual game board. ... more>>

Cooking Dinner - Leigh Nataro
Discrete Math, difficulty level 2. Using graphs and critical paths, find the amount of time it takes to make dinner. ... more>>

Delivering Toys for the Holidays - Leigh Nataro
Discrete Math, difficulty level 4. Using two different algorithms, find the distance traveled in creating a Hamilton circuit. ... more>>

Dona and Dennis Go Traveling - Dona Coffey
Discrete Math, difficulty level 2. Using matrix addition, students determine how many means of transportion they have in getting from city to city. ... more>>

A Game from West Africa - Cara Crosby
Discrete Math, difficulty level 3. This tic-tac-toe like game from Ghana has some good playing strategies and some graph theory applications. ... more>>

Gussie the lost Albino Emperor Penquin Pup - Ron Murdoch
Discrete Math, difficulty level 2. Find Gussie, a penguin pup hiding in a zoo building with nineteen rooms, before he suffers from hunger shock. ... more>>

Heads or Tails - Leigh Nataro
Discrete Math, difficulty level 2. Is it possible to have an arrangement of four coins go from HHHH to TTTT based on the rules given for flipping the coins? ... more>>

High School Reunion - Leigh Nataro
Discrete Math, difficulty level 1. Find the minimum number of meeting times needed so that no committee member will miss a meeting. ... more>>

Homework Phone Pals - Leigh Nataro
Discrete Math, difficulty level 1. Using the given clues, figure out which students are homework phone pals. ... more>>

How Many Graphs? - Joseph Rosenstein
Discrete Math, difficulty level 3. How many essentially different graphs are there with six vertices, two of which have degree two, two degree three, and two degree four? ... more>>

The Inside Lines - Larry Sue
Discrete Math, difficulty level 4. This problem makes use of Euler's formula and some geometry to find internal diagonals of regular polyhedra: tetrahedra, octahedra, and icosahedra. ... more>>

Intervals - Stephen Maurer
Discrete Math, difficulty level 3. Students are given clues about intervals on the number line and must determine whether they intersect or not. ... more>>

King Euler's Blueprint - Leigh Nataro
Discrete Math, difficulty level 1. Can you walk a path that will go through every doorway once? ... more>>

Minimal Minnie's Cost - Ethel Breuche, Dona Coffey
Discrete Math, difficulty level 2. Building a rail line that connects a number of different cities: a problem that involves graph theory, minimal cost spanning trees, and algorithms. ... more>>

Mother's Chores - Jim Greene
Discrete Math, difficulty level 1. A Traveling Salesperson Problem. Tom's mother needs to make several stops around the city and then get home. What is her shortest route without going back to one of the stops? ... more>>

Mud Slides and Critical Paths - Ethel Breuche
Discrete Math, difficulty level 4. Can the coastal village rebuild the town after a mudslide before inclement weather returns? Given an order priority digraph, find the earliest completion time and critical path. ... more>>

New York Tours - Sharon Edelkind
Discrete Math, difficulty level 2. Use vertex coloring to solve conflicting New York tour bus routes. ... more>>

Pothole Repair - Leigh Nataro
Discrete Math, difficulty level 2. Plan a route for the road crews to take. ... more>>

Train Travel - Dona Coffey
Discrete Math, difficulty level 2. Dona is in charge of setting up a new train service to connect nine towns in a county. What's the minimum cost? ... more>>

Vertices, Edges, and Regions - Leigh Nataro
Discrete Math, difficulty level 2. Find a relation among vertices, edges, and regions of planar graphs. ... more>>

Wacky�s Fun and Games Amusement Park - Natasha Hosein
Discrete Math, difficulty level 4. How can we minimize the number of clowns around the amusement park so that a child will never see two clowns at the same site? ... more>>

The West Nile Virus Carrying Mosquito Problem - Lorraine Lurie
Discrete Math, difficulty level 2. Getting the trucks to spray for the virus in all five boroughs involves knowledge of some elementary graph theory and Euler's theorems regarding traversible graphs. ... more>>

Which is the Dominant Team? - Jennifer Stetz, Nicole Zayatz
Discrete Math, difficulty level 3. Determine which soccer team dominates the division. ... more>>

Yearbook Deadlines - Leigh Nataro
Discrete Math, difficulty level 2. Find the critical path to determine the earliest time that the school yearbook can be completed. ... more>>

Page:  1


[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2012 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.