5.2 Networks

• Networks can be used to model transportation systems or social interactions.


  True
• Networks are only used to model transportation systems.

  False
• In an adjacency matrix, the rows and columns represent nodes
• For sparse graphs, adjacency lists are more storage-efficient than adjacency matrices
• Kruskal's algorithm adds edges in sorted order of weight.


  True
• In a network, nodes are also known as vertices
• Adjacency matrices are efficient for dense graphs.
• Steps of Prim's algorithm for finding the MST:

  1️⃣ Start with an arbitrary node as the root.

  2️⃣ Add the cheapest edge connecting a node in the tree to a node not in the tree.

  3️⃣ Repeat step 2 until all nodes are in the tree.
• Dijkstra's algorithm finds the shortest path between two nodes.
• A network is a mathematical model that represents a system of interconnected objects
• The nodes and edges together form the structure of a network
• What are the two common methods for representing networks?

  Adjacency matrices and lists
• How does an adjacency list represent a network?

  Each node has a list of adjacent nodes
• Steps in Prim's algorithm for finding the minimum spanning tree:

  1️⃣ Start with an arbitrary node as the root

  2️⃣ Add the cheapest edge connecting the tree to a node outside the tree

  3️⃣ Repeat until all nodes are in the tree
• What is a network in mathematical terms?

  Interconnected objects
• Networks can be used to model transportation systems.


  True
• Prim's algorithm builds the MST by merging smaller trees.

  False
• What is the first step in Kruskal's algorithm?

  Sort all edges
• For what type of graphs is Dijkstra's algorithm well-suited?

  Weighted, directed graphs
• Match the component of a network with its definition:

  Nodes (Vertices) ↔️ The individual objects in the network

  Edges (Arcs/Links) ↔️ The connections between nodes
• Adjacency matrices are efficient for sparse graphs.

  False
• The key difference between Prim's and Kruskal's algorithms is that Prim's builds a single tree
• What do edges in a network represent?

  Relationships between nodes
• What type of graphs are adjacency lists best suited for?

  Sparse graphs
• Steps of Dijkstra's algorithm for finding the shortest path:

  1️⃣ Initialize distances to infinity, except the starting node which is set to 0.

  2️⃣ Select the unvisited node with the smallest distance.

  3️⃣ Update the distances to its unvisited neighbors if a shorter path is found.

  4️⃣ Repeat steps 2-3 until all nodes are visited.