From Wikipedia, the free encyclopedia
Trong toán học và tin học, đồ thị là đối tượng nghiên cứu cơ bản của lý thuyết đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng gọi là đỉnh nối với nhau bởi các cạnh. Thông thường, đồ thị được vẽ dưới dạng một tập các điểm (đỉnh, nút) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theo ứng dụng mà một số cạnh có thể có hướng.
 | Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
Trong các tài liệu, các định nghĩa trong lý thuyết đồ thị được phát biểu theo nhiều kiểu. Dưới đây là kiểu truyền thống của cuốn từ điển bách khoa này.
Đồ thị vô hướng hoặc đồ thị G là một cặp không có thứ tự (unordered pair) G:=(V, E), trong đó
Trong nhiều tài liệu, tập các cạnh bao gồm cả các cặp đỉnh không phân biệt, các cạnh này được gọi là các khuyên. V (và E) thường là các tập hữu hạn, phần lớn các kết quả nghiên cứu đã biết không đúng (hoặc khác) khi áp dụng cho đồ thị vô hạn (infinite graph) vì nhiều luận cứ không dùng được trong trường hợp vô hạn.
Đồ thị có hướng G là một cặp có thứ tự G:=(V, A), trong đó
Đơn đồ thị là đồ thị mà không có khuyên và không có cạnh song song.
Đa đồ thị là đồ thị mà không thỏa mãn đơn đồ thị.
Đa đồ thị có hướng là một đồ thị có hướng, trong đó, nếu x và y là hai đỉnh thì đồ thị được phép có cả hai cung (x, y) và (y, x).
Đơn đồ thị có hướng (hoặc Đa đồ thị có hướng) là một đồ thị có hướng, trong đó, nếu x và y là hai đỉnh thì đồ thị chỉ được phép có tối đa một trong hai cung (x, y) hoặc (y, x).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
