Networks Flashcards
Define
Network diagram
A representation of a group of objects called vertices that are connected together by lines. Network diagrams are also called graphs.
Define
Vertex
A point (or dot) in a network diagram at which lines of pathways intersect or branch. Vertices are also called nodes.
Define
Edge
The line that connects two vertices. Edges can cross each other without intersecting at a node.
Define
Degree
(of a vertex)
The degree of a vertex is the number of edges that are connected to it. The degree of a vertex is either even or odd.
Define
Loop
(in a network)
An edge which starts and ends at the same vertex. It counts as one edge, but it contributes two to the degree of the vertex.
Define
Directed edge
Also called an arc, it has an arrow and travel is only
possible in the direction of the arrow.
Define
Walk
a connected sequence of the edges showing a route between vertices and edges.
Define
Trail
A walk with no repeated edges.
Define
Path
A walk with no repeated vertices or repeated edges. Open paths start and finish at different vertices while closed paths start and finish at the same vertex.
Define
Circuit
A walk with no repeated edges that starts and ends at the same vertex.. Circuits are also called closed trails. Alternatively, open trails start and finish at different vertices.
Define
Cycle
A walk with no repeated vertices that starts and ends at the same vertex. There are no repeated edges in a cycle as there are no repeated vertices. Cycles are closed paths.
Define
Hamiltonian path
A path passes through every vertex of a
graph once and only once.
Define
Hamiltonian cycle
A Hamiltonian path that starts and finishes
at the same vertex.
Define
Eulerian trail
A trail that uses every edge of a graph exactly once and starts and ends at different vertices. Eulerian trails exist if the graph has exactly two vertices with an odd degree.
Define
Eulerian circuit
A circuit that uses every edge of a network graph exactly once, and starts and ends at the same vertex. Eulerian circuits exist if every vertex of the graph has an even degree.
Define
Tree
A connected graph that contains no cycles, multiple edges or loops.
Define
Spanning tree
A tree which connects all the vertices in
the graph
Define
Minimum spanning tree
A spanning tree of minimum length. It connects all the vertices together with the minimum total weighting for the edges.
Prim’s algorithm
- Choose a starting vertex (any will do).
- Inspect the edges starting from the starting vertex and choose the one with the lowest weight. (If there are two edges that have the same weight, it does not matter which one you choose).
- Inspect all of the edges starting from both of the vertices you have in the tree so far. Choose the edge with the lowest weight, ignoring edges that would connect the tree back to itself.
- Keep repeating step 3 until all of the vertices are connected.
Kruskal’s algorithm
- List all the edges in ascending order of length.
- Choose the shortest edge. If two edges are the same length, arbitarily choose one.
- Choose the next shortest edge. It does not matter if this edge is connected to the first edge or not.
- Choose the next shortest edge which doesn’t create a cycle
- Continue until all vertices are connected
Dijkstra’s Algorithm
Choose a starting node and calculate the shortest distance to the next nodes. These nodes are then marked as “visited” and their shortest distances is used in calculations for later nodes.
