TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

MÔN HỌC: TOÁN ỨNG DỤNG

Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM Bài 5: CÂY VÀ CÁC ỨNG DỤNG

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

Bài 3: LÝ THUYẾT ĐỒ THỊ

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

1.1 Giới thiệu 1.2 Định nghĩa đồ thị 1.3 Phân loại đồ thị 1.4 Các thuật ngữ 1.5 Định lý về bậc của đỉnh 1.6 Đường đi, chu trình, đồ thị liên thông

2. ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

2.1 Đồ thị Euler 2.2 Đồ thị Hamilton

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.1 Giới thiệu

- Bài toán về các cây cầu ở Konigsberg:

Có cách nào để đi dạo qua tất cả bảy cây cầu, mà mỗi cây cầu chỉ đi qua một lần ?

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.1 Giới thiệu

- Năm 1736, là năm khai sinh lý thuyết đồ thị, qua việc công bố lời giải bài toán về các cây cầu ở Konigsberg của nhà toán học Euler.

C

A

D

Nhà toán học Thụy Sĩ

B

Leonhard Euler (April 1707 – September 1783)

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.2 Định nghĩa đồ thị

Định nghĩa: Đồ thị G được xác

định bởi (V, E) gồm: - V là tập hợp hữu hạn khác rỗng các phần tử gọi là đỉnh (hay nút) của đồ thị; - E là tập hợp các cặp đỉnh. Mỗi phần tử của E được gọi là một cạnh.

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.2 Định nghĩa đồ thị

Định nghĩa: Cho hai đồ thị G = (V,E) và G’ = (V’,E’)  G’ được gọi là đồ thị con của G, ký hiệu G’ G nếu V’ V

và E’  E

 Nếu V’= V và E’  E thì G’ được gọi là đồ thị con khung

của G.

G

H

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.3 Phân loại đồ thị

Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E:

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.3 Phân loại đồ thị

Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E:

- G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v thuộc V chỉ có nhiều nhất là 1 cạnh;

Detroit

New York

San Francisco

Chicago

Denver

Washington

Los Angeles

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.3 Phân loại đồ thị

Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E:

- G được gọi là đa đồ thị nếu giữa hai đỉnh u, v thuộc V có nhiều hơn 1 cạnh

Detroit

New York

San Francisco

Chicago

Denver

Washington

Los Angeles

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.3 Phân loại đồ thị

Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E:

- Đa đồ thị G được gọi là giả đồ thị nếu có khuyên. Khuyên là cạnh có hai đầu mút trùng nhau, dạng (u,u)

Detroit

New York

San Francisco

Chicago

Denver

Washington

Los Angeles

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.3 Phân loại đồ thị

Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E:

- G là đồ thị vô hướng nếu các cạnh trong E là không định hướng. Tập E gồm các cặp (u,v) không sắp thứ tự (u,v)≡ (v,u) - G là đồ thị có hướng nếu các cạnh trong E là có định hướng. Trong đồ thị có hướng, hai điểm u và v, có thể được nối bởi hai cung (u,v) và (v,u).

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.3 Phân loại đồ thị

Có cạnh bội Có khuyên

Cạnh

Vô hướng

Không

Không

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

Vô hướng

Có

Không

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

Vô hướng

Có

Có

Giả đồ thị vô hướng

Có hướng

Không

Có

Đồ thị có hướng

Có hướng

Có

Có

Đa đồ thị có hướng

Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: Loại đồ thị

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.4 Các thuật ngữ

- Cạnh uv nối u với v, cạnh uv được gọi là cạnh liên

thuộc với u,v; đỉnh u được gọi là kề với đỉnh v.

- Hai cạnh nối cùng một cặp đỉnh gọi là cạnh song song. là cạnh liên - Cạnh uv nối u với v, cạnh uv được gọi

thuộc với u,v; đỉnh u được gọi là kề với đỉnh v.

Detroit

New York

San Francisco

Chicago

Denver

Washington

Los Angeles

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.4 Các thuật ngữ

- Cho đồ thị vô hướng G = (V,E). Bậc của đỉnh v, ký hiệu deg(v), là số cạnh liên thuộc với v. Trong đó một khuyên tại một đỉnh được đếm hai lần cho bậc của đỉnh ấy.

b a

f c

d e - Đỉnh có bậc bằng 0 gọi là đỉnh cô lập - Đỉnh có bậc bằng 1 gọi là đỉnh treo Ví dụ: deg(a)=2; deg(b)=4; deg(f)= 3 deg(d)=0; deg(c)=1 Đỉnh d là đỉnh cô lập Đỉnh c là đỉnh treo

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.4 Các thuật ngữ

Bậc đỉnh a: deg(a) ?

Bậc đỉnh b: deg(b) ?

Bậc đỉnh c: deg(c) ?

b a

Bậc đỉnh d: deg(d) ?

Bậc đỉnh e: deg(e) ?

f d c

Bậc đỉnh f: deg(f) ?

e

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.4 Các thuật ngữ

Cho đồ thị có hướng G* = (V,E). - bậc ra của đỉnh v, ký hiệu deg+(v), là số cung đi ra khỏi đỉnh, - bậc vào của đỉnh v, ký hiệu deg-(v), là số cung đi vào đỉnh.

f

e

a

d

b

c

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.5 Định lý về bậc của đỉnh

Định lý: Với G là đồ thị vô hướng, với m cạnh, khi đó tổng số bậc của đỉnh là 2m.

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

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.5 Định lý về bậc của đỉnh

Định lý: Với G* là đồ thị có hướng, với m cung, khi đó chúng ta có công thức:

e

f

a

d

Thực hành: Tính toán bậc các đỉnh của đồ thị có hướng được cho trong hình bên

b

c

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.5 Định lý về bậc của đỉnh

Bài tập 1:

Vẽ đơn đồ thị vô hướng gồm 6 đỉnh với bậc là: 2,2,3,3,3,5

Bài tập 2:

Vẽ đơn đồ thị vô hướng gồm 6 đỉnh với bậc là: 2,2,3,3,3,3

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.6 Đường đi, chu trình, đồ thị liên thông

Định nghĩa:

Cho G = (V,E) là đồ thị vô hướng u,vV a) Đường đi (dây chuyền) độ dài k nối hai đỉnh u,v là dãy đỉnh và cạnh liên tiếp nhau v0e1v1e2…vk-1ekvk sao cho: v0=u ,vk= v, ei=vi-1vi , i=1,2,…,k

b) Đường đi không có cạnh nào xuất hiện quá một lần gọi là

đường đi đơn

c) Đường đi không có đỉnh nào xuất hiện quá một lần gọi là

đường đi sơ cấp

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.6 Đường đi, chu trình, đồ thị liên thông

Định nghĩa:

là chu trình nếu bắt đầu và kết

Đường đi được gọi thúc tại cùng một đỉnh Đường đi đơn có đỉnh bắt đầu và đỉnh kết thúc trùng nhau tạo ra chu trình đơn.

Bài toán: Hãy xác định theo đồ thị: 1- đường đi đơn 2- đường đi sơ cấp 3- chu trình và chu trình đơn

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.6 Đường đi, chu trình, đồ thị liên thông

Định nghĩa:

Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu

luôn tìm được đường đi giữa hai đỉnh bất kỳ của đồ thị. Với đồ thị G không liên thông, G được phân rã thành một số đồ thị con liên thông. Mỗi đồ thị con này được gọi là thành phần liên thông.

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.6 Đường đi, chu trình, đồ thị liên thông

Định nghĩa:

Đồ thị có hướng G* = (V,E) tính liên thông được xác định theo hướng của cung.

Đồ thị G* là liên thông mạnh nếu luôn tìm được

đường đi giữa hai đỉnh bất kỳ của đồ thị.

Đồ thị G* là liên thông yếu nếu chỉ tồn tại đồ thị vô

hướng nền của nó là liên thông.

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Khái niệm cơ bản

1.6 Đường đi, chu trình, đồ thị liên thông

Định nghĩa:

Cho G = (V,E) là đồ thị vô hướng liên thông là đỉnh khớp nếu G\v không liên a) Đỉnh v được gọi thông (G\v là đồ thị con của G có được bằng cách xoá v và các cạnh kề với v) b) Cạnh e được gọi là cầu nếu G\e không liên thông( G\e là đồ thị con của G có được bằng cách xoá cạnh e).

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.1 Đồ thị Euler

Định nghĩa

Chu trình đơn trong G = (V,E) đi qua mỗi cạnh của đồ

thị một lần gọi là chu trình Euler.

Đường đi đơn trong G đi qua mỗi cạnh của đồ thị một

lần được gọi là đường đi Euler.

Đồ thị được gọi là đồ thị Euler nếu có chu trình

Euler

là đồ thị nửa Euler nếu có có

Đồ thị được gọi đường đi Euler

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.1 Đồ thị Euler

Bài tập

G1 G3 G2

H1 H2 H3

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.1 Đồ thị Euler

Định lý

Đồ thị vô hướng liên thông G = (V,E) là đồ thị Euler khi

và chỉ khi mọi đỉnh của G đều có bậc chẵn.

Hệ quả

Đồ thị vô hướng liên thông G = (V,E) là đồ thị nửa Euler

khi và chỉ khi G có không quá 2 đỉnh bậc lẻ.

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.1 Đồ thị Euler

Thuật toán tìm chu trình Euler

Bắt đầu từ một đỉnh bất kỳ của G và tuân theo qui tắc sau:

1- Xóa bỏ cạnh đã đi qua và đồng thời xóa đỉnh cô lập tạo thành.

2- Ở mỗi bước ta chỉ qua cầu khi không còn cách lựa chọn nào khác.

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.1 Đồ thị Euler

Thuật toán tìm chu trình Euler

Ví dụ: Tìm chu trình Euler cho đồ thị G dưới đây

c

b

d

a

e

g

f

h

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.2 Đồ thị Hamilton

Định nghĩa

Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ

thị, mỗi đỉnh đúng một lần.

Chu trình bắt đầu từ 1 đỉnh v nào đó qua tất cả các đỉnh

còn lại đúng một lần, rồi quay trở về lại đỉnh v.

Đồ thị gọi là đồ thị Hamilton nếu có chu trình Hamilton Đồ thị gọi là đồ thị nửa Hamilton nếu có đường đi Hamilton

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.2 Đồ thị Hamilton

Định nghĩa

Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ

thị, mỗi đỉnh đúng một lần.

Ví dụ Đồ thị hình bên có phải là đồ thị Hamilton?

LÝ THUYẾT ĐỒ THỊ

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Đồ thị Euler và đồ thị Hamilton

2.2 Đồ thị Hamilton

Bài tập

Tìm đồ thị Hamilton, đồ thị nửa Hamilton

LÝ THUYẾT ĐỒ THỊ