tailieunhanh - BÀI GIẢNG: LÝ THUYẾT ĐỒ THỊ (DƯƠNG ANH ĐỨC)

Một đồ thị có hướng G=(X, U) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp U là tập các cạnh của đồ thị; Mỗi cạnh uU được liên kết với một cặp đỉnh (i, j)X2. Đồ thị có tập đỉnh và tập cạnh hữu hạn được gọi là ĐỒ THỊ HỮU HẠN Học phần này chỉ làm việc các ĐỒ THỊ HỮU HẠN, tuy nhiên để ngắn gọn chúng ta chỉ dùng thuật ngữ ĐỒ THỊ và hiểu ngầm đó là đồ thị hữu hạn | LÝ THUYẾT ĐỒ THỊ ntsonptnk@ NỘI DUNG Đại cương về đồ thị Cây Các bài toán đường đi Đồ thị phẳng và bài toán tô màu đồ thị Mạng và bài toán luồng trên mạng, bài toán cặp ghép GV: Döông Anh Ñöùc TÀI LIỆU THAM KHẢO Giáo trình Lý Thuyết Đồ Thị - Dương Anh Đức, Trần Đan Thư Toán rời rạc – Nguyễn Tô Thành, Nguyễn Đức Nghĩa . GV: Döông Anh Ñöùc ĐẠI CƯƠNG VỀ ĐỒ THỊ ĐỊNH NGHĨA Một đồ thị có hướng G=(X, U) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp U là tập các cạnh của đồ thị; Mỗi cạnh u U được liên kết với một cặp đỉnh (i, j) X2. GV: Döông Anh Ñöùc ĐỊNH NGHĨA Một đồ thị vô hướng G=(X, E) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp E là tập các cạnh của đồ thị; Mỗi cạnh e E được liên kết với một cặp đỉnh {i, j} X2, không phân biệt thứ tự GV: Döông Anh Ñöùc ĐỒ THỊ HỮU HẠN Đồ thị có tập đỉnh và tập cạnh hữu hạn được gọi là ĐỒ THỊ HỮU HẠN Học phần này chỉ làm việc các ĐỒ THỊ HỮU HẠN, tuy nhiên để . | LÝ THUYẾT ĐỒ THỊ ntsonptnk@ NỘI DUNG Đại cương về đồ thị Cây Các bài toán đường đi Đồ thị phẳng và bài toán tô màu đồ thị Mạng và bài toán luồng trên mạng, bài toán cặp ghép GV: Döông Anh Ñöùc TÀI LIỆU THAM KHẢO Giáo trình Lý Thuyết Đồ Thị - Dương Anh Đức, Trần Đan Thư Toán rời rạc – Nguyễn Tô Thành, Nguyễn Đức Nghĩa . GV: Döông Anh Ñöùc ĐẠI CƯƠNG VỀ ĐỒ THỊ ĐỊNH NGHĨA Một đồ thị có hướng G=(X, U) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp U là tập các cạnh của đồ thị; Mỗi cạnh u U được liên kết với một cặp đỉnh (i, j) X2. GV: Döông Anh Ñöùc ĐỊNH NGHĨA Một đồ thị vô hướng G=(X, E) được định nghĩa bởi: Tập hợp X được gọi là tập các đỉnh của đồ thị; Tập hợp E là tập các cạnh của đồ thị; Mỗi cạnh e E được liên kết với một cặp đỉnh {i, j} X2, không phân biệt thứ tự GV: Döông Anh Ñöùc ĐỒ THỊ HỮU HẠN Đồ thị có tập đỉnh và tập cạnh hữu hạn được gọi là ĐỒ THỊ HỮU HẠN Học phần này chỉ làm việc các ĐỒ THỊ HỮU HẠN, tuy nhiên để ngắn gọn chúng ta chỉ dùng thuật ngữ ĐỒ THỊ và hiểu ngầm đó là đồ thị hữu hạn. GV: Döông Anh Ñöùc ĐỈNH KỀ Trên đồ thị có hướng, xét cạnh u được liên kết với cặp đỉnh (i, j): Cạnh u kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh u); có thể viết tắt u=(i, j). Cạnh u đi ra khỏi đỉnh i và đi vào đỉnh j Đỉnh j được gọi là đỉnh kề của đỉnh i GV: Döông Anh Ñöùc ĐỈNH KỀ Trên đồ thị vô hướng, xét cạnh e được liên kết với cặp đỉnh (i, j): Cạnh e kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh e); có thể viết tắt e=(i, j). Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau (hay đỉnh i kề với đỉnh j và ngược lại, đỉnh j kề với đỉnh i) GV: Döông Anh Ñöùc MỘT SỐ KHÁI NIỆM Cạnh song song Khuyên Đỉnh treo Đỉnh cô lập GV: Döông Anh Ñöùc CÁC DẠNG ĐỒ THỊ Đồ thị RỖNG: tập cạnh là tập rỗng Đồ thị ĐƠN: không có khuyên và cạnh song song Đồ thị ĐỦ: đồ thị vô hướng, đơn, giữa hai đỉnh bất kỳ đều có đúng một cạnh. Đồ thị đủ N đỉnh ký hiệu là KN. KN có N(N-1)/2 cạnh. GV: Döông Anh .