Graph Theory

Where did this all begin?

• Walking puzzle in 18th century in a town in Russia called The Seven Bridges of Konigsberg (kaliningrad)

• The city of Konigsberg was split by a river into four land masses joined by seven bridges.

Solution made for Konigsberg

• Leonhard Euler in 1736 realized shapes, sizes and distances were irrelevant, except for how the parts connect, inventing the graph theory. 

• Closed walk exists if every vertex is even but each vertex (line connecting to each bridge) though in konigsberg were odd so it “simply cannot exist”

  • 1736 - Euler solves the bridges: graph theory begins

  • 1800 - Trees, circuit and maps + Four colour problem + Kirchhoff Cayley 

  • 1959 - Dijkstra publishes shortest path problem algorithm

  • Today - Powers maps, the internet and social network + AI exist 

What is Graph Theory?

• Study of graphs which are mathematical structures used to model pairwise relations of objects

What is an Undirected Graph?

• Consists of a set V(G) of vertices and a set E(G) of edges, joining two vertices

• Order and Size of a graph (G)

• Order of number of vertices (simply counting it)

• Order of G is the number of vertices - |V(G)|

• Size of G is the number of edges in G  - |E(G)|

• Multiple edges and loops

• = If there is more than one edge joining vertices u and v, then G contained a multiple edge

  • Edge from a vertex u to itself is called a loop

• Multigraph and simple graph

• = if a graph (G) contains multiple edges or loops then it is a multigraph, otherwise it is a simple graph

  • As long as vertices and edges are the same but interpreted/drawn differently it is not unique (it will still have the same output)

Degree and Neighborhood of a vertex

• = these are the degrees of a vertex where number of edges are incident to the vertex u (or simply how many connections are there) denoted by degg(u) 

• Neighborhood of us denoted by Ng(u)  is the set of all vertices adjacent to u

Walking on a graph:

• walk of length k from vertex v0 to vertex vk is a sequence of vertices such that two consecutive vertices are joined by an edge

  • EXCEPTION: You must pass through edges connected to the adjacent vertices

• The walk is called a path IF the vertices are distinct [no repetitions] = (path is also a walk)

• The walk is called a cycle if the vertices are distinct and v0 = vk (where you started is where you end BUT there should be no repetitions within the journey)

Connected vs Disconnected graph

• Graph is connected if there is always a path from a vertex to another

• Otherwise G is disconnected

Weighted Graph & Directed Graph

• Weighted Graph: All edges of G are assigned with numeral values (weights) 

• Directed Graph: where D consists of a set V(D) of vertices and a set A(D) of arcs formed using (ordered) pairs of vertices in V(D)

  • Arcs cannot be labeled the same (→)

  • An arc from u to v is written as [u,v], where u is the initial vertex while v is the terminal vertex

    • Order = number of vertices

    • Sizes = number of arcs

DJIKSTRA’s ALGORITHM

• Tool for determining a shortest path from a starting vertex s to any destination vertex

  • Applies to connected simple graphs (directed or undirected)

• State of vertex: distance value and status label

  • Distance value of a vertex represents an estimate of its distances, updated using the algorithm

• Status labels: Permanent or Temporary

  • Once a vertex reaches a permanent status we have determined its shortest distance from the starting point

STEPS IN DJIKSTRA’s ALGORITHM

1. Initialization

2. Distance Value Update

3. Current Vertex Designation Update

4. Repeat until Permanent