Home/Mathematics III Year/Team 8
Team 8

Graph Theory App

Build an app that lets users create simple graphs by entering edges, generates the adjacency matrix, computes vertex degrees, and checks basic graph properties like connectivity and regularity.

šŸŽÆ Learning Goals

  • ā–¹ Understand Vertices, Edges, and Degrees
  • ā–¹ Build and interpret an Adjacency Matrix
  • ā–¹ Apply Handshaking Theorem in practical code
  • ā–¹ Implement adjacency lists using nested application lists

šŸŒŽ Why This Matters

Graph theory is how Google Maps finds the shortest route, how LinkedIn suggests 'connections', and how the internet itself is built. When you study graphs, you are studying the science of connectivity.

šŸ“–Understanding Graph Theory Basics

Theory Masterclass
"

A graph is a collection of points (called vertices or nodes) connected by lines (called edges). Think of it like a social network: people are vertices, and friendships are edges. Key Terms: ā€¢ Vertex (Node): A point in the graph. Example: cities on a map. ā€¢ Edge: A connection between two vertices. Example: roads between cities. ā€¢ Degree: The number of edges connected to a vertex. If vertex A connects to B, C, D ā€” degree(A) = 3. Adjacency Matrix: A grid where entry [i][j] = 1 if vertex i connects to vertex j, else 0. For undirected graphs, the matrix is symmetric (same above and below diagonal). Example: 3 vertices, edges: 1-2, 2-3 Adjacency Matrix: 1 2 3 1 [0 1 0] 2 [1 0 1] 3 [0 1 0] Sum of all degrees = 2 Ɨ number of edges (Handshaking Theorem) Regular Graph: All vertices have the same degree. Complete Graph: Every vertex connects to every other vertex.

Mathematical Foundation

fxDegree(v) = sum of row v in adjacency matrix
fxSum of all degrees = 2 Ɨ |E| (Handshaking Theorem)
fxComplete graph Kn has n(n-1)/2 edges
fxRegular: all degrees are equal

šŸŽØPart A ā€” Designer View (UI Design)

Open MIT App Inventor ā†’ Switch to Designer view. Follow each step below to build the interface.

1

1. Screen Basics

ā€¢ Go to the **Properties** panel (right) for **Screen1**. ā€¢ Set **Title** to "Graph Explorer". ā€¢ Set **AlignHorizontal** to Center. ā€¢ Set **BackgroundColor** to Black.

2

2. Adding Nodes (Vertices)

ā€¢ Drag a **TextBox** from **User Interface**. Rename to 'NodeInput'. ā€¢ Set **Hint** to "Node name (e.g. A)". ā€¢ Drag a **Button** renamed 'AddNodeBtn'. Text: "ADD NODE". ā€¢ Drag a **Label** renamed 'NodesLbl'. Text: "Nodes: ".

3

3. Adding Connections (Edges)

ā€¢ Drag a **HorizontalArrangement** from **Layout**. ā€¢ Drag 2 **TextBoxes** inside ('Node1', 'Node2') and a **Button** ('AddEdgeBtn'). ā€¢ Set **Hint** for TextBoxes to "From" and "To". ā€¢ Change **AddEdgeBtn** text to "CONNECT".

4

4. Result Display

ā€¢ Drag a **Label** to the bottom. ā€¢ Rename to 'GraphInfoLbl'. ā€¢ This will show how many nodes and edges you have created.

šŸ§©Part B ā€” Blocks View (Logic & Calculation)

Switch to Blocks view. Now add the logic that makes your app actually work.

1

1. Switch to Blocks

ā€¢ Find the **Blocks** button at the top right and click it.

2

2. Setting up the Lists

ā€¢ Click the **Variables** drawer (Orange). Drag 'initialize global NodesList to'. ā€¢ Go to the **Lists** drawer (Light Blue). Drag 'create empty list' and snap it to your variable. ā€¢ Do the same for 'EdgesList'.

3

3. Adding a Node

ā€¢ Click **AddNodeBtn**. Drag the gold 'when AddNodeBtn.Click'. ā€¢ Go to the **Lists** drawer. Drag the 'add items to list' block and snap it inside. ā€¢ Snap [get global NodesList] as the list and [NodeInput.Text] as the item. ā€¢ To show it on screen: [set NodesLbl.Text to] [join "Nodes: " + NodesList].

4

4. Connecting Nodes (Edges)

ā€¢ Drag 'when AddEdgeBtn.Click' (Gold). ā€¢ Create a connection string using **Text** (Pink) 'join' block: [Node1.Text] + "-" + [Node2.Text]. ā€¢ Add this string to your **EdgesList**. ā€¢ Update the label: [set GraphInfoLbl.Text to] [join "Edges: " + EdgesList].

šŸ§ŖTesting Your App

  • āœ“3 vertices, edges 1-2, 2-3, 1-3 ā†’ Complete graph K3, all degrees = 2
  • āœ“4 vertices, edges 1-2, 3-4 ā†’ Not regular, not complete
  • āœ“Verify handshaking: sum of degrees should always be 2 Ɨ edges
  • āœ“Try adding a self-loop (1-1) and see what happens
  • āœ“Test adjacency matrix symmetry: entry [i][j] should equal [j][i]

šŸš€Bonus Challenges

Extra credit ā€” impress your instructor

  • ā˜…Draw the graph visually on a Canvas with circles and lines
  • ā˜…Add directed graph support (asymmetric adjacency matrix)
  • ā˜…Implement simple BFS to check if graph is connected
  • ā˜…Add 'Find Path' between two vertices
ā† Back to Mathematics III YearReview Basics ā†’