PDF 2 Graph Introduction Flashcards
1
Q
Definition of graphs and typologies
A
2
Q
Definition of adjacency between two nodes
A
3
Q
When an arc/edge is incident to a node?
A
4
Q
Concept of degree
A
5
Q
Definition of path for directed and undirected
A
6
Q
When two nodes are connected?
A
7
Q
What strongly connected means? And only connected?
A
8
Q
Difference between circuit and cycles
A
9
Q
Definition of bipartite graph
A
10
Q
Complete graph
A
11
Q
Definition of cuts
A
12
Q
Upper bound on the number of edges/arcs
A
13
Q
Dense and sparse graph, how to represent and different data structure
A
14
Q
Algorithm: Reachability Problem BFS and DFS
A
15
Q
Complexity of reachability problem
A
16
Q
Big O-notation
A
17
Q
Subgraph
A
18
Q
Tree
A
19
Q
Spanning tree
A
20
Q
Leaves
A
21
Q
First property of trees with proof by induction
A
22
Q
Second property unique path
A
23
Q
Third property of cycles
A
24
Q
Exchange property
A
