Flashcards
Graphs
Cards in this deck (10)
- 1What does a Graph consist of?A Graph consist of a NON-EMPTY set of elements called Vertices (V), and possibly an empty set of elements called Edges (E), where each edge is associated with a pair of vertices.
- 2When is a Graph a Directed Graph? (or a Digraph)A Graph is considered to be a Directed Graph (or a Digraph) when the edges have direction.
- 3When is a Graph an Undirected Graph?A Graph is considered to be an Undirected Graph when the edges do NOT have direction.
- 4If it is not specified whether a graph is Directed or Undirected, what is it assumed to be?A Graph that is neither specified as Directed nor Undirected is always assumed to be Undirected.
- 5What is a Path in a Graph?A path in a Graph is a
sequence of one or more
edges, all different. - 6What is a Cycle in a Graph?A cycle in a Directed or
Undirected graph is a path
which begins and ends at the
same vertex. - 7What is a Loop in a Graph?A loop is defined to be a
cycle of length one - 8What is the Degree of a Vertex?The
Degree of Vertex V is the total
number of edges which are
incident with v (i.e. joined to
v).
If the Graph is Directed, then the Indegree of V is the number of edges leading INTO V, and the Outdegree is the number of edges leading OUT of V. - 9What is a Connected Graph?A Graph is Connected if for every pair of Vertices, there is a path joining them. Otherwise, it is said to be Disconnected.
- 10What is a Weighted Graph?A Weighted Graph is a Graph in which each edge has a number (or weight) associated with it.