Graphs

Question	Answer
What 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.
When 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.
When is a Graph an Undirected Graph?	A Graph is considered to be an Undirected Graph when the edges do NOT have direction.
If 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.
What is a Path in a Graph?	A path in a Graph is a sequence of one or more edges, all different.
What 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.
What is a Loop in a Graph?	A loop is defined to be a cycle of length one
What 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.
What 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.
What is a Weighted Graph?	A Weighted Graph is a Graph in which each edge has a number (or weight) associated with it.

Resource summary

	Created by Carl Patchett about 7 years ago