Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều Bài 1: Đồ thị, phân loại đồ thị

CHÀO ĐÓN CẢ LỚP

ĐẾN BUỔI HỌC NÀY!

Để mô tả các cặp tỉnh có địa giới giáp ranh nhau, ta có thể nêu bằng lời, ví dụ, quan sát lược đồ bốn tỉnh Bạc Liêu, Cà Mau, Sóc Trăng và Kiên Giang trong Hình 1, ta nói “Các cặp tỉnh: (Bạc Liêu, Cà Mau), (Bạc Liêu, Sóc Trăng), (Bạc Liêu, Kiên Giang), (Kiên Giang, Cà Mau) giáp ranh nhau; còn (Kiên Giang, Sóc Trăng) và (Sóc Trăng, Cà Mau) không giáp ranh nhau”. Em có cách mô tả nào khác về mối quan hệ giáp ranh giữa các tỉnh đó không?

Hình 1. Lược đồ phần đất liền một số tỉnh miền Tây Nam Bộ

KHỞI ĐỘNG

Hình 1. Lược đồ phần đất liền một số tỉnh miền Tây Nam Bộ

KHỞI ĐỘNG

Việc mô tả mối quan hệ giáp ranh giữa các tỉnh có thể biểu diễn bằng đồ thị như sau:

CHUYÊN ĐỀ 3: TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 1: ĐỒ THỊ,

PHÂN LOẠI ĐỒ THỊ

NỘI DUNG BÀI HỌC

Khái niệm đồ thị

Phân loại đồ thị

Một số thuật ngữ và tính chất trên đồ thị

Phần 1.

Khái niệm đồ thị

1. Khái niệm đồ thị

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Đồ thị

là gì?

1. Khái niệm đồ thị

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Khái niệm: Đồ thị G là một cấu trúc gồm hai tập:

• Tập đỉnh V (mỗi đỉnh tương ứng với một đối tượng).

• Tập cạnh E (mỗi cạnh cho biết mối quan hệ giữa hai đối tượng).

1. Khái niệm đồ thị

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Việc mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng trong phần khởi động có thể biểu diễn bằng bốn đỉnh (tương ứng với bốn vòng tròn nét liền) và bốn cạnh (tương ứng với bốn đường nối giữa hai vòng tròn cho biết cặp tỉnh giáp ranh) như trong Hình 2.

Em hãy vẽ Hình 2 vào vở và vẽ thêm hai vòng tròn mô tả hai tỉnh Cần Thơ, Hậu Giang cùng với các cạnh để mô tả mối quan hệ giáp ranh của sáu tỉnh.

1. Khái niệm đồ thị

1. Khái niệm đồ thị

Theo em, đồ thị được ứng dụng trong thực tế như thế nào?

1. Khái niệm đồ thị

ỨNG DỤNG

Đồ thị được dùng để biểu diễn, giải nhiều bài toán trong nhiều lĩnh vực, như mô tả các hệ thống:

Mạng điện.

Mạng lưới giao thông.

Mạng máy tính.

Mối quan hệ dinh dưỡng giữa các loài.

Phần 2.

Phân loại đồ thị

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

Để phân loại đồ thị, người ta dựa vào các tính chất của cạnh.

Một cạnh của đồ thị có thể có các tính chất:

Có hướng hay vô hướng.

Có trọng số hay không có trọng số.

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

Thế nào là đơn đồ thị vô hướng?

Thế nào là đơn đồ thị có hướng?

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

a) Đơn đồ thị vô hướng

Khái niệm: Là đồ thị G = (V, E) gồm một tập không rỗng V mà các phần tử là các đỉnh và một tập E mà các phần tử là các cạnh, mỗi cạnh tương ứng với một cặp đỉnh phân biệt không có thứ tự. Một cạnh nối giữa hai đỉnh phân biệt u, v kí hiệu là {u, v} hoặc {v, u}.

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

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

a) Đơn đồ thị vô hướng

Ví dụ: Đồ thị trong Hình 2 là đơn đồ thị vô hướng. Nói tỉnh Cà Mau giáp ranh với tỉnh Kiên Giang là đồng nghĩa với nói tỉnh Kiên Giang cũng giáp ranh với tỉnh Cà Mau và cặp đỉnh này không phân biệt thứ tự.

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

b) Đơn đồ thị có hướng

Khái niệm: Là đồ thị G = (V, E) gồm một tập đỉnh không rỗng V và một tập cạnh E, mỗi cạnh tương ứng với một cặp đỉnh phân biệt có thứ tự. Một cạnh nối từ đỉnh u tới đỉnh v kí hiệu là (u, v).

Hình 3. Mô tả mối quan hệ dinh dưỡng giữa các loài

b) Đơn đồ thị có hướng

Ví dụ: Hình 3 mô tả mối quan hệ dinh dưỡng giữa sáu loài, mối quan hệ giữa các đỉnh là có thứ tự: Chuột là thức ăn của Rắn nhưng Rắn không phải là thức ăn của Chuột mà Rắn là thức ăn của Diều hâu.

Hình 3. Mô tả mối quan hệ dinh dưỡng giữa các loài

Phần 3. Một số thuật ngữ

và tính chất trên đồ thị

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

• Trong đơn đồ thị vô hướng G = (V, E) có cạnh {u, v}. Khi đó:
• Cạnh {u, v} được gọi là cạnh liên thuộc với hai đỉnh u, v.
• Đỉnh u kề với đỉnh v, đỉnh v kề với đỉnh u.
• u, v là hai đầu mút.
• Bậc của đỉnh u trong đơn đồ thị vô hướng là số cạnh liên thuộc với đỉnh u.

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

• Em hãy liệt kê các cạnh liên thuộc với các đỉnh của đồ thị trong Hình 2, từ đó xác định bậc của các đỉnh.

• Em hãy tính tổng số bậc của tất cả các đỉnh và tổng số cạnh của đồ thị, sau đó rút ra nhận xét về hai đại lượng này.

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Các cạnh liên thuộc với đỉnh tương ứng với tỉnh Kiên Giang là {Kiên Giang, Cà Mau}, {Kiên Giang, Bạc Liêu}.

→ Đỉnh có bậc bằng 2.

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Các cạnh liên thuộc với đỉnh tương ứng với tỉnh Cà Mau là {Cà Mau, Kiên Giang}, {Cà Mau, Bạc Liêu}.

→ Đỉnh có bậc bằng 2.

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Các cạnh liên thuộc với đỉnh tương ứng với tỉnh Bạc Liêu là {Bạc Liêu, Cà Mau}, {Bạc Liêu, Kiên Giang}, {Bạc Liêu, Sóc Trăng}.

→ Đỉnh có bậc bằng 3.

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Cạnh liên thuộc với đỉnh tương ứng với tỉnh Sóc Trăng là { Sóc Trăng, Bạc Liêu}.

→ Đỉnh có bậc bằng 1.

3. Một số thuật ngữ và tính chất trên đồ thị

a) Bậc của đỉnh trong đơn đồ thị vô hướng

Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng

Đồ thị có:

• Tổng số bậc của tất cả các đỉnh là 8.

• Tổng số cạnh là 4.

Ta có: 8 = 4 × 2.

⇒ Trong đơn đồ thị vô hướng thì tổng số bậc của tất cả các đỉnh bằng hai lần số cạnh.

b) Bậc của đỉnh trong đơn đồ thị có hướng

• Trong đơn đồ thị có hướng G = (V, E) có cạnh (u, v). Khi đó:
• Đỉnh u được gọi là nối tới đỉnh v, đỉnh v được nối từ đỉnh u.
• Đỉnh v kề với đỉnh u.
• u được gọi là đỉnh đầu, v được gọi là đỉnh cuối.
• Bậc ra của đỉnh u trong đơn đồ thị có hướng là số cạnh có đỉnh đầu là u.
• Bậc vào của đỉnh v trong đơn đồ thị có hướng là số cạnh có đỉnh cuối là v.

• Em hãy xác định bậc ra và bậc vào của các đỉnh trong đồ thị.

• Em hãy tính tổng số bậc ra của tất cả các đỉnh và tổng số bậc vào của tất cả các đỉnh, sau đó rút ra nhận xét về hai đại lượng này.

b) Bậc của đỉnh trong đơn đồ thị có hướng

Hình 3. Mô tả mối quan hệ dinh dưỡng giữa các loài

--------------------------------------

--------------------- Còn tiếp ----------------------