Graph Theory Models

Definitions, Models, and Representations

1. Graph Basics

Definition of a Graph

A graph $G=(V;E)$ consists of:

  • V (Vertices): Finite set of nodes (points).
  • E (Edges): Finite set of links connecting vertices.

Endpoints: The vertices associated with an edge.

Neighbor: A vertex joined by an edge to another vertex.

p q s r

Graph A (Simple Graph)

2. Terminology & Classification

Types of Edges

  • Proper Edge: Joins two distinct vertices.
  • Self-loop: Joins a vertex to itself.
  • Multi-edge: Two or more edges with identical endpoints.

Types of Graphs

  • Simple Graph: No self-loops, no multi-edges.
  • Multi-graph: Has multi-edges but NO self-loops.
  • General Graph: May have self-loops and multi-edges.
  • Null Graph: Empty vertex/edge sets.
    Trivial Graph: 1 vertex, 0 edges.

Neighborhoods

Open Neighborhood $N(v)$: Set of all neighbors of $v$.
Closed Neighborhood $N[v]$: $N(v) \cup \{v\}$.

Practice on Graph A (above):

3. Directed Graphs (Digraphs)

Definitions

  • Arc (Directed Edge): Has a Tail and a Head.
  • Oppositely Directed: Same vertices, opposite direction.
  • Multi-arc: Same tail and same head.
  • Mixed Graph: Contains both directed and undirected edges.
u v w c d f g h k

Graph D: General Digraph

4. Interactive Analysis

Analyze Graph B (General)

u v w
How many self-loops?
How many multi-edges?
Make it simple?

Analyze Graph D (Digraph)

Refer to Graph D visual in Section 3.

Identify Opposite Arcs
Identify Multi-arcs
Is it a simple digraph?

5. Formal Specifications

1. Adjacency Table (Simple Graphs)

Used for simple graphs like Graph A. Lists neighbors for each vertex.

Vertex Neighbors
p q, r, s
q p, s
r p, s
s p, q, r

2. Incidence Table (General Graphs)

Used for general graphs (Graph B). Columns are edges, rows list endpoints.

Edge a b c d f g h k
Endpts u
u		 u
u		 u
v		 u
w		 v
w		 v
w		 v
w		 v
v

3. Digraph Specs (Head & Tail)

For digraphs (Graph D), we specify Head ($v^h$) and Tail.

Edge c: Head(c) = v, Tail(c) = u

Edge g: Head(g) = w, Tail(g) = v

Edge h: Head(h) = v, Tail(h) = w

Edge k: Head(k) = v, Tail(k) = v

6. Real World Models

Roadmap Model

Mixed Graph

Vertices are landmarks. Directed edges are one-way streets; undirected are two-way.

🗺️

Corporate Hierarchy

Digraph

Vertices are staff. Edges represent reporting lines (Supervisors -> Staff).

🏢
Next: Connectivity & Isomorphism