12Topic3 Flashcards
(24 cards)
what are lines in a network called?
edges
what are points of a network called?
vertex
what is a degree?
the number of edges that meet at the vertex
how much does a loop add to a degree?
2
how to label vertices and edges?
vertices in curly brackets and edges we use the vertices that the edge sits between e.g (c,c) or (a,c)
what is a walk?
a journey through a network that starts at a vertex and ends at a vertex
what is a path?
a walk that dosent visit any vertex more than once
what is a cycle?
a walk with the same start and end vertex, which dosent visit any other vertex more than once
what is a trail?
a walk with no repreated edges
what is a circuit?
walk with no repeated edges that starts and ends at the same vertex
what is a transversable graph?
one that you can find a trail with edges and you dont take your pen off paper
connected networks
have a walk between every pair of vertices
disconnected network
not completely connected and there is not always a walk between all pairs of vertices
isomorphic graph
networks that look different but contain the same information
weighted graphs
have a number associated with each edge
what is a euler trail
a path that can be traced indefinitely without lifting a pen and visits each edge only once
how to tell if it is not a euler trail?
if it has more than 2 vertices of odd degree then it has not euler paths
what is a tree?
a network in which any two vehicles are connected by exactly one path
what is a leaf?
a vertex with a degree of 1
what is a spanning tree?
a tree that connects every vertex of a network and some of the edges, it has one less edge than the number of vertices.
what is a mst?
a minimum spanning tree - the smallest total edge weight is called a minimum spanning tree
what is kruskals algorithm?
starts with the smallest edge, then the next smallest edge
what is prims algorithm?
starts at any vertex and then chooses the shortest edge
