Unit 5: Graphs Theory II

I. Foundations of Graph Theory

Graph theory studies relationships represented by vertices and edges. A graph is written as (G=(V,E)), where (V) is a nonempty set of vertices and (E) is a set of edges joining pairs of vertices. This unit develops structural, geometric, optimization, and symbolic applications of graphs.

A. Governing Definitions and Conventions

The following concepts provide the framework used throughout the unit.

• Order and size: The order of (G) is (|V|), the number of vertices; its size is (|E|), the number of edges.
• Degree: The degree (\deg(v)) is the number of edges incident with vertex (v). A loop contributes (2) to the degree.
• Handshaking lemma: In every finite undirected graph, the sum of all vertex degrees equals twice the number of edges.

Σ deg(v) = 2|E|
v∈V

• (\deg(v)): degree of vertex (v).
• (|E|): number of edges.
  • Path and cycle: A path joins a sequence of distinct vertices through adjacent edges; a cycle is a closed path whose first and last vertices coincide.
  • Connected graph: A graph is connected when a path exists between every pair of vertices.
  • Simple graph: A simple graph has no loops and no multiple edges between the same pair of vertices.
  • Weighted graph: A weighted graph assigns a numerical weight, such as distance or cost, to every edge.

II. Planarity and Graph Embeddings

Planarity concerns whether a graph can be represented in a plane without edge crossings, apart from edges meeting at common endpoints.

A. Planar graphs

A planar graph is a graph that can be drawn in the plane so that no two edges cross.

• Plane graph: A plane graph is a particular crossing-free drawing of a planar graph.
• Faces: A plane embedding divides the plane into regions called faces, including one unbounded exterior face.
• Embedding dependence: Different drawings may produce differently shaped faces, but a connected planar graph has the same number of faces in every plane embedding.
• Edge bound: For a simple, connected planar graph with (v\geq 3),

e ≤ 3v - 6

• (v): number of vertices.
• (e): number of edges.
  • Bipartite edge bound: If the graph is also bipartite, every face has boundary length at least (4), giving (e\leq 2v-4).
  • Nonplanar graphs: (K5), the complete graph on five vertices, and (K{3,3}), the complete bipartite graph with parts of size three, are nonplanar.
  • Kuratowski’s theorem: A finite graph is planar exactly when it contains no subdivision of (K5) or (K{3,3}).
  • Example: (K_5) has (v=5) and (e=10), but (3v-6=9). Since (10>9), it cannot be planar.

III. Euler’s Planar Relation

Euler’s formula links the vertices, edges, and faces of a connected plane graph and is fundamental to planar graph analysis.

A. Euler formula

For every finite, connected plane graph, the numbers of vertices (v), edges (e), and faces (f) satisfy:

v - e + f = 2

• Conditions: The formula applies directly to a connected graph with a fixed crossing-free plane embedding.
• Disconnected form: If a plane graph has (c) connected components, then

v - e + f = 1 + c

• (c): number of connected components.
  • Structural meaning: Adding an edge that creates a cycle increases both (e) and (f) by one, preserving (v-e+f).
  • Tree case: A connected acyclic graph has only the exterior face, so (f=1). Euler’s formula then yields (e=v-1).
  • Example: A connected plane graph with (v=8) and (e=12) has

f = 2 - v + e = 2 - 8 + 12 = 6

• Limitation: Euler’s formula is a necessary structural condition for planarity, but satisfying it alone does not prove that a graph is planar.

IV. Graph Colouring

Graph colouring assigns labels called colours under specified adjacency restrictions, commonly to model conflicts and resource allocation.

A. Colouring of a graph and chromatic number

A proper vertex colouring assigns colours to vertices so that adjacent vertices receive different colours; the chromatic number (\chi(G)) is the minimum number required.

• Colour class: All vertices assigned one colour form an independent set because no two of them are adjacent.
• Basic values:
  • An edgeless graph has (\chi(G)=1).
  • A nontrivial bipartite graph has (\chi(G)=2).
  • A complete graph (K_n) has (\chi(K_n)=n).
• Cycles: An even cycle has chromatic number (2), while an odd cycle has chromatic number (3).
• Clique lower bound: If (G) contains a complete subgraph (K_r), then (\chi(G)\geq r).
• Degree upper bound: A greedy colouring uses at most (\Delta(G)+1) colours, where (\Delta(G)) is the maximum vertex degree.
• Four-colour theorem: Every planar graph has a proper vertex colouring using at most four colours.
• Greedy method: Process vertices in an order and assign each vertex the smallest colour not used by its already-coloured neighbours. The result may depend on the ordering and need not be optimal.
• Example: The triangle (K_3) requires three colours because every vertex is adjacent to the other two; hence (\chi(K_3)=3).

V. Trees

A tree is the simplest connected network: it connects all its vertices without containing redundant cyclic routes.

A. Tree graph and its properties

A tree is a connected, undirected graph containing no cycles.

• Unique-path property: Exactly one simple path exists between every pair of vertices; two distinct paths would create a cycle.
• Edge count: A tree with (n) vertices has exactly (n-1) edges.
• Minimal connectivity: Removing any edge disconnects a tree, so every edge is a bridge.
• Maximal acyclicity: Adding an edge between two existing nonadjacent vertices creates exactly one cycle.
• Leaves: Every tree with at least two vertices has at least two vertices of degree (1), called leaves or pendant vertices.
• Degree relation: For a tree with (n) vertices,

Σ deg(v) = 2(n - 1)
v∈V

• Equivalent tests: For a graph with (n) vertices, any two of connectedness, acyclicity, and having (n-1) edges imply the third.
• Example: A connected graph with (10) vertices and (9) edges is a tree; if connectedness is known, the edge count guarantees acyclicity.

VI. Hierarchical Trees

A rooted tree distinguishes one vertex as an origin, creating levels and parent-child relationships.

A. Rooted tree

A rooted tree is a tree in which one designated vertex is called the root.

• Parent and child: For each non-root vertex (v), its parent is the adjacent vertex immediately before (v) on the unique path from the root; (v) is its child.
• Siblings: Vertices with the same parent are siblings.
• Ancestors and descendants: Vertices on the root-to-(v) path before (v) are its ancestors; vertices for which (v) lies on their root path are its descendants.
• Level or depth: The depth of (v) is the number of edges from the root to (v); the root has depth (0).
• Height: The height of the rooted tree is the greatest depth of any vertex.
• Internal vertices and leaves: An internal vertex has at least one child, while a leaf has none.
• (m)-ary tree: In an (m)-ary tree, every internal vertex has at most (m) children. A binary tree has at most two.
• Full (m)-ary relation: If every internal vertex has exactly (m) children and there are (i) internal vertices, then the total number of vertices is (n=mi+1).

VII. Network-Connecting Trees

Spanning trees preserve all vertices of a connected graph while selecting enough edges to maintain connectivity without cycles.

A. Spanning and minimum spanning tree

A spanning tree of a connected graph (G) is a subgraph that contains every vertex of (G) and is itself a tree; a minimum spanning tree minimizes total edge weight.

1. Spanning tree:

   • Edge count: Every spanning tree of a graph with (n) vertices has (n-1) edges.
   • Existence: A finite undirected graph has a spanning tree exactly when it is connected.
   • Construction: Repeatedly remove cycle edges while preserving connectivity, or add edges that connect different components.

2. Minimum spanning tree:

   • Objective: Minimize

W(T) = Σ w(e)
       e∈T

• (T): selected spanning tree.
• (w(e)): weight of edge (e).
• Kruskal’s algorithm: Sort edges by increasing weight and add an edge whenever it does not create a cycle.
• Prim’s algorithm: Start at any vertex and repeatedly add the least-weight edge joining the current tree to an outside vertex.
• Uniqueness: Distinct edge weights guarantee a unique minimum spanning tree, although equal weights may still produce uniqueness in some graphs.
• Application: Minimum spanning trees model low-cost road, cable, pipeline, and communication networks.

VIII. Decision Structures

A decision tree represents sequential tests and their possible outcomes as a rooted branching structure.

A. Decision tree

A decision tree is a rooted tree in which internal vertices represent decisions or tests, edges represent outcomes, and leaves represent final results.

• Interpretation: A root-to-leaf path records one complete sequence of decisions.
• Binary decisions: A yes/no test produces at most two children, giving a binary decision tree.
• Cost: The depth of a leaf measures the number of decisions needed to reach its outcome.
• Worst-case complexity: The tree’s height gives the maximum number of decisions required.
• Information bound: A binary decision tree of height (h) has at most (2^h) leaves. Distinguishing (n) outcomes therefore requires

h ≥ ⌈log₂ n⌉

• (h): minimum worst-case number of binary decisions.
• (n): number of distinguishable outcomes.
  • Example: Distinguishing among eight equally possible outcomes needs at least (\lceil\log_2 8\rceil=3) binary decisions in the worst case.
  • Applications: Decision trees support searching, comparison-based sorting, diagnosis, classification, and algorithm complexity analysis.

IX. Expression Trees and Notation

Arithmetic expressions can be represented by rooted trees and traversed in different orders to produce standard symbolic notations.

A. Infix, prefix, and postfix notation

Infix, prefix, and postfix forms differ in the position of an operator relative to its operands.

1. Infix notation:

   • Form: The operator appears between operands, as in A + B.
   • Ambiguity control: Parentheses and precedence rules are needed; (A+B)*C differs from A+(B*C).
   • Tree traversal: Inorder traversal processes left subtree, root, then right subtree.

2. Prefix notation:

   • Form: The operator precedes its operands, as in + A B.
   • Alternative name: Prefix notation is also called Polish notation.
   • Tree traversal: Preorder traversal processes root, left subtree, then right subtree.

3. Postfix notation:

   • Form: The operator follows its operands, as in A B +.
   • Alternative name: Postfix notation is called reverse Polish notation.
   • Tree traversal: Postorder traversal processes left subtree, right subtree, then root.

• Expression-tree structure: Internal vertices contain operators, while leaves contain operands.
• Worked conversion: For the infix expression (A+B)*C:

Infix:   (A + B) * C
Prefix:  * + A B C
Postfix: A B + C *

• Evaluation: Prefix and postfix expressions require no parentheses when every operator has a fixed arity. Postfix can be evaluated using a stack: push operands, pop the required operands when an operator appears, apply it, and push the result.