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 MasterclassA 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
🎨Part A — Designer View (UI Design)
Open MIT App Inventor → Switch to Designer view. Follow each step below to build the interface.
Set up the screen
Title: "Graph Theory Explorer". Dark theme.
Create vertex count input
Label: "Number of vertices" TextBox named VertexCount (NumbersOnly, Hint: "4") Button: "Initialize Graph"
Create edge input area
Label: "Add edges (enter vertex pairs)" HorizontalArrangement: TextBox V1, Label "—", TextBox V2 Button: "Add Edge" ListView named EdgeList to show all added edges.
Add action buttons
Row 1: "Show Adjacency Matrix", "Show Degrees" Row 2: "Check Regular", "Check Complete" Row 3: "Total Edges", "Reset Graph"
Create matrix display
A large Label named MatrixLabel with monospace font to display the adjacency matrix in grid format. Another Label for degree information.
🧩Part B — Blocks View (Logic & Calculation)
Switch to Blocks view. Now add the logic that makes your app actually work.
Initialize the graph data structure
When InitializeButton.Click: 1. Read n = number(VertexCount.Text) 2. Create a list of n×n zeros (use nested loops to fill a list) 3. Store as global variable "adjMatrix" 4. Create a list "edges" to track all edges 5. Clear the ListView
Add Edge logic
When AddEdgeButton.Click: 1. Read v1 and v2 from TextBoxes 2. Validate: both must be between 1 and n 3. Set adjMatrix at position [(v1-1)*n + v2] = 1 4. Set adjMatrix at position [(v2-1)*n + v1] = 1 (undirected) 5. Add "v1 — v2" to the edges ListView
Display Adjacency Matrix
When ShowMatrixButton.Click: 1. Build a string row by row 2. For each row i (1 to n): For each column j (1 to n): Append adjMatrix[(i-1)*n + j] + " " Append newline 3. Display the formatted string in MatrixLabel
Calculate vertex degrees
When ShowDegreesButton.Click: For each vertex i (1 to n): degree = 0 Sum all values in row i of adjacency matrix Display: "Vertex i: degree = " + degree Also show total: "Sum of degrees = " + totalDegrees And: "Number of edges = " + totalDegrees/2
Check if graph is Regular
When CheckRegularButton.Click: 1. Calculate degree of each vertex 2. If all degrees are equal → "Graph is Regular (degree k)" 3. Else → "Graph is NOT regular"
Check if graph is Complete
When CheckCompleteButton.Click: 1. Calculate degree of each vertex 2. If every degree = n-1 → "Graph is Complete (Kn)" 3. Else → "Graph is NOT complete" Also verify: edges = n(n-1)/2
Reset logic
When ResetButton.Click: Clear all lists, TextBoxes, and Labels. Reset the graph to empty state.
🧪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