Intro to Graphs

Introduction to Graphs

• Course: CIS 2910

• Instructor: Joe Sawada

• Institution: University of Guelph

Problems Solved Using Graphs

• Graphs model real-world problems and facilitate solutions using well-known graph algorithms.

  • Snow Plowing: Determines the minimum cost to clear roads for a clear path between major towns.

  • Matching: Finds the optimal matching of students to co-op jobs or healthcare personnel to hospitals.

  • Scheduling: Computes the minimum number of time slots needed for final exams without conflicts.

  • Information Visualization: Challenges whether a data flow diagram can be redrawn without edge crossings.

Minimum Spanning Trees

Example: Snow Plowing

• A graph representing the road network between towns in Southern Ontario is presented.

• Costs associated with plowing roads are represented as weights on each edge.

• The goal is to determine the fewest roads needing to be plowed to ensure all towns are connected.

• Towns include: Windsor, Toronto, Barrie, Kingston, Oshawa, Hamilton, London, Guelph, Waterloo.

Matching

Maximal Matching Example

• Scenario: A co-op coordinator aims to maximize student-job placements.

• Each student has specific job interests, represented by unique vertices.

• Edges represent interest connections between students and jobs.

• Objective: Find the maximal set of edges such that no two edges share a common endpoint (ensuring unique job assignments).

Scheduling

Exam Scheduling Conflict

• Problem: What is the minimum number of time slots required to schedule exams to avoid conflicts?

• Each course is a vertex, and edges represent conflicts (sharing a student).

• Conflict example presented for courses: cs 100, math 101, chem 101, cs 200, chem 200, bio 101, cs 400, hist 200, geog 101, hist 101.

• This scenario can be abstracted into a graph-coloring problem, asking for the minimum number of colors (time slots) required for conflict-free scheduling.

Information Visualization

Planar Graphs

• Challenge: Is it possible to redraw a data flow diagram without crossing edges?

• This problem translates into a graph drawing issue - can a graph be redrawn as a planar graph where no edges intersect?

Simple Undirected Graphs

Definition

• A simple undirected graph G = (V, E) consists of:

  • A non-empty set of vertices (V).

  • A set of edges (E) as unordered pairs of distinct vertices in V.

• Example: An undirected graph representation of a social network.

Multigraphs

Definition

• A multigraph allows multiple edges between pairs of vertices.

• A simple graph is a special case of a multigraph.

• If a multigraph allows loops (edges connecting a vertex to itself), it is called a pseudograph.

• Example: A multigraph representing data center connectivity with multiple links.

Directed Graphs

Definition

• A directed graph G = (V, E) comprises:

  • A non-empty set of vertices (V) and an edge set (E) comprising ordered pairs.

• Key differences from simple undirected graphs:

  1. Edges are ordered pairs: (u, v) ≠ (v, u).

  2. Vertices in pairs are not necessarily distinct (loops are allowed).

• Example: A directed graph indicating ideas' influences between individuals.

Size and Order of Graphs

Definitions

• Order: Number of vertices in a graph (denoted by n).

• Size: Number of edges in a graph (denoted by m).

• Maximum edges in a simple undirected graph: n^2.

• Maximum edges in a directed graph: also n^2.