Network Graphs and Theory
Network graphs (or graphs) consist of nodes (vertices) connected by edges. They model real-world systems such as transport routes, social networks, and internet connections.
What You Need to Know
Key Concept Diagram
A graph has vertices (nodes) connected by edges (arcs or links)
Degree of a vertex = number of edges connected to it
Eulerian path visits every edge exactly once (requires 0 or 2 vertices of odd degree)
Shortest path algorithms (e.g. Dijkstra) find minimum cost between nodes
Key Vocabulary
Vertex (node)
A point in a network graph representing an object or location
Edge (arc)
A connection between two vertices in a graph
Degree
The number of edges connected to a vertex
Eulerian path
A path that visits every edge in a network exactly once
Knowledge Check
Select the correct answer for each question. Click "Check Answer" to see if you are right.
Question 1
A graph has vertices A, B, C connected as: A-B, A-C, B-C. What is the degree of vertex A?
Question 2
For an Eulerian path to exist in a graph, there must be exactly:
Question 3
Network graphs are used in real life to model:
Key Concepts Summary
- ●A graph has vertices (nodes) connected by edges (arcs or links)
- ●Degree of a vertex = number of edges connected to it
- ●Eulerian path visits every edge exactly once (requires 0 or 2 vertices of odd degree)
- ●Shortest path algorithms (e.g. Dijkstra) find minimum cost between nodes