Graph Theory : Graph Theory A Story of Connections Topology : Topology Topology is the study of stretching and distorting shapes.
The size and shape of an object don’t matter here. All that counts is the connectedness of the object.
This allows us to see common properties of different objects These two shapes are topologically equivalent Vocabulary : Vocabulary Graph: a network, a set of points connected by lines REGION Classifying Graphs : Classifying Graphs Size = number of vertices Degree of vertex – number of edges coming from a vertex Regular = all vertexes have same degree Vocabulary : Vocabulary Complete = every vertex connects to all other vertexes. You can’t draw anymore! Topology of the plane : Topology of the plane Topological properties in the plane do not depend on the size or shape of the objects we study. Start with…. a dot, which we call a vertex or a node. Vertexes______Edges______Regions___ V+R-E Add another dot and a connector called an edge. Dot 1 0 1 1+1-0 = It sits in a plane we will call a region Segment 2 1 1 2+1-1 = 2 2 Slide 7: Topology of the plane Now add another edge Vee 3 2 1 3+1-2= 2 Slide 8: Topology of the plane Now make a triangle We pick up an edge, but also another region – the inside of the triangle Triangle 3 3 2 3+2-3= 2 Continue the process : If I add one segment that connects to two others:
Add 1 edge
Add 1 region
Add segment that connects to one vertex only
Add 1 edge
Add 1 vertex Continue the process Slide 10: V+R-E will always be 2 for connected graphs like these in a plane! This number V + R – E is called the Euler characteristic of a graph. It describes the relationship and number of its parts. EULER CHARACTERISTIC Do other types of graphs have different Euler characteristics? Slide 11: Warning: the process fails if we add an unconnected piece: Vertexes______Edges______Regions___ V+R-E 5 4 2 5+2-4= 3 For a graph that isn’t connected, the formula generalizes to:
V+R-E = κ + 1
Where κ is exactly the number of connected sub-pieces in the graph! 2 + 1 More Vocabulary : More Vocabulary Connected graph: one in which I can reach any vertex by traveling along edges of the graph
Planar graph: can be drawn in the plane with no edges crossing
Non-planar graph: has crossing edges Planar Non-planar Non-Planar Graphs : Non-Planar Graphs This graph is called K5 It is the complete graph on five nodes, which means all its vertices are connected to each other. This one’s name is K3,3 It is the bipartite graph with 2 groups of three nodes each. In this type of graph, nodes connect to all the nodes in the other group, but not to each other. Every non-planar graph contains one of these graphs within itself! History : History Graph theory began with Leonard Euler in 1736
The bridges of Konigsberg problem: History : History Path – trip through vertices Cycle – path that starts and stops at the same place How do you describe trips around a graph? This is an important part of graph theory. History of Euler’s Formula : History of Euler’s Formula Find the Euler Characteristic for a Solid : Find the Euler Characteristic for a Solid Projection on the plane For solids, we may want to refer to regions as faces Every polyhedron corresponds to a connected planar graph with the same number of edges and vertices. How to flatten a cube : How to flatten a cube 1. Remove the “top” 2. Pull out the remaining edges. 3. Each remaining face of the cube becomes an interior region of the graph. 4. The removed top of the cube becomes the exterior region. 1 4 3 2 5 6 The Platonic Solids : The Platonic Solids The Platonic Solids : The Platonic Solids The Euler characteristic for an object with holes ? : The Euler characteristic for an object with holes ? An open box A pentagonal torus We need to adjust the formula if the object has holes.
For any polyhedron V+R-E = 2 – 2n
where n = the number of holes. Find the Euler characteristic of an open box : Find the Euler characteristic of an open box An open box For the open box, V = 8, R = 4, E = 12
V+R-E = 2 – 2n
8+4-12 = 0
= 2 – 2(1) Find the Euler characteristic for an object with one hole : Find the Euler characteristic for an object with one hole An open box A pentagonal torus For all objects with one hole,
the Euler characteristic is 0
What is the Euler characteristic for an object with two holes? Curved polygons : Curved polygons Can be straightened into a normal polygon, except for… These can’t exist with straight sides! Find the Euler characteristic for graphs on round objects : Find the Euler characteristic for graphs on round objects Sphere with 12 longitude lines. Cone with six connectors to its base Sphere with a band around the middle. Slide 26: There are some rules to follow when finding Euler characteristic V + R – E = ? 8 + 1 – 8 = 1 This can’t be right! One region cannot contain a hole. Redraw the figure like this: 8 + 4 – 12 = 0 V + R – E = ? Example: Find the Euler characteristic for an annulus. Use a figure with sides. Find the Euler characteristic for graphs on a torus : Find the Euler characteristic for graphs on a torus These two objects are topologically equivalent – they have the same Euler characteristic Work with the object with sides and the answer will apply to the torus! Find the Euler characteristic for some odd things! : Find the Euler characteristic for some odd things! A one-sided Mobius band A soccer ball Gas, water, electric : Gas, water, electric The Utility Problem: connect all 3 houses to all three utilities without crossing pipes/wires. Can’t be done! The utility problem as a Graph : The utility problem as a Graph F = 2- V + E
= 2 – 6 + 9
= 5 No loops, no 2 sided graphs, no triangular configurations are needed here. So each face has at least 4 edges. Hence, E > 4F/2 or E > 10. This is a contradiction.