Giáo Trình Toán Rời Rạc Ptit - 123doc

Làmộttrongnhữngngànhkhoahọcđược rađời từr ất sớm. ™Đượcdùngđểmôhìnhhóabằnghìnhhọc và giảiquy ết nhiềubàitoántrongthực tế. ™Cácbàitoánthườngđược mô tảthôngqua cácđỉnhvà cácđườngn ối giữa cácđỉnh, thểhiện m ối liên hệgiữa chúng

BÀI GIẢNG MÔN

TOÁN RỜI RẠC 2

Giảng viên: TH.S Phan ThỊ Hà

Điện thoại/E-mail: hathiphan@yahoo.com

Bộ môn: Công nghệ phần mềm

TOÁN RỜI RẠC 2NỘI DUNG

™ Các thuật ngữ về đồ thị

™ Biểu diễn đồ thị và sự đẳng cấu

™ Tính liên thông của đồ thị

™ Tính liên thông và bậc của đỉnh

TOÁN RỜI RẠC 2GIỚI THIỆU: Lý thuyết đồ thị

™ Là một trong những ngành khoa học được ra đời từ rấtsớm

™ Được dùng để mô hình hóa bằng hình học và giải quyếtnhiều bài toán trong thực tế

™ Các bài toán thường được mô tả thông qua các đỉnh vàcác đường nối giữa các đỉnh, thể hiện mối liên hệ giữachúng

TOÁN RỜI RẠC 2CHƯƠNG 1:Các thuật ngữ cơ bản về đồ thị

™ 1.1 Định nghĩa và khái niệm

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

™ Định nghĩa: đồ thị G là 1 cặp G = (V,E), trong đó:

ƒ V: tập hợp các đỉnh

ƒ E: tập hợp các cạnh, E ⊆ [V] 2

TOÁN RỜI RẠC 2Xét lại ví dụ 1

™ Ánh xạ kề của các đỉnh trong hình trên:

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Đồ thị vô hướng và có hướng

™ Cạnh (x, y) ∈ E là cạnh vô hướng khi cặp đỉnh (x, y)

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Đơn đồ thị và đa đồ thị

™ Đồ thị G = (V, E) trong đó mỗi cặp đỉnh chỉ được nối tối

đa bằng 1 cạnh được gọi là đơn đồ thị hay còn gọi tắt

là đồ thị.

™ Đồ thị trong đó có ít nhất 1 cặp đỉnh được nối với nhau

nhiều hơn một cạnh được gọi là đa đồ thị.

™ Một giả đồ thị G = (V, E) trong đó các cặp đỉnh đuwcjnối với nhau là 1 hoặc nhiều cạnh và mỗi đỉnh có thể

có khuyên

TOÁN RỜI RẠC 2Đơn ĐT có hướng(có thể có khuyên nhưng không có

cạnh bội cùng chiều)

TOÁN RỜI RẠC 2Bảng tổng hợp

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Đồ thị đầy đủ

™ Đồ thị vô hướng G = (V,E)

được gọi là đồ thị đầy đủ, nếu mỗi cặp đỉnh

đều có cạnh nối giữa chúng

™ Đồ thị có hướng G = (V,E) được gọi

là đồ thị đầy đủ, nếu mỗi cặp đỉnh đều

có cung nối giữa chúng (chiều của cung

có thể tùy ý)

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Bậc của đỉnh trong ĐT vô hướng

™ Giả sử G = (V, E) là một đồ thị, ta gọi bậc của một đỉnh

là số cạnh kề với đỉnh đó

ƒ Đỉnh cô lập là đỉnh không nối với bất kỳ đỉnh nào.

ƒ Đỉnh treo là đỉnh có bậc bằng 1

™ Ký hiệu: d(v) là bậc của đỉnh v trong đồ thị G

™ Chú ý: khuyên của đồ thị được tính là bậc 2

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Bậc của đỉnh trong ĐTcó hướng

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Bậc của đỉnh

™ ĐL1( Định lý bắt tay): Cho G = (V,E) là một đồ thị vô

hướng có e cạnh Khi đó 2e= ∑d(v)

ƒ (Định lý này đúng cả khi đồ thị có cạnh bội hoặc cáckhuyên)

™ Định lý 2 Trong một đồ thị vo hướng số các đỉnh bậc lẻ

là một số chẵn

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Đồ thị phân đôi

™ Một đồ thị đơn G được gọi là đồ thị phân đôi nếu tập

các đỉnh V có thể phân làm hai tập con không rỗng, rờinhau V1 và V2 sao cho mỗi cạnh của đồ thị nối mộtđỉnh của V1 với một đỉnh của V2

TOÁN RỜI RẠC 2

1.Định nghĩa và khái niệm

Sự đẳng hình

™ Hai đồ thị G1= (V1, E1) và G2= (V2, E2 ) được gọi là đẳng

hình với nhau nếu tồn tại một song ánh S trên các tập

TOÁN RỜI RẠC 21.Biểu diễn bằng ma trận liền kề

™ Cho G = (V, E) là một đồ thị có các đỉnh được đánh số:1,

2, , n

™ Ma trận vuông A cấp n được gọi là ma trận liền kề của

đồ thị G nếu:

1 nếu giữa I,j có cạnh kề

∀i, j ∈ V, A[i,j]= 0 _không có cạnh kề

™ Đồ thị G là đối xứng khi và chỉ khi ma trận kề A là đối

xứng

™ Một khuyên được tính là 1 cạnh

TOÁN RỜI RẠC 2

™ Cho G = (V, E)một gỉa đồ thị có các đỉnh được đánhsố:1, 2, , n

™

ƒ ∀i, j ∈ V, A[i,j]= 0 không có cạnh kề

™ Đồ thị G là đối xứng khi và chỉ khi ma trận kề A là đốixứng

™ Một khuyên được tính là 1 cạnh

TOÁN RỜI RẠC 2

TOÁN RỜI RẠC 2

0 1

0 0

1 1

0 1

0 1

1 1

1 0

u1

u4 u3

u2

TOÁN RỜI RẠC 2

™ Ma trận kề cũng có thể dùng để biểu diễn đồ thị

vô hướng có khuyên và có cạnh bội Khi có

cạnh bội ma trận liền kề không còn là ma trận không-một nữa, vì phần tử ở vị trí (i,j) của ma

trận này bằng số cạnh bội nối đỉnh ui và

đỉnh uj Khuyên tại đỉnh ui được coi là cạnh nối

đỉnh ui với chính nó và được tính là một cạnh Tất cả các đồ thị vô hướng, kể cả đa đồ thị và giả đồ thị đều có ma trận liền kề đối xứng.

1 2

2 1

1 0

1 1

0 3

2 0

3

3 4

TOÁN RỜI RẠC 2

2.Biểu diễn bằng danh sách kề

™ Với mỗi đỉnh của đồ thị ta xây dựng một danh sách mócnối chứa các đỉnh kề với đỉnh này: Danh sách này đượcgọi là danh sách kề

™ Một đồ thị được biểu diễn bằng một mảng các danh

sách kề

TOÁN RỜI RẠC 2

™ void Dske_To_MTke(void){

™ int dau, cuoi; char str[132], tu[12];

TOÁN RỜI RẠC 2

™ fgets(str, 132, fp);n = atoi(str);

™ printf("\n So din do thi:%d",n);Init();

™ for( dau=1; dau<=n; dau++){

TOÁN RỜI RẠC 2

™ fgets(str, 132, fp);n = atoi(str);

™ printf("\n So din do thi:%d",n);Init();

™ for( dau=1; dau<=n; dau++){

TOÁN RỜI RẠC 2

3.Ma trận liên thuộc

™ Các ma trận liên thuộc cũng có thể được dùng để biễudiễn các cạnh bội và khuyên G = (V,E) V = {v1, v2, , vn} E = {e1, e2, , em}

™ Ma trận liên thuộc của đồ thị G là M = [mij], trong đómij =1 nếu cạnh ej liên thuộc với đỉnh vi và = 0 nếucạnh ej không liên thuộc với đỉnh vi

TOÁN RỜI RẠC 24.Sự đẳng cấu của đồ thị

ĐN: Các đồ thị đơn G1 =(V1,E1) và G2 =(V2,E2) làđẳng cấu nếu có hàm song ánh f từ V1 lên V2 saocho các đỉnh a và b là liền kề trong G1 nếu và chỉnếu f(a) và f(b) là liền kề trong G2 với mọi a và b

trong V1 Hàm f như thế được gọi là một đẳng cấu

Hay: Hai đồ thị G = (V,E) và G’ = (V’,E’) gọi là đẳng cấu với nhau nếu :

TOÁN RỜI RẠC 24.Sự đẳng cấu của đồ thị

ƒ có một phép tương ứng 1 – 1(song ánh) giữa 2 tập V, V’

ƒ và có một phép tương ứng 1 – 1 giữa 2 tập hợp E, E’

Sao cho:

nếu cạnh e = (v,w) ∈ E tương ứng với cạnh

e’ = (v’,w’) ∈ E’ thì cặp đỉnh v, w ∈ V cũng là tương ứng của cặp đỉnh v’, w’ ∈ V

™ G, G’ đẳng cấu nếu tồn tại một song ánh ϕ: VÆV’ sao cho: (i, j) ∈ E (ϕ(i), ϕ(j)) ∈ E’

TOÁN RỜI RẠC 2Chương3 Tính liên thông của đồ thị

™ Đường đi

™ Tính liên thông trong đồ thị vô hướng

™ Tính liên thông trong đồ thị có hướng

™ Đếm đường đi giữa các đỉnh

™ Phương pháp duyệt đồ thị

∀i = 2, 3, , k-1, k : (xi-1, xi) ∈E

™ Đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk

TOÁN RỜI RẠC 2

2.Chu trình

™ Chu trình là một đường đi khép kín (đỉnh cuối trùng với

đỉnh đầu của đường đi)

[x1, x2,…, xk-1, x1]

™ Tuy nhiên để cho gọn, trong ký hiệu của chu trình,

thường không viết đỉnh cuối:

[x1, x2,…, xk-1]

™ Chu trình đơn: là chu trình mà các đỉnh trên nó khác

nhau từng đôi

TOÁN RỜI RẠC 2

3.Tính liên thông trong đồ thị vô hướng

™ Một đồ thị vô hướng được gọi là liên thông nếu có

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

TOÁN RỜI RẠC 23.Tính liên thông của đồ thị vô hướng

™ Định lý 1 Giữa mọi cặp đỉnh phân biệt của một đồ thị

vô hướng liên thông luôn luôn có đường đi đơn

TOÁN RỜI RẠC 2

3.Tính liên thông của đồ thị có hướng

™ ĐN Đồ thị có hướng được gọi là liên thông mạnh nếu

có đường đi từ a tới b và từ b tới a với mọi đỉnh a

và b bất kỳ của đồ thị

™ ĐN Đồ thị có hướng được gọi là liên thông yếu nếu có

đường đi giữa hai đỉnh bất kỳ của đồ thị vô hướng nền (Như vậy đồ thị liên thông mạnh thì cũng liên thông yếu)

™ một nhóm cây trong đó không có 2 cây nào được nối

với nhau được gọi là một rừng

™ Rừng bao trùm của một đồ thị là rừng và là đồ thị con

của đồ thị đó và chứa tất cả các nút của đồ thị; rừnggồm các cây T1, T2, ,Tm trong đó cây Ti chứa tất cảcác nút liên thông với nút gốc của nó trong đồ thị

™ Nếu rừng bao trùm chỉ gồm một cây thì cây đó được gọi là Cây bao trùm của đồ thị đó

TOÁN RỜI RẠC 2

4.Đếm đường đi giữa các đỉnh

™ Định lý 2 Cho G là một đồ thị với ma trận liền kề A

theo thứ tự các đỉnh v1,v2, ,vn (với các cạnh vô

hướng hoặc có hướng hay là cạnh bội, hoặc có thể cókhuyên) Số các đường đi khác nhau độ dài r từ vi đến vj trong đó r là một số nguyên dương, bằng giá trịcủa phần tử (i,j) của ma trận Ar.(cm-SGK)

TOÁN RỜI RẠC 2

™ Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta

sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ i đã được duyệt, phần tử tương ứng trong mảng chuaxet[] có giá trị FALSE Ngược lại,

nếu đỉnh chưa được duyệt, phần tử tương ứng trong

mảng có giá trị TRUE Thuật toán có thể được mô tả

bằng thủ tục đệ qui DFS () trong đó: chuaxet - là mảng các giá trị logic được thiết lập giá trị TRUE.

TOÁN RỜI RẠC 2

™ Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với v mỗi đỉnh đúng một lần Để đảm bảo

duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thànhphần liên thông), chúng ta chỉ cần thực hiện duyệt nhưsau:

™ {

™ for (i=1; i≤ n ; i++)

™ chuaxet[i] := TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/

™ for (i=1; i≤ n ; i++)

™ if (chuaxet[i] )

™ }

TOÁN RỜI RẠC 2VD:

duyệt đồ thị sau theo chiều sâu

TOÁN RỜI RẠC 2

TOÁN RỜI RẠC 2

™ void DFS(int G[][MAX], int n, int v, int chuaxet[]){

™ int u;

™ printf("%3d",v);chuaxet[v]=FALSE;

™ for(u=1; u<=n; u++){

™ if(G[v][u]==1 && chuaxet[u])

™ DFS(G,n, u, chuaxet);

™ }

TOÁN RỜI RẠC 2

™ Bước 1 (Khởi tạo):

™ Stack = ∅; Push(Stack, u); <Thăm đỉnh u>; Chuaxet[u] = False;

™ <Thăm đỉnh t>; Chuaxet[t] = False;

™ Push(Stack, s) ; Push(Stack, t) ; break ;

TOÁN RỜI RẠC 2

Hoặc thuật toán có thể được cài đặt theo stack như sau:

™ void Dtraverse(kmatran a, kvecto &chuaxet, int k, int n)

™ {stack S[20];int i,h;

TOÁN RỜI RẠC 2

Sử dụng để kiểm tra tính liên thông như sau

™ int LienThong(kmatran a,int n)

™ {Stack<int> S(20);int i,h;kvecto chuaxet;

TOÁN RỜI RẠC 2Duyệt đồ thị theo chiều rộng

™ Để ý rằng, với thuật toán tìm kiếm theo chiều sâu, đỉnhthăm càng muộn sẽ trở thành đỉnh sớm được duyệt

xong Đó là kết quả tất yếu vì các đỉnh thăm được nạpvào stack trong thủ tục đệ qui Khác với thuật toán tìmkiếm theo chiều sâu, thuật toán tìm kiếm theo chiều rộngthay thế việc sử dụng stack bằng hàng đợi queue Trongthủ tục này, đỉnh được nạp vào hàng đợi đầu tiên là v,

các đỉnh kề với v ( v1, v2, , vk) được nạp vào queue

kế tiếp Quá trình duyệt tiếp theo được bắt đầu từ cácđỉnh còn có mặt trong hàng đợi

™ Để ghi nhận trạng thái duyệt các đỉnh của đồ thị, ta cũng

vẫn sử dụng mảng chuaxet[] gồm n phần tử thiết lập giá trị ban đầu là TRUE Nếu đỉnh i của đồ thị đã được

duyệt, giá trị chuaxet[i] sẽ nhận giá trị FALSE Thuật

toán dừng khi hàng đợi rỗng Thủ tục BFS dưới đây thể

TOÁN RỜI RẠC 2

™ void BFS(int u){

™ queue = φ;

™ u <= queue; /*nạp u vào hàng đợi*/

™ chuaxet[u] = false;/* đổi trạng thái của u*/

™ while (queue ≠ φ ) { /* duyệt tới khi nào hàng đợi rỗng*/

™ queue<=p; /*lấy p ra từ khỏi hàng đợi*/

™ Thăm_Đỉnh(p); /* duyệt xong đỉnh p*/

™ for (v ∈ ke(p) ) { /* đưa các đỉnh v kề với p nhưng chưa được xét vào hàng đợi*/

™ chuaxet[v] = false;/* đổi trạng thái của v*/

™ } /* end while*/

TOÁN RỜI RẠC 2

™ Thủ tục BFS sẽ thăm tất cả các đỉnh cùng thành phần liên thông với u Để thăm tất cả các đỉnh của đồ thị,

chúng ta chỉ cần thực hiện đoạn chương trình dưới đây:

TOÁN RỜI RẠC 2

TOÁN RỜI RẠC 2

Số thành phần liên thông của đồ thị

™ Cạnh cầu- cạnh khớp-canh cat

™ Đỉnh khớp-đỉnh cắt-điểm khớp- dinh tru

™ Đếm số thành phần liên thông của đồ thị

TOÁN RỜI RẠC 2

™ 1.Khái niệm về đường đi và chu trình Euler

™ 2.Các điều kiện cần và đủ cho chu trình và đường đi

Euler

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

™ 4 Đường đi và chu trình Hamilton

CHƯƠNG 4 CHU TRÌNH EULER VÀ CHU TRÌNH HAMILTON

TOÁN RỜI RẠC 2

vd

™ Đồ thị G1 có chu trình Euler, thí dụ a,e,c,d,e,b,a Cảhai đồ thị G2 và G3 đều không có chu trình Euler Tuynhiên G3 có đường đi Euler, cụ thể là a,c,d,e,b,d,a,b

e

e

TOÁN RỜI RẠC 2

Đường đi Euler

TOÁN RỜI RẠC 2

™ Chu trình Euler là một đường đi Euler

nhưng ngược lại thì chưa chắc đã đúng (ví dụ trên đồ thị G3 thì a,c,d,e,b,d,a,b

là đường Euler, nhưng không phải là chu trình Euler).

™Chu trình Euler có thể đi qua một đỉnh hai lần (ví dụ chu trình a,e,c,d,e,b,a trên đồ thị G1) và có thể không đi qua một số

đỉnh nào đó nếu các đỉnh này là các đỉnh

cô lập, tức là các đỉnh có bậc bằng 0

1 Mở đầu

TOÁN RỜI RẠC 2

™Chu trình Euler chỉ liên quan đến các cạnh của đồ thị, vì vậy ta có thể thêm một số bất kỳ các đỉnh có bậc 0 (đỉnh

cô lập) vào đồ thị G thì chu trình

Euler của G vẫn không thay đổi.

TOÁN RỜI RẠC 2

2.Các điều kiện cần và đủ cho chu trình và

đường đi Euler

Định lý sau đây cho ta điều kiện cần và đủ để một đa đồthị có chu trình Euler:

™ Đồ thị vô hướng

Định lý 1 Một đa đồ thị không có điểm cô lập có chu

trình Euler nếu và chỉ nếu đồ thị là liên thông và mỗi

đỉnh của nó đều có bậc chẵn

™ Đối với đồ thị có hướng ta có định lý sau:

Định lý 2 Một đa đồ thị có hướng không có đỉnh cô lập

tồn tại chu trình Euler nếu và chỉ nếu đồ thị là liên thôngyếu đồng thời bậc-vào và bậc-ra của mỗi đỉnh là bằngnhau

TOÁN RỜI RẠC 23.Thuật toán tìm chu trình Euler

™ Bài toán: Cho đồ thị G = (V,E) Hãy tìm chu trình

Euler của đồ thị G nếu có

™ Thuật toán:

™ Bước 1: Kiểm tra tính liên thông của ĐT

Nếu G liên thông thì chuyển sang bước 2, ngược lại thì thông báo là chúng ta chỉ xét đồ thị liênthông và dừng thuật toán (Vì có thể thấy rằng nếu đồthị có một thành phần liên thông còn phần còn lại làcác điểm cô lập thì vẫn có thể có chu trình Euler, vìchu trình Euler chỉ quan tâm đến việc đi qua các cạnh

mà không quan tâm đến việc đi qua các đỉnh)

™ Bước 2: Kiểm tra xem ĐK cần và đủ của chu trình, đường đi euler

TOÁN RỜI RẠC 2

Bước 3: Xây dựng thuật toán tìm chu trình Euler đơn trong

G sao cho tất cả các cạnh của G đều có chu trình đơn điqua và chỉ đi qua một lần bằng cách sau:

™ Tạo mảng CE để ghi đường đi và một Stack để xếp cácđỉnh sẽ xét Đầu tiên xếp một đỉnh u nào đó của đồ thị vàoStack

™ Xét đỉnh v nằm trên cùng của Stack và thực hiện:

™ Nếu v là đỉnh cô lập thì lấy v ra khỏi Stack và đưa vào

TOÁN RỜI RẠC 2

10

4 5

6 7

1

TOÁN RỜI RẠC 2

TOÁN RỜI RẠC 2

TOÁN RỜI RẠC 2

™ void CTEuler(kmatran a, int n, int k kvecto CT, int &nCT)

™ {Stack S;kmatran B;int i,j,h,t;

™ SetEqual(B,a,n);//Dat b=a de khoi phuc lai gia tri sau nay

™ push(&S,k);//Dua dinh bat ky vao Stack, o day ta chon dinh 1

™ nCT=0;//Ban dau chu trinh chua co phan tu nao

™ while(empty(&S))

™ {h=viewtop(&S);i=1;

™ while(i<=n && a[h][i]==0) i++;//Tim i dau tien de a[h][i]#0

™ if(i==n+1) //h da la dinh co lap, dua h vao chu trinh CT

™ {nCT++;CT[nCT]=h; pop(&S,h);}//Lay dinh co lap ra khoi Stack

TOÁN RỜI RẠC 2

4.Đường đi và Chu trình Hamilton

™ Đường đi và chu trình Euler chỉ liên quan đến các cạnhcủa đồ thị Tuy nhiên câu hỏi tương tự có thể đặt ra đốivới các đỉnh Thí dụ trong một mạng lưới giao thông talại quan tâm đến việc xuất phát từ một thành phố, liệu ta

có thể đến thăm tất cả các thành phố khác mỗi thànhphố thăm đúng một lần và cuối cùng trở lại thành phốxuất phát?

TOÁN RỜI RẠC 2ĐỊNH NGHĨA

Cho đồ thị G = (V,E)

™ Đường đi R được gọi là đường đi Hamilton nếu nó điqua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần

™ Chu trình C được gọi là chu trình Hamilton nếu nó

xuất phát từ một đỉnh v nào đó, đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần rồi trở lại điểm v Đồ thị có chutrình Hamilton được gọi là đồ thị Hamilton

™ Đồ thị chứa đường đi Hamilton được gọi là đồ thị nửaHamilton

™ Trong các ví dụ sau chúng ta sẽ thấy là đồ thị Hamilton

là nửa Hamilton nhưng ngược lại không luôn luôn đúng