network concepts Flashcards
what is a network?
a network is a term to describe a group or system of interconnected objects. it consists of vertices and edges. the edges indicate a path or route between two vertices.
what is a vertex on a network?
a vertex is a point (or dot) at which lines intersect or branch
what is an edge on a network?
an edge is a line that connects vertices
what is a loop in a network?
a loop starts and ends at the same vertex, counting as one edge but contributing two to the degree of the vertex
what is a directed edge in a network?
a directed edge, also called an arc, has an arrow which indicates the only way in which travel can be directed
what is an undirected edge in a network?
an undirected edge does not have an arrow, therefore meaning that travel can be directed either way along the edge
what is a directed network?
a directed network is a network in which all of the edges are directed, and travel can only happen in the way that the edges indicate
what is an undirected network?
an undirected network is a network in which the edges are not directed, and travel can happen in any direction
what is the degree of a vertex in a network?
the degree of a vertex in a network corresponds to the number of edges that connect to a vertex
what is a walk in a network?
a walk in a network is a connected sequence of edges showing a route between vertices where the edges and vertices may be visited multiple times
what is a trail in a network?
a trail in a network is a walk with no repeated edges
what is a path in a network?
a path in a network is a walk with no repeated vertices
what is a circuit in a network?
a circuit in a network, also called a closed trail, is a walk with no repeated edges that starts and ends at the same vertex
what is a cycle in a network?
a cycle in a network is a walk with no repeated vertices that starts and ends at the same vertex
what is a connected graph?
a graph is connected if every vertex in the graph is accessible from every other vertex in the path graph along a path formed by the edges of the graph
what are isomorphic graphs?
two graphs are isomorphic (equivalent) if:
* they have the same number of edges and vertices
* corresponding vertices have the same degree and the edges connect to the same vertices
what is a weighted graph?
a weighted graph is a network that has weighted edges, meaning edges with numbers assigned that imply some numerical value such as cost, distance or time
what is a tree on a network?
a tree is a connected graph that contains no cycles, multiple edges or loops
what is a spanning tree on a network?
a spanning tree is a tree that connects all of the vertices on a graph
what is a minimum spanning tree on a network?
a minimum spanning tree is a spanning tree that takes up the minimum length possible on a network, whilst connecting all of the vertices
what is Prim’s algorithm?
Prim’s algorithm is a set of rules to determine a minimum spanning tree for a graph:
1. choose a starting vertex
2. inspect the edges starting from the starting vertex and choose the one with the lowest weight
3. inspect all of the edges starting from both of the vertices you have in the tree so far; choose each edge with the lowest weight, ignoring edges that would connect the tree back to itself
4. repeat step 3 until all of the vertices are connected
what is the shortest path in a network?
the shortest path between two vertices in a network is a path where the sum of the weights of its edges is minimised
