Module 5

Question 1

• MATHEMATICAL STRUCTURE THAT REPRESENTS RELATIONSHIPS BETWEEN PAIRS OF OBJECTS.
• DENOTED AS G = (V, E),
  o VERTICES (V): A FINITE SET OF DISTINCT POINTS REPRESENTING ENTITIES.
  o EDGES (E): A SET OF PAIRS OF VERTICES, INDICATING RELATIONSHIPS

Answer 1

Graphs

Question 2

Different Kinds of Graphs

Answer 2

Undirected Graphs
Complete Undirected Graphs
Directed Graphs (Disgraphs)
Completed Directed Graphs

Question 3

• IN AN ___________, EDGES DO NOT HAVE A DIRECTION ASSOCIATED WITH THEM.

Answer 3

Undirected Graphs

Question 4

• A ______________ IS ONE WHERE EVERY PAIR OF DISTINCT VERTICES IS CONNECTED BY AN EDGE.

Answer 4

Complete Undirected Graphs

Question 5

• IN A _______, EDGES HAVE A DIRECTION ASSOCIATED WITH THEM.

Answer 5

Directed Graphs (Disgraphs)

Question 6

• A ___________ HAS EVERY PAIR OF DISTINCT VERTICES CONNECTED BY TWO EDGES—ONE IN EACH DIRECTION

Answer 6

Completed Directed Graphs

Question 7

Graph Terminologies

Answer 7

Subgraphs
Path and Connectivity

Question 8

• IT CONSISTS OF SELECTED VERTICES AND EDGES FROM THE ORIGINAL GRAPH.

Answer 8

Subgraphs

Question 9

• Path
  o A SEQUENCE OF VERTICES CONNECTED BY EDGES FROM A STARTING VERTEX TO AN ENDING VERTEX.
• Simple Path
  o A PATH WHERE ALL VERTICES ARE DISTINCT.
• Simple Cycle
  o A SIMPLE PATH THAT FORMS A CLOSED LOOP, BEGINNING AND ENDING AT THE SAME VERTEX.
• Connectivity
  o TWO VERTICES ARE CONNECTED IF THERE EXISTS A PATH BETWEEN THEM

Answer 9

Path and Connectivity

Question 10

o A SEQUENCE OF VERTICES CONNECTED BY EDGES FROM A STARTING VERTEX TO AN ENDING VERTEX

Answer 10

Path

Question 11

o A PATH WHERE ALL VERTICES ARE DISTINCT.

Answer 11

Simple Path

Question 12

o A SIMPLE PATH THAT FORMS A CLOSED LOOP, BEGINNING AND ENDING AT THE SAME VERTEX.

Answer 12

Simple Cycle

Question 13

o TWO VERTICES ARE CONNECTED IF THERE EXISTS A PATH BETWEEN THEM

Answer 13

Connectivity

Question 14

Advanced Concepts

Answer 14

Weighted Concepts
Spanning Trees

Question 15

• REFERS TO THE PROCESS OF VISITING ALL VERTICES AND EDGES OF A GRAPH SYSTEMATICALLY TO PERFORM SPECIFIC OPERATIONS OR SEARCHES.

Answer 15

Graph Traversals

Question 16

• BEGIN AT A CHOSEN START VERTEX AND EXPLORE AS DEEPLY AS POSSIBLE ALONG EACH BRANCH BEFORE BACKTRACKING.
  o DEEP EXPLORATION: FOCUSES ON DIVING DEEPLY INTO THE GRAPH’S STRUCTURE, BEFORE BACKTRACKING.
  o STACK-BASED BACKTRACKING: USES A STACK OR RECURSION
  o TO TRACK AND BACKTRACK FROM DEAD-END PATHS.

Answer 16

Depth First Search (DFS)

Question 17

• BEGIN AT A CHOSEN START VERTEX AND EXPLORE ALL ITS NEIGHBORS BEFORE MOVING ON TO THE NEXT LEVEL OF NEIGHBORS.
• Characteristic of BFS
  o LAYER-BY-LAYER EXPLORATION: FOCUSES ON EXPLORING ALL NEIGHBORS OF A VERTEX BEFORE MOVING ON TO THE NEXT
  o QUEUE-BASED TRAVERSAL: USES A QUEUE TO MAINTAIN ORDER AND PRIORITIZE VISITING NEIGHBORS BEFORE DEEPER EXPLORATION.

Answer 17

Breadth First Search(BFS)

Question 18

SUITABLE FOR EXPLORING DEEPER PATHS

Answer 18

Depth First Search (DFS)

Question 19

IDEAL FOR SHORTEST PATH FINDING

Answer 19

Breadth First Search(BFS)

Question 20

• CHOOSE AN INITIAL VERTEX AND PLACE IT IN U.
• SELECT THE VERTEX CONNECTED TO U BY THE LOWEST-COST EDGE AND ADD IT TO U AND ITS CORRESPONDING EDGE TO T.
• REPEAT STEP 2 UNTIL U INCLUDES ALL VERTICES (U = V), CREATING THE MST.

Answer 20

Prim’s Algorithm

Question 21

• START WITH THE EDGE OF LEAST COST AS THE INITIAL EDGE IN T.
• CONSIDER EDGES IN NON-DECREASING ORDER OF COST.
• INCLUDE AN EDGE IF IT DOESN’T CREATE A CYCLE IN T; REJECT OTHERWISE.
• EMPHASIZE THE SIGNIFICANCE OF SORTING EDGES IN NON-DECREASING ORDER FOR COMPUTATIONAL EFFICIENCY.

Answer 21

Kruskal Algorithm

Question 22

• ASSIGNS VERTICES TO DIFFERENT CLASSES BASED ON THEIR CALCULATED SHORTEST DISTANCES FROM THE SOURCE.
• ITERATIVELY DETERMINES THE SHORTEST PATH FROM A SINGLE SOURCE VERTEX TO ALL OTHER VERTICES.

Answer 22

Dijkstra Algorithm

Question 23

• COMPUTES THE SHORTEST PATHS BETWEEN ALL PAIRS OF VERTICES IN A WEIGHTED GRAPH.
• STEPS OF ______
  o INITIALIZATION OF MATRICES A AND PATH.
  o ITERATIVE COMPUTATION OF SHORTEST PATHS USING INTERMEDIATE VERTICES

Answer 23

Floyds Algorithm