Giải thuật và lập trình: §1. Các khái niệm cơ bản

1.1. Định nghĩa đồ thị (GRAPH)

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ị:

Sơ đồ giao thông

Mạng máy tính

Cấu trúc phân tử

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

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.

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ị).

G được gọi là đồ thị vô hướng (undirected graph) 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).

G được gọi là đồ thị có hướng (directed graph) 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).

Ví dụ:

1.2. Các khái niệm

Như trên định nghĩa đồ thị G = (V, E) là một cấu trúc rời rạc, tức là các tập V và E hoặc là tập hữu hạn, hoặc là tập đếm được, có nghĩa là ta có thể đánh số thứ tự 1, 2, 3... cho các phần tử của tập V và E. Hơn nữa, đứng trên phương diện người lập trình cho máy tính thì ta chỉ quan tâm đến các đồ thị hữu hạn (V và E là tập hữu hạn) mà thôi, chính vì vậy từ đây về sau, nếu không chú thích gì thêm thì khi nói tới đồ thị, ta hiểu rằng đó là đồ thị hữu hạn.

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

Đố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.

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 lý: Giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi đó tổng tất cả các bậc đỉnh trong V sẽ bằng 2m:

Chứng minh: Khi lấy tổng tất cả các bậc đỉnh tức là mỗi cạnh e = (u, v) bất kỳ sẽ được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra kết quả.

Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ là số chẵn.

Đối với đồ thị có hướng G = (V, E). 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.

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 đó.

Định lý: Giả sử G = (V, E) là đồ thị có hướng với m cung, khi đó tổng tất cả các bán bậc ra của các đỉnh bằng tổng tất cả các bán bậc vào và bằng m:

Chứng minh: Khi lấy tổng tất cả các bán bậc ra hay bán bậc vào, mỗi cung (u, v) bất kỳ sẽ được tính đúng 1 lần trong deg+(u) và cũng được tính đúng 1 lần trong deg-(v). Từ đó suy ra kết quả.

Một số tính chất của đồ thị có hướng không phụ thuộc vào hướng của các cung. Do đó để tiện trình bày, trong một số trường hợp ta có thể không quan tâm đến hướng của các cung và coi các cung đó là các cạnh của đồ thị vô hướng. Và đồ thị vô hướng đó được gọi là đồ thị vô hướng nền của đồ thị có hướng ban đầu.