Graph Theory: Definitions and Applications

• This module explores graph theory and its applications to real-world problems, such as scheduling and pathfinding.
• It aims to find algorithms for optimal or good solutions to problems, balancing theory with practical applications.

Core Concept - Graphs

• Graphs are system structures describing underlying connectedness
• They are applicable to circuit board design and business efficiency

MTH3022 Main Objectives

• Learn the theory of graphs
• Explore the practical uses of graphs for solving mathematical problems

Definition of a Graph

• A graph G = (V, E, ε) consists of two sets (V and E) and a map (ε)
• V and E are finite in a finite graph.
• V consists of vertices or nodes
• E consists of edges
• Vertices 'a' and 'b' are adjacent (a ~ b) if { a, b} = ε(e) for some edge e ∈ E

Power Set Preliminary

• Power set of V, denoted P(V), is the set of all subsets of V.
• Pn(V) means subsets of V containing precisely n elements where n is a non-negative integer.

Example of Power Set Given V = {1, 2, 3}

• P(V) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
• P0(V) = {∅}
• P1(V) = {{1}, {2}, {3}}
• P2(V) = {{1, 2}, {1, 3}, {2, 3}}
• P3(V) = {{1, 2, 3}}
• Pn(V) = ∅ for all n ≥ 4.

Isomorphic Graphs

• Graphs with different names but the 'same' connections between vertices are the same graph

Graph Properties

• Loop-free Im(ε) ⊂ P2(V)
• Simple means loop-free and injective ε
• Complete means each pair of vertices is connected by precisely one edge, Im(ε) = P2(V) is simple

Morphisms of Graphs are function mapping relationships

• Given φ : V → V', φ* : P1(V) ∪ P2(V) → P1(V') ∪ P2(V')
• φ* ({a, b}) = {φ(a), φ(b)}
• φ* ({a}) = {φ(a)}
• A morphism of graphs (φ, ψ) : (V, E, ε) → (V', E', ε') is a pair of functions
• φ : V → V'
• ψ : E → E'
• satisfying the condition ε' ◦ ψ = φ* ◦ ε.

Composition of Graph Morphisms

• With (φ, ψ) : (V, E, ε) → (V', E', ε') and (φ', ψ') : (V', E', ε') → (V'', E'', ε'')
• Then (φ' ◦ φ, ψ' ◦ ψ) : (V, E, ε) → (V'', E'', ε'') is a morphism of graphs
• (φ', ψ') ◦ (φ, ψ) = (φ' ◦ φ, ψ' ◦ ψ)

Graph Invariants are unchanged or invariant under isomorphism

• Graphs that do not share such properties cannot be isomorphic

Definition of Graph Invariant

• A function 'f' takes an arbitrary graph G and returns a value f(G)
• 'f' is a graph invariant, if, f(G) = f(H) whenever G and H are isomorphic

Graph Invariant Examples

• Number of vertices of a graph
• Number of edges of a graph
• The smallest n ∈ N such that a morphism G → Kn exists, also known as the chromatic number
• A vertex's degree is the edges with it as an endpoint
• The list of degrees in ascending order is called the degree sequence of a graph

Additional Definitions

• Graphs can be defined by breaking edges into 'half-edges' that are glued together.
• In simple graphs, the edge set E identified with the image in P2(V) of the endpoint map ε.
• Graphs can have vertices or edges 'decorated' with extra information like road length or task completion times
• There is no universal terminology regarding graphs. Some consider directed graphs, others multigraphs or multidigraphs

Algorithm Attributes

• Finiteness - Must terminate in finite steps
• Definiteness - Algorithm step must be defined precisely
• Input - Requires a certain data before hand
• Output - Must have clearly specified output
• Effectiveness - Possible to work through steps

Algorithm Complexity

• The amount of time the algorithm needs to terminate
• Given real-valued functions f,g: N → R, f is of order g, written O(g), if there exist constants c ∈ R and N ∈ N
• Then for every n ∈ N we have that n ≥ N =⇒ |f(n)| ≤ c g(n)

Algorithm Complexity Examples

• Finding the smallest number in a list will have complexity O(n)
• Arranging a list of numbers in ascending order with a naive approach has complexity O(n^2 )

Common Algorithm Complexities

• Polynomial-time (O(p) for polynomial p) are efficient
• Exponential-time (O(2^n )) are impractical for large inputs

Complexity Classes

• Polynomial-time problem solvable by a polynomial-time algorithm on a deterministic Turing machine
• Class of problems is P
• A non-deterministic polynomial-time problem solvable by a polynomial-time algorithm on a non-deterministic Turing machine
• Class of problems is NP

Common Problems

• The non-deterministic Turing machine represents a theoretical best-case scenario
• NP includes any problem with a solution verifiable in polynomial time
• NP does NOT mean non-polynomial
• Proving if P=NP could be one of the biggest unsolved problems
• NP-complete problems if they could actually be in P then P=NP

Graph Colouring Basics

• Vertex colouring of a graph G is defined as a morphism of graphs G → Kn
• Kn denotes the complete graph on n vertices

Vertex Colouring

• Graph vertexes are labelled
• Adjacent vertices is such a way that no two have the same label
• Those labels are referred to as colors

Chromatic Numbers

• Given that for any n∈N there are no morphisms G → Kn if G has a loop, we can assume G is simple since multiple edges have no bearing on the problem
• The chromatic number of a graph G is the smallest number n such that there is a morphism of graphs G → Kn
• That is, it is the smallest number of colours needed to colour the vertices of G adjacent vertices have distinct colours
• The chromatic number of G is denoted as x(G)

Heuristic Algorithm

• Can produce good solutions, with no guarantee of optimality if a polynomial-time algorithm cannot be found to resolve a problem

Sensitivity Analysis

• Involves analyzing behavior by changing the input to an algorithm
• Helps find ways of algorithm improvement

Greedy colouring Algorithm

• The greedy colouring proceeds by picking any uncoloured vertex and using the shortest label for the neighbours

Welsh-Powell Algorithm

• Vertices into decreasing order
• Applies greedy colouring

Ribbon Graphs

• Are an attempt to remedy the lack of uniqueness in planar representation by considering the edge embeddings

Given the Definition of a Graph as a Quadruple

• Quadruple = (V, H, τ, ω) =
• V = vertices
• H = Half edges
• τ:H→H = fixed point free involution
• ω:H→V = Function

Vertex Colouring

• The smallest number of colours needed for colouring so adjacent vertices of a graph are distinct colour.
• The problem is NP complete and cannot be done at polynomial timing

Chromatic Polynomial facts

• Strictly speaking haven’t yet shown that PC is actually a polynomial, but this will emerge shortly
• It is a polynomial if you know every node in G
• We clearly know that chromatic number of G to be the smallest i for which a i = 0 but still not easy for the complete K, node

Map Colouring Facts

• Is colouring in such that every neighbouring regions do not share any colour
• Only four colours the minimum any map could only used.
• We can reinterpret a planar region if understood and have proper discussion.

Planarity

• A native Definition has to have no crossing edges in the plane drawing.
• All planar graph can have many planar representation
• This is the key idea, together all the problem and make use of this process

Ribbon Graphs Cont

• Are an attempt to remedy the lack of uniqueness in planar representation by considering the edge embeddings

Given the Definition of a Graph as Quadruple

• Quadruple = (V,K т,∞) where
• V = Vertices
• H = Half- edges
• т:H→H fixed point free involution
• ∞:H→V Function