01 - Các khái niệm cơ bản

Đồ thị

Đồ thị là một mô hình biểu diễn một tập hợp các đối tượng cùng với quan hệ giữa chúng. 

Ký hiệu toán học: G = (V, E)

Trong đó: V là tập các đỉnh, còn E là tập các cạnh.

Mỗi cạnh thể hiện một mối liện hệ giữa hai đỉnh của đồ thị nên người ta thường viết e = (u, v) với e ∈ E; u, v ∈ V.

Nguồn tài liệu chính cho bài viết: Sách giáo khoa chuyên Tin quyển 1, Hồ Sỹ Đàm

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

Nguồn: Tài liệu giáo khoa chuyên Tin Quyển 1, Hồ Sỹ Đàm

Dựa trên đặc tính và số lượng các cạnh trong tập cạnh E, ta phân loại đồ thị thành các loại sau:

Đơn đồ thị: mỗi cặp đỉnh u, v chỉ có một cạnh nối giữa chúng

Đa đồ thị: tồn tại một số cặp đỉnh u, v mà có nhiều hơn một cạnh nối giữa chúng. Ta gọi những cạnh này là những cạnh song song.

Đồ thị vô hướng: các cạnh trong E không có hướng, nghĩa là cạnh (u, v) cũng là cạnh (v, u)

Đồ thị có hướng: các cạnh trong E có hướng, nghĩa là cạnh (u, v) khác cạnh (v, u)

Một số khái niệm

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

Xét đồ thị G = (V, E), với cạnh e ∈ E, nếu e = (u, v) với u, v ∈  U thì ta nói u kề với v, e là cạnh liên thuộc của u và v.

Số cạnh liên thuộc với u gọi là bậc của u, ký hiệu là deg(u).

Định lý 5-1, SGK chuyên Tin, Hồ Sỹ Đàm, trang 129

Đối với đồ thị có hướng, nếu e = (u, v) thì e là cạnh (cung) đi ra từ u và đi vào v. Ta có thể gọi u là đỉnh đầu, v là đỉnh cuối.

Lúc này, bậc của một đỉnh v sẽ được phân biệt thành hai loại là bán bậc ra ký hiệu deg+(v) và bán bậc vào deg-(v) tương ứng với số cung đi ra khỏi v và đi vào v.

                    Định lý 5-2, SGK chuyên Tin, Hồ Sỹ Đàm, trang 129

Nhiệm vụ 1. Cho đồ thị G sau đây:

(Lưu ý: Các số màu đỏ không phải tên cạnh mà là trọng số cạnh, chúng ta sẽ nói ở phần sau. Cạnh trong trường hợp này được viết theo định nghĩa: (1, 4) là cạnh từ 1 đến 4.)

Trắc nghiệm 1 - Các khái niệm cơ bản

Đường đi, chu trình

Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G=(V,E) là dãy(theo đỉnh): x0, x1, …, xn-1, xn.

Trong đó: 

+ u = x0

+ v= x n

+ (xi, xi+1) ∈ E

Hay theo cạnh: (x0, x1), (x1, x2), …, (xn-1, xn).

Khi đó: u gọi là đỉnh đầu, v gọi là đỉnh cuối của đường

đi.

Chu trình

Là một đường đi có đỉnh đầu và đỉnh cuối trùng nhau.

Đường đi hay chu trình được gọi là đơn nếu nó không đi qua đỉnh náo quá một lần.

Đồ thị đẳng cấu

Đồ thị G = (V, E) và G' = (V', E') được gọi là đẳng cấu nếu tồn tại một song ánh f: V -->V' sao cho số cung nối u với v trên E bằng số cung nối f(u) và f(v) trên E'.

ví dụ: các đồ thị sau đây là đẳng cấu

Đồ thị con

Đồ thị G' = (V', E') được gọi là đồ thị con của G = (V, E) nếu V' ⊂ V và E' ⊂ E

Ví dụ: M1, M2, M3, M4 là con của G

Phiên bản có hướng, vô hướng

Phiên bản có hướng của đồ thị vô hướng G = (V, E) là G' = (V, E') được tạo thành bằng cách thay mỗi cung e trong E thành hai cung ngược chiều nhau.

Phiên bản vô hướng của đồ thị có hướng G = (V, E) là G' = (V, E') được tạo thành bằng cách thay mỗi cung e trong E thành một cung vô hướng. Nói cách khác bỏ chiều của tất cả cạnh e trong E

Tính liên thông

• Đồ thị vô hướng gọi là liên thông nếu giữa hai cặp đỉnh bất kỳ luôn tồn tại đường đi.

• Đồ thị có hướng gọi là liên thông mạnh nếu giữa hai đỉnh bất kỳ của đồ thị tồn tại đường đi.

• Đồ thị có hướng gọi là liên thông yếu nếu như phiên bản vô hướng của nó là đồ thị liên thông.

Thành phần liên thông

Nếu một đồ thị không liên thông thì sẽ được phân rã thành các thành phần liên thông. Mỗi thành phần liên thông là một đồ thị con của đồ thì ban đầu.

Ví dụ: Đồ thị G sau đây có 2 thành phần liên thông, H có 3 thành phần liên thông

Đồ thị đầy đủ

Đồ thị vô hướng gọi là đầy đủ nếu mọi cặp đỉnh đều là kề nhau. Đồ thị đầy đủ gồm N đỉnh ký hiệu là Kn

Đồ thị hai phía

Một đồ thị vô hướng gọi là hai phía nếu như tập đỉnh V của nó có thể chia thành hai tập khác rỗng, rời nhau X, Y sao cho không tồn tại cạnh nối hai đỉnh thuộc X cũng như không tồn tại cạnh nào nối hai đỉnh thuộc Y.

Ví dụ sau đây là một đồ thị hai phía:

Nếu |X| = m, |Y| = n và giữa mọi cặp đỉnh (x, y) trong đó x ∈ X và y ∈ Y đều có cạnh nối thì ta gọi nó là đồ thị hai phía đầy đủ.

Định lý:

Đồ thị G = (V, E) là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ

Thuật toán kiểm tra đồ thị hai phía:

B1. Chọn v đỉnh bất kỳ. đặt X = {v}

B2. Y = {u|u kề v, ∀ v ∈ X}

B3. Nếu X ∩ Y ≠ Ø  --> G không là đồ thị hai phía

B4. Ngược lại: đặt X <--Y, quay lại bước 2

B5. Nếu tất cả các đỉnh được xét hết mà không xãy ra bước 3 thì G là đồ thị hai phía. Ngược lại G không phải đồ thị hai phía

Nhiệm vụ 2. Kiểm tra xem đồ thì sau đây có là đồ thị hai phía không

Khớp và cầu

Một đỉnh gọi là Khớp nếu bỏ nó và các cạnh liên thuộc với nó thì sẽ làm tăng số thành phần liên thông của đồ thị

Một cạnh gọi là cầu nếu bỏ nó đi sẽ làm tăng số thành phần liên thông của đồ thị.