Các Khái Niệm Cơ Bản Trong Đồ Thị

1. Đồ Thị là gì?

Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức:

G = (V, E)

V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V.

Một số hình ảnh của đồ thị:

Một mạng máy tính	Một sơ đồ giao thông

2. Phân loại đồ thị

Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E:
Cho đồ thị G = (V, E). Định nghĩa một cách hình thức

 Đơn đồ thị

G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v.

Đa đồ thị

G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v (Hiển nhiên đơn đồ thị cũng là đa đồ thị).

Đồ thị vô hướng

G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự. (u, v)≡(v, u).

Đồ thị có hướng

G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u).

Đồ thị vô hướng	Đồ thị có hướng

Đơn đồ thị

Đồ thị vô hướng	Đồ thị có hướng

Đa đồ thị

3. Các khái niệm

Cạnh liên thuộc, đỉnh kề

Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e ∈  E, nếu e = (u, v) thì ta nói hai đỉnh u và v

là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v

Bậc

Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên thuộc với v cũng là số đỉnh kề với v.

Đỉnh đầu, đỉnh cuối

Xét một cung e ∈  E, nếu e = (u, v) thì ta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e.

Bán bậc ra, bán bậc vào

Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: 

• Bán bậc ra của v ký hiệu deg+(v) là số cung đi ra khỏi nó;
• bán bậc vào ký hiệu deg-(v) là số cung đi vào đỉnh đó.