Ch 9. Graphs
9.1 Complete Graphs
A graph is a mathematical structure used to model relationships between objects. It consists of vertices (or nodes) which are the individual objects or entities, edges (or links) which are the connections between pairs of vertices, and paths which are sequences of edges that connect a sequence of vertices.
An edge is incident on a vertex if the vertex is one of its endpoints. A vertex is incident on an edge if it is connected by that edge. Two vertices are adjacent if they are connected by an edge.
Example 9.1
Let’s consider a graph with vertices [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex], and edges [latex]AB[/latex] and [latex]BC[/latex].
Vertex [latex]A[/latex] is adjacent to [latex]B[/latex]. Edge [latex]AB[/latex] is incident on vertices [latex]A[/latex] and [latex]B[/latex]. The path from [latex]A[/latex] to [latex]C[/latex] is [latex]A \rightarrow B \rightarrow C[/latex].
Parallel edges occur when two or more edges connect the same pair of vertices. Loops occur when edges connect a vertex to itself. An isolated vertex is a vertex with no incident edges. A simple graph is a graph with no loops or parallel edges.
Example 9.2
A graph with vertices [latex]\{ 1, 2, 3 \}[/latex] and edges [latex]\{ (1, 2), (2, 3) \}[/latex] is a simple graph.
If we add a loop at vertex [latex]2[/latex] and a second edge between [latex]1[/latex] and [latex]2[/latex], it becomes a non-simple graph.
A weighted graph assigns a numerical value (weight) to each edge. The weight of an edge represents cost, distance, time, or any other quantity. The length of a path is the sum of the weights of the edges in the path.
Example 9.3
Consider the following graph with vertices [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex] and edges [latex]AB[/latex], [latex]BC[/latex], and [latex]AC[/latex], with weights [latex]3[/latex], [latex]2[/latex], and [latex]5[/latex] respectively.
The shortest path from [latex]A[/latex] to [latex]C[/latex] is [latex]A \rightarrow B \rightarrow C[/latex] with a total length of [latex]3 + 2 = 5[/latex], which is equal to the direct edge [latex]AC[/latex].
A complete graph is a graph in which every pair of distinct vertices is connected by a unique edge. This graph is denoted by [latex]K_{n}[/latex], where [latex]n[/latex] is the number of vertices.
The total number of edges is equal to the number of distinct pairs of vertices. From [latex]n[/latex] vertices, the number of ways to choose [latex]2[/latex] distinct vertices is given by [latex]\frac{n(n-1)}{2}[/latex]. Each pair corresponds to exactly one edge in [latex]K_{n}[/latex]. Therefore, the total number of edges in [latex]K_{n}[/latex] is [latex]\frac{n(n-1)}{2}[/latex].
Example 9.4
[latex]K_{3}[/latex] has [latex]3[/latex] vertices and [latex]3[/latex] edges.
[latex]K_{4}[/latex] has [latex]4[/latex] vertices and [latex]6[/latex] edges.
[latex]K_{5}[/latex] has [latex]5[/latex] vertices and [latex]10[/latex] edges.
Complete graphs have several properties. They are symmetric, which means every vertex has the same number of connections. They are undirected, that is, the edges have no direction unless otherwise specified. They are dense, which means that they contain the maximum number of edges possible for a given number of vertices. The degree of each vertex in [latex]K_{n}[/latex] is [latex]n - 1[/latex].
Example 9.5
Consider [latex]K_{4}[/latex] with vertices [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], and [latex]D[/latex].
It has edges [latex]AB[/latex], [latex]AC[/latex], [latex]AD[/latex], [latex]BC[/latex], [latex]BD[/latex], and [latex]CD[/latex]. Each vertex is connected to [latex]3[/latex] other vertices, giving it a degree of [latex]3[/latex]. The total number of edges is [latex]\frac{4(4-1)}{2}=6[/latex].
A bipartite graph is a graph with vertices that can be divided into two disjoint sets [latex]V_{1}[/latex] and [latex]V_{2}[/latex] such that every edge connects a vertex in [latex]V_{1}[/latex] to one in [latex]V_{2}[/latex]. No edges exist between vertices within the same set.
Example 9.6
Let [latex]V_{1} = \{ 1, 2 \}[/latex], [latex]V_{2} = \{ A, B, C \}[/latex], and [latex]E = \{ (1, A), (1, B), (2, C) \}[/latex]. This is a bipartite graph.
A complete bipartite graph, denoted [latex]K_{m, n}[/latex], is a bipartite graph where every vertex in set [latex]V_{1}[/latex] is connected to every vertex in set [latex]V_{2}[/latex]. The graph contains [latex]mn[/latex] edges.
Example 9.7
Let [latex]V_{1} = \{ 1, 2 \}[/latex], [latex]V_{2} = \{ A, B, C \}[/latex], and [latex]E = \{ (1, A), (1, B), (1, C), (2, A), (2, B), (2, C) \}[/latex]. There are a total of [latex]2 \cdot 3 = 6[/latex] edges.
Real-World Example 9.1: Fully Connected Network
In a peer-to-peer communication system, each device must be able to communicate directly with every other device. This is modelled as a complete graph, where each device is a vertex, and each communication is an edge. For [latex]n[/latex] devices, the system requires [latex]\frac{n(n-1)}{2}[/latex] direct links.
This model is also used in neural networks with fully connected layers, in social networks where everyone knows everyone, and in testing scenarios where every component interacts with every other component.
