Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌCBài giảng dùng cho lớp SP.Toán Tin K31 Giảng viên: Phạm Văn Huy (Email: pvhuy@ctu.edu.vn) Bộ môn Toán – Khoa Sư phạm - ĐHCT1Nội dung môn họcPhần 1: Lý thuyết đồ thịĐại cương về đồ thịCác bài toán về đường điĐồ thị phẳng và bài toán tô màu đồ thịCâyPhần 2: Đại số BooleĐại số BooleCổng logicCực tiểu hóa hàm Boole2Các khái niệm cơ bảnĐồ thị (Graph)G = (V, E) với V≠V: tập các đỉnhE: tập các cạnh Cạnh eEứng với 2 đỉnh u, vVv, w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và wKý hiệu: e = vw ()u v: e được gọi là vòng (khuyên) tại u3Các khái niệm cơ bảnĐồ thị (Graph)Cạnh bội (song song)Hai cạnh phân biệt cùng tương ứng với một cặp đỉnhĐơn đồ thịĐồ thị không có vòng và cạnh song songĐa đồ thịCác đồ thị không phải là đơn đồ thị4Các khái niệm cơ bảnĐồ thị (Graph)Đồ thị đầy đủĐồ thị mà mọi cặp đỉnh đều kề nhauKn: đơn đồ thị đầy đủĐồ thị conĐồ thị G’ = (V’, E’) V’  V, E’  EĐồ thị hữu hạnE và V hữu hạnĐồ thị vô hạn5Biểu diễn đồ thịBiểu diễn hình họcMỗi đỉnh  một điểmMỗi cạnh  một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nóBiểu diễn bằng ma trậnThường được dùng để biểu diễn trên máy tính2 cách biểu diễn thường dùngMa trận kềMa trận liên thuộc6Biểu diễn đồ thịBiểu diễn bằng ma trậnMa trận kềMa trận vuông cấp n (số đỉnh của đồ thị)Các phần tử aij được xác định bởiaij = 1: Nếu vivj là một cạnh của Gaij = 0: Nếu vivj không là một cạnh của GTính chấtPhụ thuộc vào thứ tự liệt kê của các đỉnhMa trận là đối xứngMột vòng được tính là một cạnh (akk = 1)7Biểu diễn đồ thịBiểu diễn bằng ma trậnMa trận kềVí dụ 18Biểu diễn đồ thịBiểu diễn bằng ma trậnMa trận kềVí dụ 29Biểu diễn đồ thịBiểu diễn bằng ma trậnMa trận liên thuộcMa trận M = (mij)nxmCác phần tử mij được xác định bởimij = 1: Nếu cạnh ej liên thuộc với vi của Gmij = 0: Nếu cạnh ej không liên thuộc với vi của GTính chấtCác cột tương ứng với các cạnh bội là giống nhau trong ma trân liên thuộcCác vòng ứng với một cột có đúng một phần tử bằng 1 ứng với đỉnh nối với nó.10Biểu diễn đồ thịBiểu diễn bằng ma trậnMa liên thuộcVí dụ11Biểu diễn đồ thịBiểu diễn bằng bảng (danh sách liền kề)Lưu trữ các đỉnh liền kề với một đỉnhVí dụĐỉnhĐỉnh liền kềab, c, ebaca, c, d, edc, eea, c, d12Các khái niệm cơ bảnBậc của đỉnhĐỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác.Ký hiệu: deg(v) hay d(v)Mỗi vòng được kể là 2 cạnh tới một đỉnhĐỉnh cô lập  deg(v)=0Đỉnh treo  deg(v)=1Cạnh treo có đầu mút là một đỉnh treoĐồ thị rỗng: deg(v)=0 v13Các khái niệm cơ bảnBậc của đỉnhĐịnh lý 1.1Trong mọi đồ thị G = (V, E), tổng số bậc của các đỉnh của G bằng 2 lần số cạnh của nóHệ quảTrong mọi đồ thị G = (V, E) ta cóSố đỉnh bậc lẻ là một số chẵnTổng bậc của đỉnh bậc lẻ là một số chẵn14Các khái niệm cơ bảnBậc của đỉnhĐịnh lý 1.2Trong mọi đồ thị G = (V, E), nếu số đỉnh nhiều hơn 1 thì tồn tại ít nhất hai đỉnh cùng bậcĐịnh lý 1.3Trong mọi đồ thị G = (V, E), nếu số đỉnh nhiều hơn 2 và có đúng hai đỉnh cùng bậc thì hai đỉnh này không đồng thời bằng 0 hoặc n-115Các khái niệm cơ bảnChứng minh và giải toán bằng phương pháp đồ thịXây dựng đồ thị mô tả đầy đủ thông tin của bài toánMỗi đỉnh vV  các đối tượng trong bài toánMỗi cạnh eE  mối quan hệ giữa hai đối tượngVẽ đồ thị mô tả bài toánSử dụng các định nghĩa, tính chất, định lý,  suy ra điều cần phải chứng minh16Các khái niệm cơ bảnMột số bài toán ví dụChứng minh rằng trong một cuộc họp tùy ý có ít nhất 2 đại biểu tham gia trở lên, luôn có ít nhất hai đại biểu mà họ có số người quen bằng nhau trong các đại biểu đến dự họp17Các khái niệm cơ bảnMột số bài toán ví dụChứng minh rằng số người mà mỗi người đã có một số lẻ lần bắt tay nhau trên trái đất là một con số chẵn.18Một số đồ thị đặc biệtĐồ thị đầy đủ KnĐơn đồ thịSố đỉnh: 	|V| = nBậc: 	deg(v) = n – 1 v VSố cạnh:	 |E| = n(n - 1) / 219Một số đồ thị đặc biệtĐồ thị vòng CnĐơn đồ thịSố đỉnh: 	|V| = n  3Bậc: 	deg(v) = 2 v VSố cạnh:	 |E| = n20Một số đồ thị đặc biệtĐồ thị hình bánh xe WnNối các đỉnh của Cn với một đỉnh mới u ta được WnSố đỉnh: 	|V| = n + 1  3Bậc: 	deg(v) = 3 v V \ {u};	deg(u) = nSố cạnh:	 |E| = 2n21Một số đồ thị đặc biệtĐồ thị đềuNối các đỉnh của Cn với một đỉnh mới u ta được WnSố đỉnh: 	|V| = n + 1  3Bậc: 	deg(v) = 3 v V \ {u};	deg(u) = nSố cạnh:	 |E| = 2n22Một số đồ thị đặc biệtCác khối n-lập phươngNối các đỉnh của Cn với một đỉnh mới u ta được WnSố đỉnh: 	|V| = n + 1  3Bậc: 	deg(v) = 3 v V \ {u};	deg(u) = nSố cạnh:	 |E| = 2n23Một số đồ thị đặc biệtĐồ thị bùHai đơn đồ thị G và G’ được gọi là bù nhau chúng có chung các đỉnhCạnh nào thuộc G thì không thuộc G’ và ngược lạiKý hiệu: G’ = G24Một số đồ thị đặc biệtĐồ thị lưỡng phânMột đồ thị G được gọi là đồ thị lưỡng phân nếu tập các đỉnh của G có thể phân thành 2 tập hợp không rỗng, rời nhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập này đến một đỉnh thuộc tập kia.Ký hiệu: Km,n25TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌCBài giảng dùng cho lớp SP.Toán Tin K31 Giảng viên: Phạm Văn Huy (Email: pvhuy@ctu.edu.vn) Bộ môn Toán – Khoa Sư phạm - ĐHCT26Sự đẳng cấu giữa các đồ thịĐịnh nghĩaG(V, E) đẳng cầu với G’(V’, E’), (GG’) nếuTồn tại song ánh f: V  V’Bảo toàn quan hệ liền kề:uv E  f(u)f(v) E’G đẳng cấu với G’ thì|V| = |V’||E| = |E’|deg(v) = deg(f(v))	 v V27Sự đẳng cấu giữa các đồ thịĐịnh nghĩaChứng minh 2 đồ thị đẳng cấuĐiều kiện cần Xét số cạnh, số đỉnh, bậc của đỉnhĐiều kiện đủ Xây dựng song ánh bảo toàn quan hệ liền kềVí dụ 128Sự đẳng cấu giữa các đồ thịĐịnh nghĩaChứng minh 2 đồ thị đẳng cấuVí dụ 229Sự đẳng cấu giữa các đồ thịĐồ thị tự bùĐịnh nghĩaĐồ thị G tự bù nếu G đẳng cấu với phần bù của nóVí dụĐịnh lý 1.4Hai đồ thị có ma trận liền kề (theo một thứ tự nào đó của các đỉnh) bằng nhau thì đẳng cấu với nhau30Đồ thị có hướngĐịnh nghĩaG = (V, E)Tập đỉnh VTập cạnh (cung) E = { (a, b) | a,b  V }e = (a, b)  EKý hiệu: e = e có hướng từ a đến ba: đỉnh đầu;	b: đỉnh cuốie là khuyên  ab31Đồ thị có hướngBậc của đỉnhBậc vàodeg - (v) = | { u | (u, v)  E } |Bậc radeg + (v) = | { u | (v, u)  E } |32Đồ thị có hướngBậc của đỉnhĐịnh lý 1.5Tổng bậc vào của các đỉnh bằng tổng bậc ra và bằng số cạnh của đồ thị Đồ thị cân bằng33Đồ thị có hướngBậc của đỉnhVí dụCó một nhóm gồm 9 đội bóng bàn thi đấu vòng tròn một lượt.Hỏi sau khi có kết quả thi đấu của tất cả các đội có thể có trường hợp bất kỳ đội nào trong 09 đội này cũng đều thắng 05 đội khác trong nhóm được không? 34Đường đi và chu trìnhĐường điĐịnh nghĩaĐường đi là một dãy các cạnh liên tiếpKý hiệu v0v1, v1v2, , vn-1vnv0v1v2  vn-1vnv0: đỉnh đầu;	vn: đỉnh cuối35Đường đi và chu trìnhĐường điĐịnh nghĩaĐường đi đơn (giản)Đường đi không qua cạnh nào quá một lầnĐường đi sơ cấpĐường đi không qua đỉnh nào quá một lầnĐường sơ cấp  Đường đi đi đơn 36Đường đi và chu trìnhChu trìnhĐịnh nghĩaChu trình đường đi khép kín (v0v1v2  vn-1vnv0)độ dài ít nhất là 3Chu trình đơn giảnChu trình không chứa cạnh nào quá 1 lầnChu trình sơ cấpChu trình không chứa đỉnh nào quá 1 lần37Đường đi và chu trìnhChu trìnhĐịnh lý 1.6G = (V, E) là một đồ thị vô hướngSố đỉnh lớn hơn hoặc bằng 3Bậc của mọi đỉnh đều lớn hơn hoặc bằng 2thì trong G luôn tồn tại một chu trình sơ cấpĐịnh lý 1.7G = (V, E) là một đồ thị vô hướngSố đỉnh lớn hơn hoặc bằng 4Bậc của mọi đỉnh đều lớn hơn hoặc bằng 3thì trong G luôn tồn tại một chu trình sơ cấp có độ dài chẵn38Tính liên thôngTính liên thông trong đồ thị vô hướngĐịnh nghĩaMột đồ thị liên thông nếu giữa hai đỉnh phân biệt bất kỳ đều có đường điThành phần liên thôngĐồ thị con G’ = (V’, E’) G’ liên thôngĐịnh lý 1.8Đồ thị G=(V, E) là liên thông khi và chỉ khi G có duy nhất một thành phần liên thông39Tính liên thôngTính liên thông trong đồ thị vô hướngĐỉnh cắt và cầuu là một đỉnh cắt  số thành phần liên thông tăng lên nếu bỏ u và các cạnh liên thuộc với nóe là một cầu  số thành phần liên thông tăng lên nếu bỏ cạnh e 40Tính liên thôngTính liên thông trong đồ thị vô hướngĐịnh lý 1.9G = (V , E)|V| = n  2deg(u) + deg(v)  n  u,v  Vthì G là đồ thị liên thôngHệ quảG = (V , E)|V| = n  2deg(v)  n/2  u,v  Vthì G là đồ thị liên thông41Tính liên thôngTính liên thông trong đồ thị có hướngLiên thông mạnhĐồ thị có hướng G được gọi 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 nóLiên thông yếuĐồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông42Tính liên thôngTính liên thông trong đồ thị có hướngĐịnh lý 1.10Nếu đồ thị G có đúng 2 đỉnh bậc lẻ thì 2 đỉnh này phải liên thông với nhauĐịnh lý 1.11Đồ thị G là một đồ thị lưỡng phân khi và chỉ khi mọi chu trình của nó đều có độ dài chẵn43Một số phép biến đổi đồ thịHợp của 2 đồ thịG = (V, E)G’ = (V’, E’)G’’ = G  G’ = (V’’, E’’)V’’ = V  V’E’’ = E  E’44Một số phép biến đổi đồ thịPhép phân chia sơ cấpPhép thay thế cạnh e = uv bởi một đỉnh mới cùng với 2 cạnh uw và vwĐồng phôiG đồng phôi với G’ nếu chúng có thể nhận được từ cùng một đồ thị bằng một dãy các phép phân chia sơ cấpHai đồ thị đồng phôi chưa chắc đẳng cấu với nhau45