MA5-NET-P-01 solves problems involving the characteristics of graphs/networks, planar graphs and Eulerian trails and circuits
📖 Prior Knowledge: None!
Examine and describe a graph/network
Describe a network as a collection of objects (nodes or vertices) interconnected by lines (edges) that can represent systems in the real world
Examine real-world applications of networks such as social networks, supply chain networks and communication infrastructure, and explore other applications of networks
Explain that the terms graph and network are interchangeable
Identify and define elements of a graph including vertex, edge and degree
Explain that a given graph can be drawn in different ways
Define a planar graph and apply Euler’s formula for planar graphs
Define a planar graph as any graph that can be drawn in the plane so that no 2 edges cross
Define a non-planar graph as a graph that can never be drawn in the plane without some edges crossing
Demonstrate that some graphs that have crossing edges are still planar if they can be redrawn so that no 2 edges cross
Identify the number of faces in a planar graph
Describe and apply Euler’s formula for planar graphs: v−e+f=2, where v= vertices, e= edges and f= faces
Explain the concept of Eulerian trails and circuits in the context of the Königsberg bridges problem
Explain that a connected graph is a graph that is in one piece, so that any 2 vertices are connected by a path
Define a walk on a graph to be a sequence of vertices and edges of a graph
Explain the difference between trail, circuit, path and cycle
Relate the definition of a trail to an Eulerian trail as a walk in which every edge in the graph is included exactly once
Relate the definition of a circuit to an Eulerian circuit that is defined as an Eulerian trail that ends at its starting point
Relate Euler’s Seven Bridges of Königsberg network problem to the definition of an Eulerian trail or circuit