Graph Types

Simple Graphs

Definition

Simple graph: undirected, no loops, no parallel edges. Vertices connected by edges at most once. Basic modeling unit.

Properties

Edges: unordered pairs of distinct vertices. Degree: count of edges incident on vertex. No self-connection allowed.

Examples

Social networks without multiple friendships, road networks ignoring one-way roads, basic connectivity models.

Directed Graphs (Digraphs)

Definition

Directed graph: edges are ordered pairs (u,v). Direction indicates edge from u to v. Allows asymmetric relationships.

In-degree and Out-degree

In-degree: number of edges arriving at vertex. Out-degree: number of edges leaving vertex. Sum of all in-degree equals sum of all out-degree.

Applications

Modeling flow: internet links, workflows, precedence constraints, citation networks.

Weighted Graphs

Definition

Weighted graph: edges assigned numerical values (weights). Weights represent cost, length, capacity, or strength.

Weighted Simple and Directed Graphs

Can be simple or directed. Weight function w: E → ℝ or subset. Allows optimization and shortest path computations.

Use Cases

Routing, network design, resource allocation, transportation networks.

W : E → ℝw(e) = weight of edge eTotal weight = ∑ w(e) over selected edges

Bipartite Graphs

Definition

Vertices divided into two disjoint sets U, V. Edges only connect vertices from U to V, none inside a set.

Properties

No odd cycles: characterization of bipartite graphs. Matching theory applies extensively.

Examples

Job assignment problems, matching students to schools, modeling relationships between two classes.

Complete Graphs

Definition

Simple graph where every pair of distinct vertices connected by an edge. Denoted K_n for n vertices.

Properties

Edges count: n(n-1)/2. Maximum edge density, maximal connectivity.

Significance

Benchmark graphs, test cases for algorithms, extremal combinatorics.

Number of edges in K_n = n(n-1)/2Example: K_4 has 6 edges

Planar Graphs

Definition

Graphs that can be drawn on a plane without edge crossings. Embedding exists with no intersecting edges.

Kuratowski's Theorem

Planar iff no subgraph homeomorphic to K_5 or K_{3,3}. Characterizes planar graphs structurally.

Applications

Geographical maps, circuit design, network layouts.

Multigraphs

Definition

Graphs allowing multiple edges (parallel edges) between the same pair of vertices. Loops may be allowed.

Properties

Edge multiplicity tracked. Degree counts all incident edges including multiples and loops.

Applications

Transportation systems (multiple routes), communication networks with multiple channels.

Trees

Definition

Connected acyclic simple graphs. Unique path between every vertex pair. |E| = |V| - 1.

Rooted Trees

One vertex designated root. Defines parent-child relationships and hierarchy.

Use Cases

Data structures, hierarchical organization, spanning trees in networks.

Tree properties:Connected & AcyclicEdges = Vertices - 1Unique path between nodes

Special Graph Classes

Cyclic Graphs

Contain at least one cycle. Used to detect loops in systems.

Regular Graphs

All vertices have equal degree. Denoted k-regular if degree k.

Complete Bipartite Graphs

Bipartite graphs where every U vertex connects to every V vertex. Denoted K_{m,n}.

Graph Representations

Adjacency Matrix

Square matrix A where A[i][j] = 1 if edge exists, else 0. Efficient for dense graphs.

Adjacency List

List of neighbors for each vertex. Space-efficient for sparse graphs.

Incidence Matrix

Matrix with rows as vertices, columns as edges. Entries indicate vertex-edge incidence.

Adjacency Matrix (A):A[i][j] = { 1 if edge (i,j) exists 0 otherwise }Size: n x n for n vertices

Key Graph Properties

Connectivity

Graph connected if path exists between every vertex pair. Components: maximal connected subgraphs.

Degree Sequence

List of vertex degrees, often sorted. Used to characterize graphs.

Planarity and Colorability

Planar graphs can be vertex-colored with at most four colors (Four Color Theorem).

Applications of Graph Types

Computer Networks

Modeling nodes and connections. Directed graphs for data flow, weighted for latency/cost.

Operations Research

Weighted graphs for shortest path, bipartite graphs for assignment problems.

Social Sciences

Simple graphs for social ties, multigraphs for multiple relations, trees for hierarchies.

References

• Diestel, Reinhard. Graph Theory. Springer, Vol. 173, 2017, pp. 1-300.
• West, Douglas B. Introduction to Graph Theory. Prentice Hall, 2nd ed., 2001, pp. 1-600.
• Bollobás, Béla. Modern Graph Theory. Springer, 1998, pp. 1-400.
• Bondy, J.A., and Murty, U.S.R. Graph Theory with Applications. North-Holland, 1976, pp. 1-600.
• Harary, Frank. Graph Theory. Addison-Wesley, 1969, pp. 1-350.