chapter 2;networks and paths Flashcards
what is a network diagram
a graph of vertices connected by lines
what is a vertex
a dot in the diagram which lines of pathways intersect or branch
what is an edge
line that connects vertices
what is a degree
number of edges that are connected to the dot
directed edge
has an arrow and travel only possible in the direction of the arrow
undirected edge
all edges undirected, travel is possible in both directions
simple network
no multiple edges or loops
weighted edge
an edge that has a weight or number assigned to it which has numerical value
what is a walk
connected sequence of edges showing a route between vertices where the edges and vertices may be visited multiple times
what is a trail
walk with no repeated edges
what is a path
walk with no repeated vertices
what is a circuit
walk with no repeated edges and starts and ends at the same vertex
what is a cycle
walk with no repeated vertices that starts and ends at the same vertex
traversable graph
trail that includes every edge
non-traversable graph
impossible to find a trail
connected graph
every vertex in the graph is accessible from every other vertex in the graph along a path formed by edges of the graph
isomorphic graph
same numbers of edges and vertices, corresponding vertices have the same degree and the edges connect to the same vertices
weighted graph
weighted edges or an edge with numbers assigned to it that implies it has numerical value (cost, distance, time)
eulerian trail
uses every edge of the graph, starts and ends at different vertices
eulerian circuit
uses every edge exactly once, starts and ends at the same vertex
Hamiltonian path
passes through every vertex once only
Hamiltonian cycle
starts and finishes at the same vertex
minimum spanning tree
minimum length, connects all vertices together with the minimum total weighting for the edges
shortest path
between two vertices in a network is the path where the sum of the weights of its edges minimised
