TAILIEUCHUNG - Bài giảng Toán rời rạc 2 - Khái niệm về đồ thị

Bài giảng "Toán rời rạc 2 - Khái niệm về đồ thị" cung cấp cho người học các kiến thức: Định nghĩa đồ thị, một số thuật ngữ cơ bản trên đồ thị vô hướng, một số thuật ngữ cơ bản trên đồ thị có hướng, một số dạng đồ thị đặc biệt. Mời các bạn cùng tham khảo. | Bài giảng Toán rời rạc 2 - Khái niệm về đồ thị KHÁI NIỆM VỀ ĐỒ THỊ Toán rời rạc 2 Nội dung Định nghĩa đồ thị Một số thuật ngữ cơ bản trên đồ thị vô hướng Một số thuật ngữ cơ bản trên đồ thị có hướng Một số dạng đồ thị đặc biệt Bài tập 2 Định nghĩa đồ thị Đơn đồ thị vô hướng Đơn đồ thị vô hướng G lt V E gt bao gồm V là tập các đỉnh E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. 4 Đa đồ thị vô hướng Đa đồ thị vô hướng G bao gồm V là tập các đỉnh E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là tập các cạnh. e1 E e2 E được gọi là cạnh bội nếu chúng cùng tương ứng với một cặp đỉnh. 5 Giả đồ thị vô hướng Giả đồ thị vô hướng G bao gồm V là tập đỉnh E là họ các cặp không có thứ tự gồm hai phần tử hai phần tử không nhất thiết phải khác nhau trong V được gọi là các cạnh. Cạnh e được gọi là khuyên nếu có dạng e u u trong đó u là đỉnh nào đó thuộc V. 6 Đơn đồ thị có hướng Đơn đồ thị có hướng G bao gồm V là tập các đỉnh E là tập các cặp có thứ tự gồm hai phần tử của V gọi là các cung. 7 Đa đồ thị có hướng Đa đồ thị có hướng G bao gồm V là tập đỉnh E là cặp có thứ tự gồm hai phần tử của V được gọi là các cung. Hai cung e1 e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp. 8 Phân biệt các loại đồ thị Loại đồ thị Cạnh Có cạnh bội Có khuyên Đơn đồ thị vô hướng Vô hướng Không Không Đa đồ thị vô hướng Vô hướng Có Không Giả đồ thị vô hướng Vô hướng Có Có Đơn đồ thị có hướng Có hướng Không Không Đa đồ thị có hướng Có hướng Có Có 9 Quy ước Ta chủ yếu làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Khi viết đồ thị vô hướng ta hiểu là đơn đồ thị vô hướng . Khi viết đồ thị có hướng ta hiểu là đơn đồ thị có hướng . 10 Một số thuật ngữ cơ bản trên đồ thị vô hướng Bậc của đỉnh ĐN 1. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu u v là cạnh thuộc đồ thị G. Nếu e u v là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v hoặc ta nói cạnh e nối đỉnh u với đỉnh v đồng thời các đỉnh u và v .

• Toán học
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Khái niệm về đồ thị
• Đđồ thị vô hướng
• Đồ thị có hướng
• Dạng đồ thị đặc biệt
• 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 toán rời rạc
• lý thuyết toán rời rạc
• đề cương Toán rời rạc
• tìm hiểu Toán rời rạc
• Thuật toán Dijkstra
• Thuật toán Bellman Ford
• Bài toán tìm đường đi ngắn nhất
• Toán học rời rạc
• Cấu trúc rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Bài giảng Toán học rời rạc
• Tìm kiếm trên đồ thị
• Thuật toán tìm kiếm
• Ứng dụng của thuật toán tìm kiếm
• Công nghệ thông tin
• Giới thiệu môn học
• Trí tuệ nhân tạo
• Biểu diễn đồ thị trên máy tính
• Biểu diễn đồ thị
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Đồ thị Euler
• Đồ thị Hamilton
• Chứng minh đồ thị là nửa Euler
• Toán rời rạc ứng dụng trong tin học
• Bài toán về đường đi
• Đường đi Euler
• Đường đi Hamilton
• Cây khung của đồ thị
• Hàm đơn ánh
• Độ tăng của hàm
• Thuật toán
• Thuật toán sắp xếp nổi bọt
• Hàm và thuật toán
• Độ phức tạp của thuật toán
• Nguyên lý bù trừ
• Hoán vị lặp
• Tổ hợp lặp
• Giải tích tổ hợp
• Hệ thức đệ qui
• Lý thuyết tập hợp
• Phép toán tập hợp
• Tích Descartes
• cơ sở dữ liệu
• hệ thống dữ liệu
• Bài giảng Hàm Bool
• Phép toán trên hàm Bool
• Dạng nối rời chính tắc của Hàm Bool
• Phương pháp biểu đồ Karnaugh
• Đồ thị vô hướng
• Biểu diễn đồ thị bằng ma trận kề
• Thuật toán tìm kiếm theo chiều sâu
• Bài giảng Quan hệ
• Quan hệ 2 ngôi
• Tính chất quan hệ 2 ngôi
• Tập hợp thương
• Bài giảng Toán rời rạc 1
• Toán rời rạc 1
• Bài toán liệt kê
• Thuật toán quay lui
• Thuật toán nhánh
• Nguyên lý Dirichlet
• Duyệt đồ thị
• Bài toán đường đi ngắn nhất
• Lý thuyết đồ thị
• Bài toán luồng cực đại