Toán rời rạc 5

Đồ thị Nguyễn Thế Vinh-ĐHKH

64

CHƯƠNG IV

ĐỒ THỊ

Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu nhưng lại

có nhiều ứng dụng hiện đại nhất là ứng dụng trong tin học ngày nay. Những ý

tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là

Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán nổi tiếng về các cầu

ở Konigsberg hay còn gọi là bài toán 7 chiếc cầu.

Đồ thị cũng được dùng để giải các bài toán trong nhiều lĩnh vực khác

nhau. Ví dụ, dùng đồ thị để biểu diễn mối quan hệ quen biết, dùng đồ thị biểu

diễn một mang lưới giao. Chúng ta cũng có thể phân biệt hai hợp chất hóa học

có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta

cũng có thể xác định xem hai máy tính có được nối với nhau bằng một đường

truyền thông hay không nếu dùng mô hình đồ thị mạng máy tính. Đồ thị với

các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán

như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao

thông, hoặc là xây dựng hệ thông giao thông đảm bảo tính liên thông với chi

phí nhỏ nhất dựa trên thuật toán cây khung. Chúng ta cũng có thể dùng đồ thị

để lập lịch thi và phân chia kênh tối thiểu cho các đài truyền hình sao cho

không xảy ra hiện tượng "tranh chấp" kênh.

4.1. CÁC LOẠI ĐỒ THỊ

Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh hoặc cung (vô

hướng hoặc có hướng) nối các đỉnh đó. Người ta phân loại đồ thị tùy theo đặc

tính và số các cạnh nối các cặp đỉnh của đồ thị. Nhiều bài toán thuộc những

lĩnh vực rất khác nhau có thể giải được bằng mô hình đồ thị. Chẳng hạn người

ta có thể dùng đồ thị để biểu diễn sự cạnh tranh các loài trong một môi trường

sinh thái (đồ thị canh tranh), dùng đồ thị để biểu diễn ai có ảnh hưởng lên ai

trong một tổ chức nào đó (đồ thị ảnh hưởng) và cũng có thể dùng đồ thị để

biểu diễn các kết cục của cuộc thi đấu thể thao (đồ thị đấu vòng tròn). Chúng

ta cũng có thể dùng đồ thị để giải các bài toán như bài toán tính số các tổ hợp

khác nhau của các chuyến bay giữa hai thành phố trong một mạng hàng

Đồ thị Nguyễn Thế Vinh-ĐHKH

65

không, hay để giải bài toán đi tham quan tất cả các đường phố của một thành

phố sao cho mỗi đường phố đi qua đúng một lần, hoặc bài toán tìm số các màu

cần thiết để tô các vùng khác nhau của một bản đồ.

Trong đời sống, chúng ta thường gặp những sơ đồ, như sơ đồ tổ chức bộ

máy chính quyền, sơ đồ giao thông, sơ đồ hướng dẫn thứ tự đọc các chương

trong một cuốn sách v.v..., gồm những điểm biểu thị các đối tượng được xem

xét (người, tổ chức, địa danh, chương mục sách, ...) và nối một số điểm với

nhau tượng trưng cho một quan hệ nào đó giữa các đối tượng. Đó là những ví

dụ mô phỏng về đồ thị.

4.1.1. Định nghĩa 1: Một đơn đồ thị vô hướng G = (V, E) bao gồm một

tập khác rỗng V mà các phần tử của nó gọi là các đỉnh, và E là tập các cặp

không sắp thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.

4.1.2. Định nghĩa 2: Một đa đồ thị G = (V, E) bao gồm một tập khác

rỗng V mà các phần tử của nó gọi là các đỉnh, và E là họ các cặp không sắp

thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2

được gọi là cạnh song song hay cạnh bội nếu chúng cùng tương ứng với một

cặp đỉnh.

Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào

cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối

một cặp đỉnh nào đó.

4.1.3. Định nghĩa 3: Một giả đồ thị G = (V, E) bao gồm một tập khác

rỗng V mà các phần tử của nó gọi là các đỉnh, và E là họ các cặp không sắp

thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là các

cạnh.

Với v∈V, nếu (v,v)∈E thì ta nói có một khuyên tại đỉnh v.

Tóm lại, giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể

chứa các khuyên và các cạnh bội. Đa đồ thị là loại đồ thị vô hướng có thể chứa

cạnh bội nhưng không thể có các khuyên, còn đơn đồ thị là loại đồ thị vô

hướng không chứa cạnh bội hoặc các khuyên.

4.1.4. Định nghĩa 4: Một đồ thị có hướng G = (V, E) gồm một tập khác

rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của

Đồ thị Nguyễn Thế Vinh-ĐHKH

66

nó gọi là các cung, đó là các cặp có thứ tự (u,v) của các phần tử thuộc V. Đỉnh

u được gọi là đỉnh đầu và đỉnh v được gọi là đỉnh cuối

4.1.5. Định nghĩa 5: Một đa đồ thị có hướng G = (V, E) gồm một tập

khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần

tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V.

Đồ thị vô hướng nhận được từ đồ thị có hướng G bằng cách xoá bỏ các

chiều mũi tên trên các cung được gọi là đồ thị vô hướng nền của G.

4.2. CÁC MÔ HÌNH ĐỒ THỊ

4.2.1. Đồ thị lấn tổ trong sinh thái học. Đồ thị được dùng trong nhiều

mô hình có tính đến sự tương tác của các loài vật. Chẳng hạn sự cạnh tranh

của các loài trong một hệ sinh thái có thể mô hình hóa bằng đồ thị “lấn tổ”.

Mỗi loài được biểu diễn bằng một đỉnh. Một cạnh vô hướng nối hai đỉnh nếu

hai loài được biểu diễn bằng các đỉnh này là cạnh tranh với nhau.

Ví dụ cùng chung nguồn thức ăn cạnh tranh với nhau như Sóc và Gấu

trúc còn Quạ và Chuột chù thì không.

4.2.2. Đồ thị quen biết. Chúng ta dùng đồ thị để biểu diễn mối quan hệ

quen biết. Mỗi người hoặc nhóm người coi là một đỉnh. Một cạnh vô hướng

dùng để nối hai người hay hai nhóm người quen biết nhau.

4.2.3. Đồ thị ảnh hưởng. Khi nghiên cứu tính cách của một nhóm

nguời, ta thấy một số người có thể có ảnh hưởng đến suy nghĩ của những

người khác. Nếu người A có ảnh hưởng đến người B thì đỉnh a(biểu diễn

người A) và đỉnh b(biểu diễn người B) được nối bằng một cạnh có hướng.

4.2.4. Đồ thị Hollywood. Là một đồ thị vô hướng biểu diễn các diễn

viên bởi các đỉnh và có một cạnh nối hai đỉnh nếu hai diễn viên cùng đóng

trong cùng một bộ phim

4.2.5. Đồ thị đấu vòng tròn. Một cuộc thi đấu thể thao trong đó mỗi

đội hoặc mỗi cá nhân phải thi đấu vòng tròn một lượt. Cuộc thi đấu như thế có

thể được mô hình bằng một đồ thị có hướng trong đó mỗi đội hoặc mỗi cá

nhân là một đỉnh. Một cung đi từ đỉnh a đến đỉnh b nếu A thắng B.

Đồ thị Nguyễn Thế Vinh-ĐHKH

67

4.2.6. Đồ thị WEB. Mạng máy tính được mô hình như một đồ thị có

hướng trong đó mỗi trang WEB bằng một đỉnh và một cung xuất phát từ a đến

b nếu có một liên kết từ trang WEB A chỉ đến trang WEB B và kết thúc tại B.

4.2.7. Đồ thị cộng tác. Mô hình hóa của quan hệ đồng tác giả của các

bài báo, các đề tài v.v…Các đỉnh biểu diễn các tác giả còn một cạnh nối hai

đỉnh nếu hai người viết chung cùng một bài báo hay cùng một đề tài.

4.2.6. Đồ thị cuộc gọi điện thoại. Mô hình hóa các cuộc gọi điện thoại

trong một mạng. Là một đồ thị có hướng mỗi số máy biểu diễn một đỉnh của

đồ thị và một cung nối từ máy gọi đến máy nhận.

4.2.6. Đồ thị ưu tiên và xử lí cạnh tranh.

Các chương trình máy tính có thể thi hành nhanh hơn bằng cách thi

hành đồng thời một số câu lệnh nào đó. Điều quan trọng là không được thực

hiện một câu lệnh đòi hỏi kết quả của câu lệnh khác chưa được thực hiện. Sự

phụ thuộc của các câu lệnh vào các câu lệnh trước có thể biểu diễn bằng một

đồ thị có hướng. Mỗi câu lệnh được biểu diễn bằng một đỉnh và có một cung

từ một đỉnh tới một đỉnh khác nếu câu lệnh được biểu diễn bằng đỉnh thứ hai

không thể thực hiện được trước khi câu lệnh được biểu diễn bằng đỉnh thứ

nhất được thực hiện. Đồ thị này được gọi là đồ thị ưu tiên

4.3. CÁC KHÁI NIỆM CƠ BẢN

4.3.1. Bậc của đỉnh

Định nghĩa 1: Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được

gọi là liền kề nếu (u,v)∈E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các

đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v

gọi là các điểm đầu mút của cạnh e.

Định nghĩa 2: Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là

số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho

bậc của nó.

Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0.