By the end of this chapter, you will be able to: - accurately use key graph theory terms as required in the workplace - correctly identify and apply different types of graphs in practical situations - accurately represent graphs to meet workplace standards - correctly apply graph theory concepts to real-world workplace applications
Mastering these skills will help you solve complex problems efficiently and communicate clearly in your technical field.
Graph theory is a fundamental area of discrete mathematics with widespread applications in ICT, particularly in network design, data organization, and algorithm optimization. For ICT technicians in Kenya, understanding graph theory enables efficient problem-solving in tasks such as routing, network topology analysis, and resource allocation. This chapter introduces key graph terminologies and explores their mathematical properties through practical examples relevant to ICT systems.
A graph \(G\) is a mathematical structure used to model pairwise relations between objects. Formally, a graph is defined as an ordered pair \(G = (V, E)\), where \(V\) is a set of vertices (nodes) and \(E\) is a set of edges connecting pairs of vertices. In ICT, graphs represent networks where vertices are devices or data points, and edges are communication links or relationships.
$$G = (V, E)$$
Example 1: A small LAN has 4 computers connected in a network. List the graph representation if computers are vertices and connections are edges: connections are between computer 1 and 2, 2 and 3, 3 and 4.
Given:
\(V = \{1, 2, 3, 4\}\)
Edges \(E = \{(1,2), (2,3), (3,4)\}\)
$$G = (V, E) = (\{1, 2, 3, 4\}, \{(1,2), (2,3), (3,4)\})$$
Answer: Graph \(G\) with 4 vertices and 3 edges representing the LAN.
Example 2: In a wireless sensor network, 5 sensors are deployed. The communication links exist between sensors 1-2, 1-3, 2-4, and 3-5. Write the graph \(G\).
Given:
\(V = \{1, 2, 3, 4, 5\}\)
\(E = \{(1,2), (1,3), (2,4), (3,5)\}\)
$$G = (V, E) = (\{1, 2, 3, 4, 5\}, \{(1,2), (1,3), (2,4), (3,5)\})$$
Answer: Graph \(G\) represents the sensor network with 5 nodes and 4 edges.
Example 3: A data center has 6 servers connected with 7 links. The edges are \((1,2), (1,3), (2,4), (3,5), (4,6), (5,6), (2,5)\). Define the graph.
Given:
\(V = \{1, 2, 3, 4, 5, 6\}\)
\(E = \{(1,2), (1,3), (2,4), (3,5), (4,6), (5,6), (2,5)\}\)
$$G = (V, E) = (\{1, 2, 3, 4, 5, 6\}, \{(1,2), (1,3), (2,4), (3,5), (4,6), (5,6), (2,5)\})$$
Answer: Graph \(G\) models the server connections with 6 vertices and 7 edges.
A vertex (or node) is a fundamental unit or point in a graph representing an entity such as a computer, server, or data point. Vertices are usually denoted by elements of a set \(V\). In ICT networks, vertices correspond to devices or components requiring analysis.
Example 1: Given a graph with vertices \(V = \{A, B, C, D\}\), how many vertices are there?
Given: \(V = \{A, B, C, D\}\)
Number of vertices \(= |V| = 4\)
Answer: 4 vertices
Example 2: In a network graph with vertices numbered 1 to 10, find the total count of vertices.
Given: \(V = \{1, 2, \ldots, 10\}\)
Number of vertices \(= |V| = 10\)
Answer: 10 vertices
Example 3: A graph representing a data flow system has vertices \(V = \{v_1, v_2, \ldots, v_n\}\). If \(n = 15\), what is the number of nodes?
Given: \(n = 15\)
Number of vertices \(= 15\)
Answer: 15 vertices
An edge in a graph connects two vertices, representing a relationship or link between them. Edges can be undirected or directed, indicating bidirectional or unidirectional connections respectively. Edges are elements of the set \(E\), where each edge is a pair of vertices.
Example 1: In a graph with vertices \(V = \{1, 2, 3\}\), edges are \((1,2)\) and \((2,3)\). How many edges?
Given: \(E = \{(1,2), (2,3)\}\)
Number of edges \(= |E| = 2\)
Answer: 2 edges
Example 2: A network graph has vertices \(V = \{A, B, C, D\}\) and edges \((A,B), (B,C), (C,D), (D,A), (B,D)\). Count edges.
Given: \(E = \{(A,B), (B,C), (C,D), (D,A), (B,D)\}\)
Number of edges \(= 5\)
Answer: 5 edges
Example 3: In a data center network, 8 servers are connected with 12 communication links. Represent the number of edges.
Given: \(V = 8\), number of edges \(= 12\)
Answer: 12 edges
The degree of a vertex is the number of edges incident to it. For undirected graphs, the degree counts all edges connected to the vertex. For directed graphs, the degree splits into in-degree and out-degree counting incoming and outgoing edges respectively.
Example 1: In an undirected graph with vertex \(v\) connected to vertices \(a, b, c\), find the degree of \(v\).
Given: Edges incident on \(v\) are \((v,a), (v,b), (v,c)\)
Degree of \(v\) = 3
Answer: Degree of vertex \(v\) is 3
Example 2: In a directed graph, vertex \(x\) has 4 incoming edges and 2 outgoing edges. Find total degree, in-degree, and out-degree.
Given: In-degree = 4, Out-degree = 2
Total degree = In-degree + Out-degree = 4 + 2 = 6
Answer: Total degree = 6, In-degree = 4, Out-degree = 2
Example 3: In a network graph, vertex \(5\) has edges \((5,2), (3,5), (5,6), (1,5)\). Calculate in-degree and out-degree.
Given: Outgoing edges from 5: \((5,2), (5,6)\) → 2 edges
Incoming edges to 5: \((3,5), (1,5)\) → 2 edges
In-degree = 2, Out-degree = 2
Answer: In-degree = 2, Out-degree = 2
A path is a sequence of vertices connected by edges, with no vertex repeated, representing a route through a graph. Paths are essential in routing algorithms for network communication.
Example 1: In a graph with vertices \(1, 2, 3, 4\) and edges \((1,2), (2,3), (3,4)\), find the path from vertex 1 to 4.
Given: Edges connecting \(1 \to 2 \to 3 \to 4\)
Path: \(1 \to 2 \to 3 \to 4\)
Answer: Path length = 3 edges
Example 2: Determine if there is a path from node \(A\) to \(D\) in a graph with edges \((A,B), (B,C), (C,D)\).
Given: Edges \(A \to B \to C \to D\)
Path exists: \(A \to B \to C \to D\)
Answer: Path exists with length 3
Example 3: In a directed graph, edges are \((1,3), (3,4), (4,2)\). Is there a path from vertex 1 to 2?
Given: Edges \(1 \to 3 \to 4 \to 2\)
Path exists
Answer: Yes, path length is 3 edges
A cycle is a path where the first and last vertices are the same, with no other vertex repeated. Cycles indicate loops in network topologies, which can affect data flow and routing.
Example 1: In a graph with edges \((1,2), (2,3), (3,1)\), identify if a cycle exists.
Given: Path \(1 \to 2 \to 3 \to 1\)
Cycle detected
Answer: Cycle of length 3 exists
Example 2: Check for cycles in graph with edges \((A,B), (B,C), (C,D), (D,A)\).
Given: Path \(A \to B \to C \to D \to A\)
Cycle detected
Answer: Cycle of length 4 exists
Example 3: In a directed graph with edges \((1,2), (2,3), (3,4), (4,2)\), is there a cycle?
Given: Path \(2 \to 3 \to 4 \to 2\)
Cycle exists
Answer: Yes, cycle involving vertices 2, 3, 4
A connected graph is one where there is a path between every pair of vertices. Connectivity ensures communication feasibility in networks.
Example 1: A graph with vertices \(\{1,2,3\}\) and edges \((1,2), (2,3)\). Is the graph connected?
Given: Paths exist between all vertices
Answer: Graph is connected
Example 2: Graph with vertices \(\{A,B,C,D\}\) and edges \((A,B), (B,C)\). Vertex \(D\) isolated.
Given: No path from \(D\) to others
Answer: Graph is not connected
Example 3: In a network graph of 5 nodes with edges \((1,2), (2,3), (3,4), (4,5)\), is the graph connected?
Given: Path exists between any two nodes
Answer: Graph is connected
A directed graph or digraph has edges with a direction, indicating unidirectional relationships. Digraphs model data flow or command structures in ICT.
Example 1: Represent a digraph with vertices \(\{1,2,3\}\) and edges \((1 \to 2), (2 \to 3)\).
Given: Directed edges as pairs with arrows
Answer: Digraph with 3 vertices and 2 directed edges
Example 2: In a digraph with edges \((A \to B), (B \to C), (C \to A)\), determine if it contains a cycle.
Given: Path \(A \to B \to C \to A\)
Answer: Digraph contains a cycle
Example 3: A data packet flows from node 1 to 4 via nodes 2 and 3. Edges: \((1 \to 2), (2 \to 3), (3 \to 4)\). Write the digraph.
Given: Directed edges representing data flow
Answer: Digraph models packet flow in sequence
An undirected graph has edges without direction, representing mutual relationships. It models symmetric connections like peer-to-peer networks.
Example 1: Graph with vertices \(\{1,2,3\}\) and edges \(\{(1,2), (2,3)\}\). Is it undirected?
Given: Edges without arrows
Answer: Yes, undirected graph
Example 2: Network of 4 computers connected with links \((1,2), (2,3), (3,4), (4,1)\). Identify graph type.
Given: Connections are bidirectional
Answer: Undirected graph with cycle
Example 3: In a social network, friendships are mutual. Represent 3 friends \(A, B, C\) connected pairwise.
Given: Edges \(\{(A,B), (B,C), (A,C)\}\)
Answer: Undirected graph representing mutual friendships
Define a graph \(G\) with vertex set \(V = \{1, 2, 3, 4, 5\}\) and edges connecting \(1-2, 2-3, 3-4, 4-5, 5-1\). Write the graph representation and identify if it contains a cycle. (5 marks)
Given a directed graph with vertices \(V = \{A, B, C, D\}\) and edges \((A \to B), (B \to C), (C \to D)\), find the in-degree and out-degree of vertex \(B\). (5 marks)
In an undirected graph with vertices \(1, 2, 3, 4\), edges are \((1,2), (2,3), (3,4), (4,1), (1,3)\). Calculate the degree of vertex 1. (5 marks)
Determine whether the graph with vertices \(\{1, 2, 3, 4\}\) and edges \((1,2), (2,3)\) is connected. Justify your answer. (5 marks)
For a digraph with edges \((1 \to 2), (2 \to 3), (3 \to 1)\), explain if there is a cycle, and write the sequence of vertices forming the cycle. (5 marks)
Create a free account to open more of this chapter.
Free: practical guides, quick cards, workplace scenarios and more.
Create a free accountThis chapter introduced the fundamental concepts of graph theory starting with key terminologies such as graph, vertex, edge, degree of a vertex, path, cycle, connected graph, directed graph, and undirected graph. It then explored different types of graphs including bar graphs, line graphs, histograms, and ogive curves, highlighting their distinct characteristics. Various methods for representing graphs were discussed, focusing on adjacency matrices, adjacency lists, and incidence matrices as tools to organize and analyze graph data. The chapter concluded by examining practical applications of graphs in areas such as computer networks, social networks, transport networks, and scheduling or task management. Understanding these concepts is essential for modeling relationships and solving complex problems in discrete mathematics and related fields. The knowledge gained provides a foundation for further study and application in diverse technological and organizational contexts.
In a directed graph representing a computer network, vertex \(A\) has 3 outgoing edges and 2 incoming edges. Calculate the total degree of vertex \(A\). (2 marks)
A network graph has 7 vertices and 10 edges. If the graph is undirected and connected, calculate the average degree of the vertices. (3 marks)
At the start of this chapter we promised you would be able to:
Tick each one you can genuinely do.
So, are you there yet?
You're competent when you can confidently do 50% or more of what this chapter promised.
Sign in to record how you're doing.