Difference between revisions of "Graphs And Polyhedra"
| Line 88: | Line 88: | ||
= Hints for difficult problems = | = Hints for difficult problems = | ||
Statement : The Königsberg bridge problem : if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. | Statement : The Königsberg bridge problem : if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. | ||
| + | |||
| + | This is equivalent to asking if the multigraph on four nodes and seven edges (right figure) has an Eulerian cycle. This problem was answered in the negative by Euler (1736), and represented the beginning of graph theory. | ||
| + | http://photonics.cusat.edu/images/koning4.jpg | ||
| + | |||
| + | |||
| + | |||
| + | Image Courtesy : http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | Interpretation : | ||
| + | |||
| + | [[File:bridge .jpeg|400px]] | ||
| + | |||
| + | |||
| + | For Konigsberg, let us represent land with red dots and bridges with black curves, or arcs: | ||
| + | |||
| + | |||
| + | Thus, in its stripped down version, the seven bridges problem looks like this: | ||
| + | |||
| + | The problem now becomes one of drawing this picture without retracing any line and without picking your pencil up off the paper. Consider this: all four of the vertices in the above picture have an odd number of arcs connected to them. Take one of these vertices, say one of the ones with three arcs connected to it. Say you're going along, trying to trace the above figure out without picking up your pencil. The first time you get to this vertex, you can leave by another arc. But the next time you arrive, you can't. So you'd better be through drawing the figure when you get there! Alternatively, you could start at that vertex, and then arrive and leave later. But then you can't come back. Thus every vertex with an odd number of arcs attached to it has to be either the beginning or the end of your pencil-path. So you can only have up to two 'odd' vertices! Thus it is impossible to draw the above picture in one pencil stroke without retracing. | ||
= Project Ideas = | = Project Ideas = | ||
Revision as of 04:35, 10 July 2014
| Philosophy of Mathematics |
While creating a resource page, please click here for a resource creation checklist.
Concept Map
Error: Mind Map file Graphs And Polyhedrons.mm not found
Textbook
Additional Information
Useful websites
Wikipedia page for Graph Theory
For More Informations on Platonic Solids
Reference Books
Teaching Outlines
- Defining a Graph, node arc and Region
- Framing Euler's Formula for graphs
- Verifying Euler's Formula N + R = A + 2 for given Plane graphs
- Drawing graphs for given N,R and A
- Identifying the Traversible graphs
- Explaining and using the condition for Traversible graphs
- defining a Polyhedra
- Framing Euler's formula for Polyhedra
- verifying Euler's formula for the given Polyhedra
Concept
Representation of a Graph
Learning objectives
- To define what is node.
- to define what is arc
- To define what is Region
- To represent a Graph with node, Arc and Regions
Notes for teachers
These are short notes that the teacher wants to share about the concept, any locally relevant information, specific instructions on what kind of methodology used and common misconceptions/mistakes.
Activities
- Activity No #1
Introduction to Graphs
- Activity No #2
Graph Theory
Concept #
Learning objectives
Notes for teachers
These are short notes that the teacher wants to share about the concept, any locally relevant information, specific instructions on what kind of methodology used and common misconceptions/mistakes.
Activities
- Activity No #1
- Activity No #2
Assessment activities for CCE
Hints for difficult problems
Statement : The Königsberg bridge problem : if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began.
This is equivalent to asking if the multigraph on four nodes and seven edges (right figure) has an Eulerian cycle. This problem was answered in the negative by Euler (1736), and represented the beginning of graph theory.
Image Courtesy : http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html
Interpretation :
For Konigsberg, let us represent land with red dots and bridges with black curves, or arcs:
Thus, in its stripped down version, the seven bridges problem looks like this:
The problem now becomes one of drawing this picture without retracing any line and without picking your pencil up off the paper. Consider this: all four of the vertices in the above picture have an odd number of arcs connected to them. Take one of these vertices, say one of the ones with three arcs connected to it. Say you're going along, trying to trace the above figure out without picking up your pencil. The first time you get to this vertex, you can leave by another arc. But the next time you arrive, you can't. So you'd better be through drawing the figure when you get there! Alternatively, you could start at that vertex, and then arrive and leave later. But then you can't come back. Thus every vertex with an odd number of arcs attached to it has to be either the beginning or the end of your pencil-path. So you can only have up to two 'odd' vertices! Thus it is impossible to draw the above picture in one pencil stroke without retracing.
Project Ideas
Math Fun
Usage
Create a new page and type {{subst:Math-Content}} to use this template