Graphs Flashcards
What is a graph?
This is a collection of distinct vertices and edges.
What is a subgraph?
This is a portion of a graph, which is also a graph itself.
What is the difference between a directed graph and an undirected graph?
A directed graph represents one-way connections, while an undirected graph represents two-way connections.
What is a path?
This is a sequence of edges between two nodes.
What is the length of a path?
This is the number of edges a path comprises.
What is a cycle?
This is a path that begins and ends at the same vertex.
What is an acyclic graph?
This is a graph which has no cycle.
What is a weighted graph?
This is a graph which has weights on its edges.
What is a connected graph?
This is a graph which has a path between each pair of distinct nodes.
What is a completed graph?
This a graph that not only has a path, but an edge between each pair of distinct vertices.
What are neighbors?
In an undirected graph, these are nodes connected by an edge. In a directed graph, these are only the nodes that are related by a one-way connection.
How many edges at most, can a directed graph with n vertices have?
n(n-1) vertices
How many vertices, at most, can a directed graph with n vertices have?
n(n-1]/2 vertices
What is a sparse graph?
This is a graph that has relatively few edges; O(n) edges
What is a dense graph?
This is a graph that has relatively many edges O(n^2) edges.
What is a topological order?
This is a graph where, when there is a directed edge between two nodes a and b, node a precedes node b.
What is a depth-first traversal?
This is a type of traversal where we go as deep as possible into the graph before searching the paths of other nodes.
What is a breadth-first traversal?
This is a type of traversal that visits the neighbors of a node before visiting neighbors’ neighbors.
What is the origin vertex?
This is the vertex where a traversal begins.