Graph Theory Concepts and Applications

The video introduces graphs as nonlinear structures composed of nodes and edges, explaining both undirected and directed graphs with examples like social networks and street maps. It covers two methods of graph representation: adjacency matrices and adjacency lists, discussing their pros and cons in terms of time and space complexity.

What is a graph primarily composed of?

• Vertices and lines

• Nodes and vertices

• Nodes and edges

• Edges and vertices

In an undirected graph, what does an edge represent in a social network?

• A data point

• A one-way connection

• A user profile

• A friendship or connection

How does a directed graph differ from an undirected graph?

• It has no nodes

• It has one-way connections

• It has two-way connections

• It has no edges

What is an example of a directed graph?

• A family tree

• A street map

• A computer network

• A social network

What is the time complexity to locate an edge in an adjacency matrix?

• O(n^2)

• O(n)

• O(log n)

• O(1)

What is a disadvantage of using an adjacency matrix?

• Limited to small graphs

• High space complexity

• High time complexity

• Difficult to implement

How is an adjacency list structured?

• As a list of linked lists

• As a tree structure

• As a single linked list

• As a 2D array

What is the space complexity of an adjacency list?

• O(V + E)

• O(E)

• O(V^2)

• O(V)

What is a benefit of using an adjacency list over a matrix?

• Faster edge lookup

• Less space usage

• More accurate

• Easier to implement

What is a common use of graphs in real-world applications?

• Modeling networks

• Storing data

• Calculating sums

• Sorting numbers