Graph Theory Basics: Vertices, Edges, and Types

• A graph G = (V, E) is composed of a nonempty set V of vertices (or nodes) and a set E of edges, where each edge connects one or two vertices known as endpoints.
• An edge connects its endpoints in a graph.

Terminology

• A simple graph’s edges connect two different vertices, with no two edges linking the same pair of vertices.
• Multigraphs can have multiple edges connecting the same two vertices; if m distinct edges connect vertices u and v, {u, v} has a multiplicity of m.
• A loop is an edge that connects a vertex to itself.
• Pseudographs may have loops and multiple edges connecting the same pair of vertices.

Directed Graphs

• A directed graph (or digraph) G = (V, E) includes a nonempty collection of vertices (or nodes) V and a set of directed edges (or arcs) E.
• Each edge is associated with an ordered pair of vertices, where the start is at u and the end is at v for the directed edge (u,v).
• Graphs with unordered edge endpoints are undirected graphs.
• A simple directed graph contains no loops or multiple edges.
• A directed multigraph may have multiple directed edges; when m directed edges extend from vertex u to vertex v, the edge (u, v) has a multiplicity of m.

Computer Networks

• The appropriate graph type should be used in a graph model to capture key application features.
• Data centers are represented by the vertices with communication links, represented by the edges in computer network models.
• A simple graph is used in a computer network model when the concern is whether two data centers are connected by a communications link.
• A multigraph is used to model numerous links among data centers.
• A pseudograph is needed to model a computer network with diagnostic links at data centers, because loops are needed.

Graph Terminology: Summary

• Key questions that can be asked when building a graph model are:
• Are the edges of the graph undirected, directed, or both?
• If the edges are undirected, are multiple edges present connecting the same pair of vertices?
• If the edges are directed, are multiple dierected edges present?
• Are loops present?

Other graph Applications

• Graph Models can be used for the following:
• Social Networks
• Communications Networks
• Information Networks
• Software Design
• Transportation Networks
• Biological Networks

Basic Terminology

• Two vertices u and v in an undirected graph G are adjacent (or neighbors) if there is an edge e between u and v; e is incident with vertices u and v and connects u and v.
• The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is the neighborhood of v; if A is a subset of V, N(A) is the set of all vertices in G that are adjacent to at least one vertex in A.
• The degree of a vertex in an undirected graph is the number of edges incident with it, with a loop at a vertex contributing two to the degree of that vertex; the degree of vertex v is denoted as deg(v).

Degrees of Vertices

• According to the Handshaking Theorem, if G = (V, E) is an undirected graph with m edges, then 2m = ∑ deg(v).
• An undirected graph contains an even number of vertices of odd degree

Directed Graphs (Continued)

• In directed Graphs the in-degree of a vertex v, denoted deg-(v), is the number of edges that terminate at v.
• While the out-degree of v, denoted deg+(v), is the number of edges with v as their initial vertex.
• A loop at a vertex contributes 1 to both the in-degree and the out-degree of the vertex.
• For graphs with directed edges the total number of edges |E| = ∑ deg-(v) = ∑ deg+(v).

Types of Simple Graphs: Complete Graphs

• A complete graph on n vertices, denoted by Kn, is the simple graph with exactly one edge between each pair of distinct vertices.

Types of Simple Graphs: Cycles and Wheels

• A cycle Cn for n ≥ 3 consists of n vertices , and edges {V1, V2}, {V2, V3},..., {Vn-1, Vn}, {Vn ,V₁}.
• A wheel Wₙ is obtained via the addition of a vertex to a cycle Cn for n ≥ 3, connecting the new vertex with the vertices in C n using new edges.

Types of Simple Graphs: n-Cubes

• An n-dimensional hypercube, or n-cube, Qₙ, is a graph with 2ⁿ vertices that symbolize all bit strings of length n, where an edge exists if two vertices differ by one bit position.

Bipartite Graphs

• A simple graph G is bipartite if V can be partitioned into two disjoint subsets V₁ and V₂ such that every edge connects a vertex in V₁ and a vertex in V2; there are no edges that connect two vertices in V₁ or in V₂.

Complete Bipartite Graphs

• A complete bipartite graph Kₘ,ₙ contains a vertex set partitioned into two subsets V₁ with a size of m and V₂ with a size of n such that an edge runs from every vertex in V₁ to every vertex in V₂.

Representing Graphs

• An adjacency list is used to represent a graph without multiple edges; it specifies the vertices adjacent to each graph vertex.
• The adjacency matrix stores a 1 in its (i, j)th entry, when the corresponding vertices are adjacent using a zero-one matrix.
• Sparse graphs contain few edges relative to the total number of possible edges.
• Dense graphs contain a high percentage of the possible edges, an adjacency matrix is preferable.
• Adjacency matrices can represent graphs with loops and multiple edges.
• A given loop at vertex vᵢ is represented by a 1 at the (i, i)th position of the matrix.
• When multiple edges link the same pair of vertices vᵢ and vⱼ or when multiple loops exist at the identical vertex, the (i, j)th entry is equivalent to the number of edges linking the vertex pair.
• The adjacency matrices represent directed graphs.
• For a directed graph G = (V, E), the corresponding matrix contains a 1 at position (i, j) if there is an edge extending from vᵢ to vⱼ given that v₁, v₂, … vₙ represents a list of vertices.
• Incidence matrix representation of graphs.

Incidence Matrices

• An undirected graph G = (V, E) contains vertices v₁, v₂, … vₙ and edges e₁, e₂, … eₘ.
• The incidence matrix with respect to the ordering of V and E is the n x m matrix M = [mᵢⱼ], where mᵢⱼ is 1 when edge eⱼ is incident with vᵢ.

Connectivity

• A path is the sequence of edges that starts at a graph vertex and travels along graph edges/vertices.

Paths in Undirected Graphs

• A path of length n from u to v in G is a sequence of n edges e₁, …, eₙ of G for which there exists a sequence x₀ = u, x₁, …, xₙ₋₁, xₙ = v of vertices such that eᵢ has, for i = 1, …, n, the endpoints xᵢ₋₁ and xᵢ.
• For a simple graph, the path contains the vertex sequence x₀, x₁, … xₙ.
• A circuit begins and ends at the same vertex (u = v), has a length greater than zero, and is termed a circuit.
• A path or circuit passes through vertices x₁, x₂, …, xₙ₋₁ and traverses edges e₁, …, eₙ
• A path or circuit is simple if it does not reuse edges.

Connectedness in Undirected Graphs

• A graph is connected if there is a path between every pair of vertices.
• A graph that is disconnected, is disconnected when vertices or edges are removed.
• A connected component of a graph G refers to a connected subgraph of G.
• A graph G that is not connected has two or more connected components.

Connectedness in Directed Graphs

• A directed graph which is strongly connected has a path from a to b and from b to a if both a and b are vertices in the graph.
• A path between every two vertices in the underlying undirected graph defines a weakly connected directed graph.
• Strongly connected components/ strong components are the subgraphs of a directed graph G that show strong connectivity but cannot be contained in larger strongly connected subgraphs.