TAILIEUCHUNG - ĐẠI CƯƠNG VỀ ĐỒ THỊ

Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp V và E, trong đó V các phần tử của V được gọi là các đỉnh (vertices), các phần tử của E được gọi là các cạnh (edges), mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh kề (hay 2 đỉnh liên kết) (adjacent) với nhau. Ta cũng nói cạnh e tới hay liên thuộc (incident) với các đỉnh | CHƯƠNG I ĐẠI CƯƠNG VỀ ĐÒ THỊ I. Các khái niệm cơ bản 1. Đồ thị 2. Biểu diễn đồ thị 3. Bâc của đỉnh trong đồ thị 4. Chứng minh - giải bài toán bằng phương pháp đồ thị II. Môt số đồ thị đặc biệt 1. Đồ thị đầy đủ 2. Đồ thị vòng 3. Đồ thị hình bánh xe 4. Đồ thị đều 5. Các khối n-lâp phương 6. Đồ thị bù 7. Đồ thị lưỡng phân III. Sự đẳng cấu của các đồ thị 1. Định nghĩa 2. Đồ thị tự bù IV. Đồ thị có hướng 1. Định nghĩa 2. Bâc của đỉnh trong đồ thị có hướng V. Tính liên thông 1. Đường đi 2. Chu trình 3. Tính liên thông trong đồ thi vô hướng 4. Tính liên thông trong đồ thi có hướng VI. Môt số phép biến đổi đồ thi 1. Hợp của hai đồ thi 2. Phép phân chia sơ cấp I. Các khái niệm cơ bản 1. Đồ thi Đồ thi graph G V E là môt bô gồm 2 tập hợp V và E trong đó V 0 các phần tử của V được gọi là các đỉnh vertices các phần tử của E được gọi là các cạnh edges mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v w thì ta nói v và w là 2 đỉnh kề hay 2 đỉnh liên kết adjacent với nhau. Ta cũng nói cạnh e tới hay liên thuộc incident với các đỉnh v và w. Ký hiệu e hay v w hoặc e vw e wv . Cạnh tương ứng với 2 đỉnh trùng nhau gọi là môt vòng hay khuyên loop tại v. Hai cạnh phân biệt cùng tương ứng với môt cặp đỉnh được gọi là 2 cạnh song song paralleledges hay cạnh bôi. Đồ thi không có cạnh song song và cũng không có vòng được gọi là đơn đồ thi simple graph . Ngược lại là đa đồ thi multigraph . Đồ thi mà mọi cặp đỉnh của nó đều kề nhau được gọi là đồ thi đầy đủ. Complete graph . Đơn đồ thi đầy đủ bao gồm n đỉnh được ký hiệu Kn. Đồ thi G V E được gọi là môt đồ thi con subgraph của đồ thi G V E nếu V G V E E. Đồ thi có số đỉnh và số cạnh hữu hạn được gọi là đồ thi hữu hạn finite graph ngược lại được gọi là đồ thi vô hạn Infinite graph . Trong giáo trình này chúng ta chỉ khảo sát các đồ thi hữu hạn. 2. Biểu diễn đồ thi Môt đồ thi có thể được biểu diễn bằng hình học môt ma trận hay môt bảng. . Biểu diễn hình học Người ta thường biểu diễn hình học của đồ thị như sau - Biểu diễn mỗi .

• Toán học
• tài liệu về đồ thị
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• lý thuyết đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• đồ thị
• giáo trình đồ thị
• ứng dụng của đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị