Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 9 - Networks and Graphs - Coggle Diagram
Chapter 9 - Networks and Graphs
9A + B
An Euler path is one where each edge is travelled only once
Graph elements
Dots and lines
Vertices (dots) represent the land
Edges (lines) represent bridges
Together
Loop --> joins the vertex to itself
Two or more edges that connect the same vertices are called multiple edges
A loop contributes two degrees to a vertex
Degree of a vertex
May be odd or even
The sum of degrees of the vertices is equal to twice the number of edges
A loop contributes one edge to the graph
A graph with all odd vertices cannot be traced or drawn without going over the same edge more than once
9C
Isomorphic Graphs
Different looking graphs containing the same information
Same number of edges and vertices
Corresponding vertices have the same degree and the edges connect to the same vertices
Connected Graphs and Bridges
If every vertex in the graph is accessible from every other vertex
A bridge -- Single edge in a connected graph that leaves the graph disconnected (can have more than 1)
9D
Planar graph
Drawn on a plane so no edges intersect
Faces of a graph
Outside face is infinite
Eulers formula
For a connected planar graph ----- V-e+f=2
9E
Trails
A walk with no repeated edges
Walks
A sequence of edges connecting a starting vertex to an ending vertex
Can travel over any edge and any vertex any number of times
Circuits
No repeated edges
Starts and ends at the same vertex
Cycles
A walk with no repeated vertices
Starts and ends at the same vertex
Path
A walk with no repeated vertices
No repeated vertices = no repeated edges
9F
Traversable Graph
A trail that includes every edge in the graph
Rules of identification
Must first be connected
All vertices are of even degree or two of the vertices are odd degree and the rest of them are even
No more than two vertices of odd degree
9G
Eulerian Trail
Trail that includes every edge in the graph
Must have exactly two odd degree vertices and will start with one finish at the other
Eulerian Cricuit
Circuit that includes every edge in the graph
All even degree vertices and start and finish at the same vertex
9H
Hamilton paths and cycles focus on vertices
A Hamilton path passes through every vertex
A Hamilton cycle is a Hamilton path that starts and finishes at the same vertex
9I
Weighted graph --> A number is associated with each edge
Network, a weighted graph in which the weights are physical quantities
Determining the shortest (---) to move around a network is called the shortest path problem
9J
Tree
A connected graph that contains no cycles, multiple edges or loops
May be part of a larger graph
A tree with n vertices has n-1 edges
Spanning Tree
A tree that connects all the vertices in a connected graph
Minimum spanning tree
The spanning tree of minimum length
There may be more than one minimum spanning tree in a weighted graph
Prim's Algorithm
3
Repeat the process until all the vertices are connected then stop.
The result is a minimum spanning tree
2
Inspect the edges starting from the vertices and choose the edge with the lowest weight
1
From a vertex inspect the edges and choose the one with the lowest weight