Introduction to Graphs

Question 1

What are the conditions for a tree?

Answer 1

1. V-1 connected edges with no cycles
2. Removing edge disconnects
3. Acyclic, adding edge creates cycle
4. One simple path connects each pair of vertices

Question 2

When is a graph sparse/ dense?

Answer 2

• Sparse when few of possible edges present
• Dense when few edges are missing

Question 3

What is the space-time of Kruskal’s algorithm?

Answer 3

Space: E
Time: E log E