Table of Contents
- Understanding the Building Blocks: Vertices and Edges Notation
- Representing Graph Structures: Common Graph Notations
- Describing Graph Properties: Notation for Degree, Paths, and Cycles
- Operations and Variations: Notation for Graph Transformations and Special Graphs
- Beyond the Basics: Advanced Graph Theory Notation
- Conclusion: Mastering Discrete Math Graph Theory Notation
Understanding the Building Blocks: Vertices and Edges Notation
At the heart of every graph lies its fundamental components: vertices and edges. The standard notation for a graph, often denoted as 'G', typically comprises a set of vertices, usually represented by the letter 'V', and a set of edges, denoted by 'E'. Thus, a graph G can be formally defined as an ordered pair G = (V, E). The vertices, also known as nodes, are the individual points or entities within the graph. They are commonly represented by uppercase letters such as A, B, C, or by numbers like 1, 2, 3, especially in smaller or more abstract examples. For larger or more complex graphs, it's common to use a set notation like V = {v₁, v₂, v₃, ..., v
The edges, or links, represent the relationships or connections between these vertices. Each edge connects two vertices. The notation for an edge typically involves listing the two vertices it connects. For an undirected graph, where the connection has no specific direction, an edge between vertex 'u' and vertex 'v' is commonly written as {u, v} or simply uv. The order of the vertices within the curly braces or without any symbols between them does not matter, indicating that the edge {u, v} is the same as {v, u}. This symmetry is a defining characteristic of undirected graphs. The set E is then a collection of these unordered pairs of vertices, like E = {{u₁, v₁}, {u₂, v₂}, ...}.
In contrast, directed graphs, often called digraphs, introduce directionality to the edges. Here, an edge from vertex 'u' to vertex 'v' signifies a one-way connection. The notation for a directed edge is typically an ordered pair (u, v), where 'u' is the initial vertex (or tail) and 'v' is the terminal vertex (or head). The order is crucial; (u, v) is distinct from (v, u). The set of edges E in a directed graph would be a collection of such ordered pairs, E = {(u₁, v₁), (u₂, v₂), ...}. Understanding this distinction between unordered pairs for undirected graphs and ordered pairs for directed graphs is foundational to correctly interpreting graph theory concepts and notation.
Vertex Notation Variations
While uppercase letters and numerical indices are prevalent, the specific context can influence vertex notation. In some applications, vertices might be named with strings or identifiers that are more descriptive of the entities they represent. For instance, in a social network graph, vertices might be represented by actual names of people. However, for the sake of mathematical rigor and simplicity, abstract representations are usually preferred. The key is that each vertex in the set V must be distinct and uniquely identifiable. When working with subgraphs or specific parts of a larger graph, subsets of V might be denoted using superscripts or subscripts, such as V' or V₁, to indicate a particular collection of vertices under consideration.
Edge Notation Variations
Similar to vertices, edge notation can also have variations based on the type of graph and the information associated with the edges. Beyond simple {u, v} or (u, v) notation, edges can be assigned weights, labels, or capacities. In a weighted graph, an edge 'e' between 'u' and 'v' might be represented as (u, v, w) or {u, v, w}, where 'w' is the weight associated with that edge. These weights can represent costs, distances, strengths of connections, or other quantifiable metrics. Labels, on the other hand, might be used to categorize the type of relationship. For instance, in a semantic network, an edge might be labeled 'is-a' or 'has-part'. The set of edges E might then be represented as a set of tuples or objects that encapsulate not just the connectivity but also these additional attributes.
Representing Graph Structures: Common Graph Notations
Beyond the basic definition of G = (V, E), specific types of graphs have evolved their own common notational conventions. These conventions help to quickly convey the properties of a graph without needing lengthy descriptions. For instance, the number of vertices in a graph is typically denoted by |V|, and the number of edges is denoted by |E|. These cardinalities are fundamental metrics for analyzing graph size and complexity.
A simple graph is one that contains no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices. While not always explicitly notated as "simple graph G", the absence of these features is generally assumed unless stated otherwise. In contrast, a multigraph allows for multiple edges between the same pair of vertices and/or loops. If a graph is a multigraph, this property is usually explicitly mentioned.
Specific graph structures also have established notation. For instance, a complete graph, where every distinct pair of vertices is connected by a unique edge, is often denoted by K
Bipartite Graph Notation
A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets, U and W, such that every edge connects a vertex in U to one in W. This is commonly represented by G = (U ∪ W, E), where U ∩ W = ∅. Sometimes, a graph is explicitly stated as being bipartite, or the partitioning is provided. A complete bipartite graph, where every vertex in U is connected to every vertex in W, is denoted by K
Special Graph Types and Their Notation
There are numerous other specialized graph types, each with its own conventions. For example, a tree is a connected acyclic graph. A graph forest is a collection of disjoint trees. An adjacency matrix is a square matrix where the entry (i, j) is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. The adjacency matrix for a graph G with N vertices is an N x N matrix, often denoted by A or M.
The adjacency list is another common representation, where for each vertex, a list of its adjacent vertices is provided. This is particularly useful for sparse graphs (graphs with relatively few edges). The notation here is typically a mapping from each vertex v ∈ V to a list of its neighbors. For instance, Adj(v) = {u ∈ V | {v, u} ∈ E}. For directed graphs, this would be the set of vertices reachable from v by an outgoing edge.
Describing Graph Properties: Notation for Degree, Paths, and Cycles
The properties of vertices and edges are crucial for graph analysis. The degree of a vertex in an undirected graph is the number of edges incident to it. This is denoted by deg(v) or d(v). For instance, in the graph with edges {{1,2}, {1,3}, {2,3}}, the degree of vertex 1 is deg(1) = 2, as it is connected to vertices 2 and 3. The sum of degrees in any undirected graph is always equal to twice the number of edges, a theorem known as the Handshaking Lemma: Σ
In directed graphs, we distinguish between the in-degree and the out-degree of a vertex. The in-degree, denoted deg⁻(v), is the number of edges directed towards v, while the out-degree, denoted deg⁺(v), is the number of edges directed away from v. The total degree of a vertex in a directed graph is deg(v) = deg⁻(v) + deg⁺(v). The sum of in-degrees over all vertices equals the sum of out-degrees, and both sums equal the total number of edges.
Paths and cycles are fundamental concepts in graph theory. A path is a sequence of vertices where each adjacent pair in the sequence is connected by an edge. For an undirected graph, a path from vertex 'u' to vertex 'v' can be denoted as a sequence of vertices: u = v₀, v₁, v₂, ..., v
A cycle is a path that starts and ends at the same vertex, and all other vertices in the path are distinct. A simple cycle is one where only the start and end vertices are repeated. A cycle of length k is often denoted as C
Connectivity Notation
Connectivity in graphs refers to how well-connected the vertices are. The distance between two vertices, d(u, v), is the length of the shortest path between them. If no path exists, the distance is often considered infinite (∞). The eccentricity of a vertex 'v', denoted ε(v), is the greatest distance from 'v' to any other vertex in the graph. The diameter of a graph, diam(G), is the maximum eccentricity of any vertex in the graph. The radius of a graph is the minimum eccentricity.
A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. A graph that is not connected is said to have multiple connected components. A graph with only one connected component is simply called a connected graph.
Operations and Variations: Notation for Graph Transformations and Special Graphs
Graph theory also involves various operations that can be performed on graphs to create new ones or modify existing ones. Understanding the notation for these operations is crucial. For example, the complement of a graph G, denoted G', is a graph with the same vertex set V, but with an edge between two vertices if and only if there is no edge between them in G. So, G' = (V, E') where E' = {{u, v} | u, v ∈ V, u ≠ v, {u, v} ∉ E}.
The union of two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) is a graph G = G₁ ∪ G₂ with vertex set V = V₁ ∪ V₂ and edge set E = E₁ ∪ E₂. The intersection of two graphs G₁ and G₂ with the same vertex set is a graph G = G₁ ∩ G₂ with vertex set V = V₁ ∩ V₂ and edge set E = E₁ ∩ E₂.
A subgraph H of a graph G is a graph where the vertex set of H is a subset of the vertex set of G, and the edge set of H is a subset of the edge set of G, such that the endpoints of any edge in H are also in H. This relationship is denoted as H ⊆ G.
Edge Contraction and Minor Notation
Edge contraction is an operation where an edge {u, v} is removed, and the two vertices u and v are merged into a single new vertex. Any edges that were incident to either u or v are now incident to the new vertex. If this results in multiple edges between the new vertex and another vertex, these are typically retained unless the operation specifies creating a simple graph. The resulting graph is called a contraction of G.
A graph minor is obtained by a sequence of edge contractions, edge deletions, and vertex deletions. The notation for a graph H being a minor of G is often written as H ≺ G. Minor theory is a significant area within graph theory, particularly in relation to graph structure theorems.
Beyond the Basics: Advanced Graph Theory Notation
As graph theory applications become more sophisticated, so does the notation. For instance, in algorithms related to graph traversal, such as Breadth-First Search (BFS) or Depth-First Search (DFS), specific data structures and notation are used. For BFS, queues are typically employed, and the notation might involve marking vertices as visited or unvisited, and storing distances from a source vertex.
For weighted graphs, Dijkstra's algorithm uses notation for distances and predecessor vertices. The notation might involve arrays or sets to keep track of the minimum distance found so far to each vertex and the path taken to achieve that distance. Priority queues are often used in conjunction with this notation to efficiently select the next vertex to process.
Flow networks are a specialized type of directed graph with capacities on edges and a designated source and sink vertex. Notation in flow network problems often involves representing edge capacities and current flow values. For an edge (u, v), its capacity might be denoted as c(u, v), and the current flow as f(u, v). The notation for the residual graph, which is crucial for algorithms like Ford-Fulkerson, involves residual capacities.
Graph Coloring Notation
Graph coloring problems involve assigning colors to vertices such that no two adjacent vertices share the same color. The chromatic number of a graph G, denoted χ(G), is the minimum number of colors needed for a proper vertex coloring. For example, a bipartite graph has a chromatic number of 2 (unless it has no edges, then 1). The notation for a coloring itself can be a function, c: V → {1, 2, ..., k}, where k is the number of colors used.
Edge coloring involves assigning colors to edges such that no two adjacent edges share the same color. The chromatic index of a graph G, denoted χ'(G), is the minimum number of colors needed for a proper edge coloring. Vizing's theorem states that for any simple graph, χ'(G) is either Δ(G) or Δ(G) + 1, where Δ(G) is the maximum degree of any vertex in the graph.
Conclusion: Mastering Discrete Math Graph Theory Notation
A deep understanding of discrete math graph theory notation is not merely about memorizing symbols; it's about grasping the precise language used to define, describe, and manipulate complex relationships. From the fundamental sets V and E to specialized notations for graph types like K
