Graphs Test Flashcards
What is a graph?
Consists of vertices or nodes which are connected by edges or arcs.
What is a weighted graph? What is another term for weighted graph?
A graph which has a weight associated with each edge and otherwise known as a network.
What is a subgraph?
A graph where each of its vertices and edges belong to the original graph. It is a part of the original graph.
What is the degree, valency or order of a vertex?
The number of edges incident to it.
What is a walk?
A route through a graph along edges from one vertex to the next.
What is a path?
A path is a walk which no vertex is visited more than once.
What is a trail?
A walk which no edge is visited more than once.
What is a cycle?
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.
What is a Hamiltonian cycle?
A cycle that includes every vertex.
What is a loop?
An edge that starts and finished at the same vertex.
What is a simple graph?
A simple graph is one in which there are no loops and there is at most one edge connecting any pair of vertices.
What is a digraph?
If the edges of a graph have a direction associated with them the they are known as directed edges and the graph is known as a directed graph.
What is Euler’s handshaking lemma?
In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges; leading to the number of odd vertices being even.
What is a tree?
A tree is a connected graph with no cycles.
What is a spanning tree?
A spanning tree of a graph is a subgraph of which includes all the vertices of the original graph and is a tree.
