Networks Flashcards
What is a vertex?
A vertex is a point in a network diagram at which lines of pathways intersect/meet. Vertices are also called nodes.
What is an edge?
An edge is a line that connects the vertices.
What is meant by the degree of a vertex?
The degree of a vertex is the number of edges that are connected to it. The degree of the Broken Hill vertex is 3 because there are three edges attached to the vertex.
Finish the sentence…
“The degree of a vertex is ? if it has an even number of edges attached to it.”
The degree of a vertex is even if it has an even number of edges attached to the vertex.
Finish the sentence…
“The degree of a vertex is ? if it has an odd number of edges attached to it.”
The degree of a vertex is odd if it has an odd number of edges attached to it.
What is a loop?
A loop starts and ends at the same vertex. It counts as one edge, but it contributes two to the degree of the vertex.
What is a directed edge?
A directed edge has an arrow and travel is only possible in the direction of the arrow.
What is an undirected edge?
An undirected edge has no arrow and travel is possible in both directions.
What is a directed network?
In a directed network all the edges are directed - travel is only permissible in the direction of the arrows.
What is an undirected network?
In an undirected network, all the edges are undirected and travel on an edge is possible in both directions.
What is a simple network?
In a simple network, there are no edges or loops.
What is a weighted edge?
A weighted edge is an edge of a network diagram that has a number assigned to it that implies some numerical value such as cost, distance or time.
What is a walk?
A walk is a connected sequence of the edges showing a route between vertices where the edges and vertices may be visited multiple times.
What is a trail?
A trail is a walk with no repeated edges.
What is a path?
A path is a walk with no repeated vertices.
What is a cycle?
A cycle is 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.
What is a circuit?
A circuit is 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.
What is a traversable graph?
A traversable graph has a trail that includes every edge. The trail A–B–C–A–C is one example.
What is a non-traversable graph?
Not all graphs are traversable. It is impossible to find a trail in a non-traversable graph that includes every edge.
What is a connected graph?
A connected graph has every vertex connected to every other vertex, either directly or indirectly via other vertices. That is, every vertex in the graph can be reached from every other vertex in the graph.
Finish the sentence…
Two graphs are isomorphic if:
- ?
- ?
Two graphs are isomorphic if:
- they have the same numbers of edges and vertices
- corresponding vertices have the same degree and the edges connect to the same vertices.
What are isomorphic graphs?
Different looking graphs can contain the same information.
What is an 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.
What is an 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.
