TAILIEUCHUNG - Giáo trình đồ thị - Khái niệm đồ thị

Chúng ta đã nhìn thấy hoặc sử dụng bản đồ các tuyến đường giao thông của một thành phố, sơ đồ tổ chức một cơ quan, sơ đồ khối tính toán của một thuật toán, sơ đồ một mạng máy tính . Đó là những ví dụ cụ thể về đồ thị. Đồ thị (graph) là một mô hình toán học được ứng dụng trong nhiều lĩnh vực khoa học, kỹ thuật và được định nghĩa như sau. | BÀI 01 . Khái niệm đồ thị . Định nghĩa đồ thị Chúng ta đã nhìn thấy hoặc sử dụng bản đồ các tuyến đường giao thông của một thành phố sơ đồ tổ chức một cơ quan sơ đồ khối tính toán của một thuật toán sơ đồ một mạng máy tính . Đó là những ví dụ cụ thể về đồ thị. Đồ thị graph là một mô hình toán học được ứng dụng trong nhiều lĩnh vực khoa học kỹ thuật và được định nghĩa như sau. Định nghĩa Đồ thị là một cặp G V E trong đó 1 V là tập hợp các đỉnh vertex 2 E c V X V là tập hợp các cạnh edge . Ví dụ Hình Đồ thị hữu hạn Đồ thị G cho ở hình vẽ trên với tập các đỉnh V a b c d e và tập các cạnh E a b a c b c d b d c e a e b e d . Nếu a b là một cạnh của đồ thị thì ta nói rằng đỉnh b kề với đỉnh a và cả hai đỉnh a và b kề với cạnh a b . Trong đồ thị ở Ví dụ hai đỉnh b và c kề với đỉnh a ba đỉnh a b và d kề với đỉnh e. Do vậy ta có thể định nghĩa đồ thị bằng ánh xạ kề như sau. Định nghĩa Đồ thị là một cặp G V F trong đó 1 V là tập hợp các đỉnh 2 F V 2V được gọi là ánh xạ kề. ánh xạ kề của đồ thị trong Ví dụ được xác định như sau F a b c F b c F c 0 F d b c và F e a b d . Sự tương đương của hai định nghĩa của đồ thị được thể hiện bằng mệnh đề sau đây V x y E V x y E E y E F x . về bản chất đồ thị là một tập hợp các đối tượng được biểu diễn bằng các đỉnh và giữa các đối tượng này có một quan hệ nhị nguyên biểu diễn bằng các cạnh. Cặp đỉnh x y G E không sắp thứ tự được gọi là cạnh vô hướng còn nếu nó có sắp thứ tự thì được gọi là cạnh có hướng. Vì thế chúng ta thường phân các đồ thị thành hai lớp. Định nghĩa Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ thị vô hướng còn đồ thị chỉ chứa các cạnh có hướng được gọi là đồ thị có hướng. Hiển nhiên mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng bằng cách thay mỗi cạnh vô hướng bằng hai cạnh có hướng tương ứng. Định nghĩa Đồ thị G V E được gọi là đối xứng nếu V x y G V x y G E y x G E. Các đồ thị vô hướng là đối xứng. Định nghĩa Đồ thị G V E mà mỗi cặp đỉnh được nối với nhau

• Toán học
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• tài liệu về đồ thị
• Lý thuyết đồ 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ị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ 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ề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• toán rời rạc
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• 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