TAILIEUCHUNG - Bài giảng Toán học rời rạc và cấu trúc rời rạc: Chương 4 - Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh

Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 4: Đại cương về đồ thị" cung cấp cho người học các kiến thức: Giới thiệu, các khái niệm cơ bản, biểu diễn đồ thị, đẳng cấu đồ thị, đường đi, chu trình. | Chương 4. ĐẠI CƯƠNG VỀ ĐỒ THỊ lvluyen@ http luyen cautrucroirac FB cautrucroirac https tailieudientucntt Nội dung 1. Giới thiệu 2. Các khái niệm cơ bản 3. Biểu diễn đồ thị 4. Đẳng cấu đồ thị 5. Đường đi chu trình https tailieudientucntt 2 1. Giới thiệu Bài toán. Thành phố Königsberg Đức nằm trên một con sông có hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Bài toán đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không https tailieudientucntt 3 Năm 1736 nhà toán học Leonhard Euler đã chứng minh rằng điều đó là không thể được. https tailieudientucntt 4 Bài toán 1. Có thể vẽ hình phong bì thư bởi một nét bút hay không Nếu có hãy chỉ ra tuần tự các nét vẽ 1 2 3 4 5 https tailieudientucntt 5 Bài toán 2. Một đoàn kiểm tra chất lượng các con đường. Để tiết kiệm thời gian đoàn kiểm tra muốn đi qua mỗi con đường đúng 1 lần. Kiểm tra xem có cách đi như vậy không 4 7 5 1 8 6 2 3 https tailieudientucntt 6 Bài toán 3. Một sinh viên muốn đi từ nhà đến trường thì phải đi như thế nào Cách đi nào là ngắn nhất https tailieudientucntt 7 2. Các khái niệm cơ bản Định nghĩa. Một đồ thị vô hướng undirected graph G V E được định nghĩa bởi Tập hợp V được gọi là tập các đỉnh vertex và n V gọi là cấp của đồ thị Tập hợp E là tập các cạnh edge của đồ thị Mỗi cạnh e E được liên kết với một cặp đỉnh i j không phân biệt thứ tự https tailieudientucntt 8 Đỉnh kề Định nghĩa. 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 ij Đỉ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 Hai cạnh nối cùng một cặp đỉnh gọi là hai

• Toán học
• Toán học rời rạc
• Cấu trúc rời rạc
• Biểu diễn đồ thị
• Đẳng cấu đồ thị
• Đại cương về đồ thị
• Bài giảng Toán học rời rạc
• Toán rời rạc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc
• Câu hỏi Toán rời rạc
• Ôn thi Toán rời rạc
• Luyện thi Toán rời rạc
• Bài thi Toán rời rạc
• Hướng dẫn thi Toán rời rạc
• Câu hỏi thi Toán rời rạc
• Học phần Toán rời rạc 1
• Toán rời rạc 1
• Câu hỏi thi Toán rời rạc 1
• Ngân hàng câu hỏi Toán rời rạc 1
• Thi tự luận Toán rời rạc 1
• Hướng dẫn thi Toán rời rạc 1