Unit 5: Graphs theory II

1. Planar Graphs

Definition

A graph is called a planar graph if it can be drawn in a plane such that no two edges cross each other except at their endpoints.

• Plane Graph: A specific drawing of a planar graph with no edge crossings.
• Non-planar Graph: A graph that cannot be drawn without at least one pair of edges crossing.

Regions (Faces)

When a planar graph is drawn without crossings, it divides the plane into disjoint areas called regions or faces.

• Infinite Region: Every plane graph has exactly one unbounded (infinite) region.
• Degree of a Region: The length of the boundary of the region.

Kuratowski’s Theorem

A graph is non-planar if and only if it contains a subgraph that is homeomorphic to (Complete graph with 5 vertices) or (Complete bipartite graph).

• : The "Pentagram" graph. It is the smallest non-planar complete graph.
• : The "Three Utilities" problem graph. It is the smallest non-planar bipartite graph.

2. Euler’s Formula

For any connected planar graph with vertices, edges, and regions (faces):

Essential Inequalities (Corollaries)

These are used to prove that specific graphs are non-planar.

1. Standard Inequality:
   For a simple connected planar graph with :
   

   
   If a graph violates this, it is non-planar.

2. Triangle-Free Inequality:
   If a connected planar graph has no triangles (cycles of length 3), such as bipartite graphs:
   

Examples

• Checking :
  • .
  • Check: .
  • This is False. Therefore, is non-planar.

3. Graph Coloring

Definition

Graph Coloring is the assignment of labels (colors) to the vertices of a graph such that no two adjacent vertices share the same color. This is technically known as Vertex Coloring.

Chromatic Number

The chromatic number of a graph , denoted as , is the minimum number of colors needed to color properly.

Chromatic Numbers of Standard Graphs

• Complete Graph (): (Every vertex is connected to every other vertex).
• Cycle Graph ():
  • If is even:
  • If is odd:
• Bipartite Graph (): .
• Planar Graphs: By the Four Color Theorem, every planar graph has .

Applications

• Map Coloring: Ensuring no two adjacent regions (states/countries) have the same color.
• Scheduling: Vertices represent classes/exams, edges represent conflicts (common students). The chromatic number is the minimum time slots required.

4. Trees and Their Properties

Definition

A Tree is a connected graph that contains no cycles.

• A Forest is a graph containing no cycles (a collection of disjoint trees).

Key Properties

Let be a tree with vertices and edges.

1. Edges count: .
2. Path Uniqueness: There is exactly one simple path between any pair of vertices in .
3. Acyclicity: Adding any edge to a tree creates exactly one cycle.
4. Connectivity: Removing any edge from a tree disconnects the graph (every edge is a bridge).

5. Rooted Trees

Definition

A Rooted Tree is a tree in which one specific vertex is designated as the root. The edges are directed away from the root.

Terminology

• Parent: The vertex is a parent of if there is a directed edge from to .
• Child: The vertex is a child of .
• Siblings: Vertices with the same parent.
• Leaf (Terminal Node): A vertex with no children (degree 1, excluding the root context).
• Internal Node: A vertex that has children.
• Level: The root is at level 0. Children of the root are at level 1, and so on.
• Height: The maximum level in the tree.

Types of Rooted Trees

• m-ary Tree: Every internal node has no more than children.
• Full m-ary Tree: Every internal node has exactly children.
• Binary Tree: An m-ary tree where . Children are designated as left child and right child.

6. Tree Traversal and Notation (Infix, Prefix, Postfix)

Traversal refers to the process of visiting each node in a rooted tree exactly once. These are critical for processing mathematical expressions represented as trees.

1. Preorder Traversal (Prefix)

Order: Root Left Subtree Right Subtree.

• Notation (Polish Notation): Operator comes before operands.
• Example:

2. Inorder Traversal (Infix)

Order: Left Subtree Root Right Subtree.

• Notation (Standard Arithmetic): Operator is between operands.
• Example:
• Note: Inorder traversal is only applicable to binary trees.

3. Postorder Traversal (Postfix)

Order: Left Subtree Right Subtree Root.

• Notation (Reverse Polish Notation): Operator follows operands.
• Example:

Example Conversion

Expression Tree for:

• Root:
• Left Child: (which has children A and B)
• Right Child:

Results:

• Infix: (Parentheses usually required for precedence)
• Prefix:
• Postfix:

7. Spanning Trees and Minimum Spanning Trees (MST)

Spanning Tree

A spanning tree of a connected, undirected graph is a subgraph that is a tree and includes all the vertices of .

• A graph may have multiple spanning trees.
• If has vertices, the spanning tree must have edges.

Minimum Spanning Tree (MST)

In a weighted graph (where edges have numerical costs/weights), an MST is a spanning tree where the sum of the edge weights is minimized.

Algorithms to find MST

1. Kruskal’s Algorithm (Greedy by Edges)

1. List all edges in ascending order of weight.
2. Select the edge with the smallest weight.
3. Select the next smallest edge, provided it does not form a cycle with previously selected edges.
4. Repeat until edges are selected.

2. Prim’s Algorithm (Greedy by Vertex)

1. Start from an arbitrary vertex.
2. Find the minimum weight edge connecting a vertex in the tree to a vertex outside the tree.
3. Add that vertex and edge to the tree.
4. Repeat until all vertices are included.

8. Decision Trees

Definition

A Decision Tree is a rooted tree used to model decisions and their possible consequences.

• Internal Nodes: Represent a "test" or a decision point.
• Branches: Represent the outcome of the test.
• Leaf Nodes: Represent a class label or a final decision/payoff.

Applications

• Sorting Algorithms: Establishing the lower bound of comparison-based sorts ().
• Game Theory: Modeling moves in games like Chess or Tic-Tac-Toe (Game Trees).
• Search Problems: Binary Search trees allow determining the location of an item in time.