Back to Subject

Unit 2: Graphs and Combinatorics

CSE333 — Combinatorial Studies-I 3 min read

I. Foundations and Governing Framework

Graph theory and combinatorics study discrete structures, their relationships, and the systematic enumeration of possible arrangements. A graph represents pairwise connections, while combinatorial methods provide principles for counting, constructing, and analyzing finite or countable configurations.

  • Graph model: A graph is an ordered pair (G=(V,E)), where (V) is a nonempty set of vertices and (E) is a set of edges joining vertices.
  • Graph conventions:
    • In a simple graph, edges are unordered pairs of distinct vertices; loops and parallel edges are excluded.
    • In a directed graph, each edge is an ordered pair ((u,v)), directed from (u) to (v).
    • The order of (G) is (|V|), and its size is (|E|).
  • Degree: The degree (\deg(v)) is the number of edges incident with vertex (v). A loop, when permitted, contributes (2) to the degree.
  • Handshaking lemma: For every finite undirected graph,
    TEXT
    sum(deg(v), v in V) = 2|E|.

    Here, (\deg(v)) is the degree of (v), and (|E|) is the number of edges.
  • Combinatorial viewpoint: Problems are solved by identifying allowable objects, constraints, and whether order or repetition matters.
  • Proof conventions: Common methods include direct counting, bijections, induction, contradiction, extremal arguments, and double counting.

II. Connectivity — Reachability in Graphs

Connectivity measures whether vertices can be reached from one another through sequences of adjacent edges.

A. connectivity

Connectivity distinguishes graphs that form a single linked structure from graphs divided into separate components.

  • Walk: A walk is a sequence
    TEXT
    v0, e1, v1, e2, ..., ek, vk

    where each edge (ei) joins (v{i-1}) to (v_i); vertices and edges may repeat.
  • Trail and path:
    • A trail contains no repeated edge.
    • A path contains no repeated vertex and therefore no repeated edge.
    • The length of either is the number (k) of edges used.
  • Connected graph: An undirected graph is connected if a path exists between every pair (u,v\in V).
  • Components: A connected component is a maximal connected subgraph. For example, a graph with edge sets ({ab,bc}) and ({de}) has two components: ({a,b,c}) and ({d,e}).
  • Cut structures:
    • A cut-vertex is a vertex whose deletion increases the number of components.
    • A bridge is an edge whose deletion increases the number of components.
    • Every edge of a tree is a bridge.
  • Vertex connectivity: (\kappa(G)) is the minimum number of vertices whose deletion disconnects (G) or reduces it to a single vertex.
  • Edge connectivity: (\lambda(G)) is the minimum number of edges whose deletion disconnects (G). For a nontrivial connected graph,
    TEXT
    kappa(G) <= lambda(G) <= delta(G),

    where (\delta(G)) is the minimum vertex degree.
  • Directed connectivity:
    1. A digraph is strongly connected if directed paths exist from (u) to (v) and from (v) to (u) for every pair.
    2. It is weakly connected if replacing directed edges by undirected edges produces a connected graph.

B. Applications and Characterization

Connectivity supports network reliability analysis and the construction of spanning structures.

  • Spanning tree: Every connected graph contains a spanning tree, meaning a connected, acyclic subgraph containing every vertex.
  • Tree criterion: A graph with (n) vertices is a tree precisely when it is connected and has (n-1) edges.
  • Traversal algorithms: Breadth-first search and depth-first search visit exactly the vertices in the start vertex’s component and run in (O(|V|+|E|)) time with adjacency lists.
  • Reliability interpretation: Larger values of (\kappa(G)) and (\lambda(G)) mean that more vertex or edge failures are required to disconnect the network.

III. Matching — Pairing Without Conflict

A matching selects edges that do not compete for endpoints, modeling assignments such as workers to jobs or students to projects.

A. matching

A matching (M\subseteq E) is a set of edges no two of which share a common endpoint.

  • Matched vertices: A vertex incident with an edge of (M) is saturated; every other vertex is unsaturated.
  • Matching types:
    • A maximal matching cannot be enlarged by adding another edge.
    • A maximum matching has the largest possible cardinality, denoted (\nu(G)).
    • A perfect matching saturates every vertex and therefore contains (|V|/2) edges.
  • Necessary parity condition: A graph of odd order cannot have a perfect matching, although even order alone does not guarantee one.
  • Augmenting path: Relative to (M), an augmenting path begins and ends at unsaturated vertices and alternates between edges outside and inside (M).
  • Berge’s theorem: A matching is maximum if and only if no augmenting path exists. Reversing membership along an augmenting path increases the matching size by one.
  • Bipartite graph: A graph is bipartite when (V=X\cup Y), (X\cap Y=\varnothing), and every edge joins a vertex in (X) to one in (Y).
  • Hall’s theorem: A bipartite graph has a matching saturating (X) if and only if
    TEXT
    |N(S)| >= |S| for every S subseteq X.

    Here, (N(S)) is the set of vertices in (Y) adjacent to at least one vertex of (S).
  • Worked example: If (X={x_1,x_2,x_3}) and every subset (S\subseteq X) has at least (|S|) neighbors, Hall’s condition guarantees three disjoint edges saturating (X), even without specifying which matching an algorithm will find.

B. Scope and Uses

Matching translates pairing constraints into a graph structure with testable optimality conditions.

  • Assignment model: Vertices represent participants and resources; an edge represents compatibility, and a maximum matching serves the greatest possible number of participants.
  • Weighted extension: When edge (e) has cost or benefit (w(e)), the objective may be to optimize
    TEXT
    sum(w(e), e in M).

    Here, (M) is a matching and (w(e)) is the weight assigned to edge (e).
  • Limitation: Ordinary matching imposes one-to-one assignment; capacities greater than one require variants such as (b)-matching or network flow.

IV. Coloring — Assigning Labels Under Constraints

Graph coloring assigns colors to graph elements so that conflicting elements receive different labels.

A. coloring

A proper vertex coloring is a function (c:V\to{1,\ldots,k}) such that adjacent vertices receive different colors.

  • Chromatic number: (\chi(G)) is the least (k) for which a proper (k)-coloring exists.
  • Basic values:
    • (\chi(K_n)=n) for the complete graph (K_n).
    • A nonempty bipartite graph has (\chi(G)=2).
    • An even cycle has chromatic number (2), while an odd cycle has chromatic number (3).
  • Bipartite characterization: A graph is bipartite if and only if it contains no odd cycle.
  • Greedy coloring: Given an ordering (v_1,\ldots,v_n), assign each vertex the smallest color not used by its already-colored neighbors.
    TEXT
    for each vertex v in the chosen order:
    assign the smallest available color to v
  • Greedy bound: The procedure uses at most (\Delta(G)+1) colors, where (\Delta(G)) is the maximum degree; the exact result may depend on vertex order.
  • Edge coloring: A proper edge coloring gives different colors to incident edges. Its minimum number of colors is the chromatic index (\chi'(G)).
  • Planar coloring: Every planar graph satisfies (\chi(G)\leq 4), the statement of the Four Color Theorem.
  • Worked example: In the cycle (C_5), alternating two colors forces the fifth vertex to match the first, although they are adjacent; therefore a third color is necessary and (\chi(C_5)=3).

B. Interpretation and Limitations

Coloring models conflicts in which simultaneously assigned objects must be separated.

  • Scheduling: Vertices can represent examinations, edges can represent shared students, and colors can represent time slots.
  • Register allocation: Variables with overlapping lifetimes are adjacent; colors correspond to available processor registers.
  • Computational limitation: Determining (\chi(G)) for an arbitrary graph is computationally difficult, so greedy heuristics are often used despite not always being optimal.

V. Counting — Enumerating Discrete Possibilities

Counting principles determine the number of outcomes without listing each outcome individually.

A. counting

Counting begins by deciding whether choices are mutually exclusive, sequential, ordered, or repetitive.

  • Sum rule: If disjoint alternatives contain (m) and (n) outcomes, their union contains (m+n) outcomes.
  • Product rule: If a process has (m) choices followed by (n) choices for each first choice, it has (mn) outcomes.
  • Permutations: The number of ordered arrangements of (r) distinct objects selected from (n) is
    TEXT
    P(n,r) = n!/(n-r)!.

    Here, (n\geq r\geq0), and (n!=n(n-1)\cdots1).
  • Combinations: The number of unordered (r)-element subsets of an (n)-element set is
    TEXT
    C(n,r) = n!/[r!(n-r)!].
  • Repetition: The number of (r)-element multisets selected from (n) types is
    TEXT
    C(n+r-1,r).
  • Inclusion-exclusion: For two finite sets,
    TEXT
    |A union B| = |A| + |B| - |A intersection B|.

    The subtraction corrects double counting of common elements.
  • Pigeonhole principle: Placing more than (n) objects into (n) boxes forces at least one box to contain at least two objects.
  • Worked example: A committee of (3) chosen from (8) people can be formed in
    TEXT
    C(8,3) = 8!/(3!5!) = 56

    ways because committee order is irrelevant.

B. Structural Counting

Combinatorial identities often follow by counting the same set in two different ways.

  • Binomial theorem:
    TEXT
    (x+y)^n = sum(C(n,k)x^(n-k)y^k, k=0 to n).

    Here, (n) is a nonnegative integer and (k) counts selections of the (y)-term.
  • Double counting: The handshaking lemma counts vertex-edge incidences once by degrees and once as two incidences per edge.
  • Bijection principle: If a one-to-one and onto correspondence exists between finite sets (A) and (B), then (|A|=|B|).

VI. Recurrence Relations — Defining Sequences from Earlier Terms

A recurrence relation specifies sequence values using preceding values together with sufficient initial conditions.

A. recurrence relations

Recurrences convert a combinatorial construction into an equation relating smaller instances.

  • General form:
    TEXT
    a_n = F(n, a_(n-1), a_(n-2), ..., a_(n-k)).

    Here, (a_n) is the (n)th term, (k) is the order, and (F) is a specified function.
  • Linear homogeneous recurrence:
    TEXT
    a_n = c_1 a_(n-1) + ... + c_k a_(n-k),

    where (c_1,\ldots,c_k) are constants and no independent forcing term appears.
  • Characteristic equation: Substituting (a_n=r^n) gives
    TEXT
    r^k - c_1 r^(k-1) - ... - c_k = 0.

    Distinct roots (r_1,\ldots,r_k) yield combinations (a_n=A_1r_1^n+\cdots+A_kr_k^n).
  • Nonhomogeneous case: A recurrence such as (an=2a{n-1}+3) requires a particular solution in addition to the homogeneous solution.
  • Initial conditions: An order-(k) recurrence generally requires (k) initial values to determine a unique sequence.
  • Worked example: For (an=2a{n-1}) and (a_0=3), repeated substitution gives
    TEXT
    a_n = 3(2^n).

B. Combinatorial Role

Recurrences arise by partitioning objects according to their first or last construction step.

  • Fibonacci model: Tiling a board of length (n) with tiles of lengths (1) and (2) gives (tn=t{n-1}+t_{n-2}), according to the final tile used.
  • Algorithm analysis: Divide-and-conquer running times may satisfy recurrences such as (T(n)=2T(n/2)+n).
  • Limitation: A recurrence defines terms efficiently but may not immediately reveal growth rate or a closed formula.

VII. Generating Functions — Encoding Sequences as Power Series

A generating function represents an entire sequence as coefficients of a formal power series, allowing algebraic operations to solve counting problems and recurrences.

A. generating functions

The ordinary generating function of ((an){n\geq0}) is a formal series whose coefficient of (x^n) is (a_n).

  • Definition:
    TEXT
    A(x) = sum(a_n x^n, n >= 0).

    Here, (A(x)) is the generating function, (a_n) is the sequence term, and (x) is a formal variable.
  • Geometric series:
    TEXT
    1/(1-x) = 1 + x + x^2 + ...,

    so the constant sequence (a_n=1) has generating function (1/(1-x)).
  • Coefficient notation: ([x^n]A(x)) denotes the coefficient of (x^n) in (A(x)).
  • Product principle: If (A(x)) and (B(x)) encode two choices, then
    TEXT
    [x^n](A(x)B(x)) = sum(a_k b_(n-k), k=0 to n).

    This convolution counts ways to divide total size (n) between the two choices.
  • Recurrence solving: Multiplying a recurrence by (x^n), summing over valid (n), and applying initial conditions converts the recurrence into an algebraic equation for (A(x)).
  • Worked example: For (an=2a{n-1}), (a0=3),
    TEXT
    A(x) - 3 = 2xA(x),
A(x) = 3/(1-2x).

    Since (1/(1-2x)=\sum    {n\geq0}2^nx^n), coefficient extraction gives (a_n=3\cdot2^n).

B. Scope and Interpretation

Generating functions turn coefficient enumeration into algebra while preserving the underlying discrete information.

  • Construction rules: Addition represents disjoint alternatives, while multiplication represents combining independent structures with additive sizes.
  • Closed forms: Rational generating functions often correspond to linear recurrences with constant coefficients.
  • Formal treatment: In combinatorics, convergence is frequently unnecessary because the series is manipulated coefficient by coefficient.
  • Limitation: Deriving (A(x)) does not finish the problem unless its coefficients can be extracted or estimated.
Previous
Unit 1
Next
Unit 3