Fichas

Graphs

Carl Patchett Computing Science and Mathematics Inglés 10 fichas

Fichas del conjunto (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.