Graph/Tree Flashcards
What are two sets that determine a graph?
G(V, E). A set of vertices | V | and set of edges | E |.
What are graph properties?
- Weight (weighted/unweighted)
- Directionality (directed/undirected)
- Path
- Cycle
- Connectivity
- Vertex Degree
What is a weighted graph vs an un-weighted graph?
A graph that has numerical weights associated with every edge, while there are no weights in an un-weighted graph.
What is a directed graph vs un-directed graph?
In a directed graph, there are certain ways that could be travelled between nodes (like a one-way street) while in an undirected graph, either way can be travelled through edges (bidirectional).
What is a path?
A path is a sequence of vertices that are connected to edges.
ex. A->B->C->B->C
What is a simple path?
A simple path is a path with no vertices repeated.
ex. A->B->C
What is a cycle?
A cycle is a simple path that start and end at the same node.
ex. A->B->C->A
What is a connected graph?
A graph where there exists a path between every 2 vertices (otherwise disconnected).
What is a bipartite graph?
A graph where all vertices can be divided into two sets: V1 and V2 such that
V1 ⋃ V2 = V (all vertices are used) (Union is OR)
AND
V1 ⋂ V2 = Ø (no vertices belong to both V1 and V2) (Intersection is AND)
AND
Vertexes are adjacent only between elements of V1 and V2.
What is a vertex degree in an UNDIRECTED graph?
The number of edges adjacent to the particular vertex.
What are vertex degrees in a DIRECTED graphs composed of?
Indegrees and outdegrees.
What is an indegree in a directed graph?
The number of edges that point to a vertex.
What is an outdegree in a directed graph?
The number of edges that start from a particular vertex.
What is a clique?
A strongly connected, undirected graph in which every two vertices have an edge.
An “n-clique” clique has n edges.
What is the relationship amongst number of edges in a clique and the number of vertices.
Arithmetic series.
|E| = (V(V-1))/2
What are two ways graphs are represented?
Adjacency List / Adjacency Matrix (V x V).
When should you use an adjacency matrix to represent a graph?
Use an adjacency matrix when time is critical (only O(1), compared to O(n) for list).
When should you use an adjacency list to represent a graph?
Use an adjacency list when space is critical (O(E) (or O(n^2) for worst case compared to O(n^2) for matrix).
What is a tree?
A tree is a graph that is connected, acyclic, and undirected.
What is a root node in a tree?
The topmost node of a tree that does not have any parent node.
What can you do if a tree does not have a specified root?
You can take any vertex and name it as root.
What is a leaf node in a tree?
Leaf nodes are nodes which do not have any child nodes.
What is a parent node in a tree?
The node which is a predecessor of a node is called the parent of that node.
What is a child node in a tree?
The node which is the immediate successor of a node is called the child of that node.
