TAILIEUCHUNG - Bài giảng lý thuyết đồ thị - Chương 2

CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THị Biểu diễn bằng hình học Cho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau: Mỗi v ∈ V ta đặt tương ứng với một điểm trong mặt phẳng, điểm đó gọi là đỉnh của đồ thị. a) Trường hợp G là đồ thị vô hướng, nếu e = (u,v) ∈ V thì trong mặt phẳng, các đỉnh u, v được nối với nhau bởi một cạnh không có hướng. Đồ thị vô hướng G = ({v1, v2, v3, v4},. | Giáo án môn Lý Thuyết Đô Thị Chương 2 CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THỊ 6 tiết Biểu diễn bằng hình học Cho đồ thị G V E khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau Mỗi ve V ta đặt tương ứng với một điểm trong mặt phẳng điểm đó gọi là đỉnh của đồ thị. a Trường hợp G là đồ thị vô hướng nếu e u v e V thì trong mặt phẳng các đỉnh u v được nối với nhau bởi một cạnh không có hướng. Nếu e u u e V thì tại đỉnh u sẽ có một khuyên. b Trường hợp G là đồ thị có hướng Nếu e u v e V thì trong mặt phẳng sẽ có một cung có hướng đi từ u đến v. Nếu u v thì tại đỉnh u sẽ có một khuyên có hướng vào chính nó. Ví dụ 1 Đồ thị vô hướng G V1 V2 V3 v4 V1 V2 V2 V3 V2 V4 V3 V4 V4 V4 được biểu diễn hình học như sau V1 ĩ v3 v4 v2 Đồ thị có hướng G vi V2 V3 V1 V1 V1 V2 V2 V3 V3 V1 V3 V2 được biểu diễn hình học như sau v2 v3 Biểu diễn đồ thị bằng hình học là một cách biểu diễn đơn giản trực quan nhưng không có nhiều ý nghĩa trong việc xử lý bằng máy tính. Biểu diễn bằng ma trận kề liền kề ma trận trọng số Xét đơn đồ thị Vô hướng G V E Với tập đỉnh V v1 v2 . vn tập cạnh E e1 e2 . em . Ta gọi ma trận kề của đồ thị G là ma trận A ịa i j 1 2 . n Với các phần tử aij được xác định theo quy tắc sau aij 1 nếu vi Vj e E aij 0 nếu vi Vj Ể E i j 1 2 . n Ví dụ 2 Cho đồ thị Vô hướng G V1 V2 V3 V1 V1 V1 V2 V1 V3 V2 V3 Ma trận kề của G là 13 Nguyễn Minh Đức - ĐHQG Hà Nội Giáo án môn Lý Thuyết Đô Thị V1 v2 v3 v1 1 1 1 v2 1 0 1 v3 1 1 0 Ví dụ 3 Cho đồ thị vô hướng G như sau Ma trận kề của G là 1 2 3 4 5 1 0 1 0 1 0 2 1 0 1 0 1 3 0 1 0 1 0 4 1 0 1 0 1 5 0 1 0 1 0 Chú ý Ma trận kề của một đồ thị tuỳ thuộc vào thứ tự liệt kê các đỉnh. Do vậy có tới n ma trận kề khác nhau của một đồ thị n đỉnh vì có n cách sắp xếp n đỉnh. Các tính chất của ma trân kề của đồ thỉ đơn vô hướng a Ma trận kề của đơn đồ thị vô hướng n đỉnh là một ma trân vuông đối xứng cấp nxn. b Tổng các phần tử trên hàng i cột j của ma trận kề chính bằng bậc của đỉnh i đỉnh j . c Nếu kí hiệu aj i j 1 2 . n là các phần tử của ma

• Toán học
• biểu diễn đồ thị
• thuật toán
• đồ thị euler
• phương pháp biểu diễn
• cây khung
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Biểu diễn đồ thị bằng danh sách kề
• Ma trận liên thuộc
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• biểu diễn hình học
• biêu diễn đồ thị bằng ma trận
• biểu diễn đồ thị bằng bảng
• sự đẳng cấu của các đồ thị
• Số cạnh của đồ thị
• Cách biểu diễn đồ thị
• Ma trận trọng số
• Bài toán trên đồ thị
• Gom cụm đồ thị
• Khối thông điệp
• Diễn đàn thảo luận
• Bài toán gom cụm phẳng
• Biểu diễn văn bản bằng đồ thị
• Gom cụm đồ thị bằng mạng Kohonen
• tài liệu về đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Bài giảng Toán rời rạc
• Đồ thị liên thông
• Biểu diễn đồ thị bằng ma trận
• Bài toán đường đi ngắn nhất
• Tiếp cận kết thúc mở
• Biểu diễn trực quan
• Biểu diễn đồ thị hàm số
• Hàm bậc hai
• Tính chất của dãy số
• Dạy học toán
• Khái niệm đồ thị
• đồ thị con
• đồ thị riêng
• sự đẳng hình của đồ thị
• định nghĩa đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• Đồ thị phẳng
• bài toán luồng trên mạng
• tài liệu lý thuyết đồ thị
• đồ thị có hướng
• đồ thị hữu hạn
• đồ thị vô hạn
• Tìm kiếm trên đồ thị
• Đồ thị Hamilton
• Thuật toán đồ thị
• Ứng dụng tìm kiếm trên đồ thị
• Bài toán cây khung nhỏ nhất
• Thuật toán duyệt đồ thị