Chapter 9. Graphs Flashcards
What is a list?
A linear data structure, where the elements are ordered in: A_1, A_2, A_3, … A_n. Order may or may not be relevant in this data structure.
What is a tree?
A generalization of a list, each branch is composed of lists.
What is a graph?
Essentially a graph is a collection of vertices (V) and edges (E).
What are the two main variations that we can have for a graph?
We can have a directed graph or an undirected graph.
What is an edge in a directed graph?
An edge from a directed graph is, a pair (v,w). Where v is the starting vertex and w is the ending vertex.
What is an edge in an undirected graph?
A pair (v,w) belonging to the set of edges. Such that v or w is the starting vertix and v or w but not both is the ending vertix.
What is the weight of an edge in a graph?
The cost associated with each edge. The cost of getting from one vertex to another.
Why are graph algorithms so important?
Because the algorithms can be used to solve many real world applications.
What is an edge?
A single path (v,w) from one vertex v to another vertex w.
What is the in-degree of a vertex v?
Indicates how many vertices go into v.
What is the out-degree of a vertex u?
Number of edges that go out of the vertex u.
When do we say that vertex w is adjacent to vertex v?
If and only if (v,w) is an element of the set of edges.
What is a path in a graph?
A sequence of vertices w_1, w_2, w_3, … w_n such that each pair (w_i, w_(i+1)) forms an edge.
What is the length of a path?
This is proportional to the number of edges in the path. Or to the number of vertices visited: N - 1.
What is a simple path?
Path in which all vertices are distinct, except that the first and last vertices can be the same. We don’t cross the same vertex more than once, unless that same vertex is the first and last one.
What is a cycle in a directed graph?
Path in a directed graph, of length at least 1 such that the starting and ending vertices are the same.
When is a cycle in a directed graph simple?
When all vertices are distinct except for possibly the first and last ones can be the same.
What is a cycle in an undirected graph?
Cycle such, that the first and last vertices are equal except that all edges must be distinct. Because for every (v,u), (u,v) is essentially the same edge.
When is a directed graph acyclic?
When the directed graph has no cycles.
What is a loop?
edge (v,v) such that it is a path from a vertex v to itself.
When is an undirected graph said to be connected?
When there is a path from every vertex to every other vertex.
When is a directed graph said to be strongly directed?
Whenever there is a path from every vertex to every other vertex
When is a directed graph said to be weakly connected?
When the underlying graph (graph with no arrows) is connected.
What is a complete graph, for an undirected graph?
If there is an edge for every pair of distinct vertices (v, w).
