Bài này chỉ viết về các định nghĩa cơ bản. Để gọi rộng hơn, xin xem triết lý đồ thị. Về ý nghĩa sâu sắc biểu diễn hàm số bên trên hệ tọa độ, xem trang bị thị hàm số. Trong toán học cùng tin học, đồ thị là đối tượng người sử dụng nghiên cứu cơ bạn dạng của lý thuyết đồ thị. Một giải pháp không chủ yếu thức, đồ dùng thị là 1 trong tập các đối tượng gọi là đỉnh nối cùng nhau bởi những cạnh. Thông thường, đồ dùng thị được vẽ dưới dạng một tập những điểm (đỉnh, nút) nối với nhau bởi những đoạn trực tiếp (cạnh). Phụ thuộc vào ứng dụng mà một số cạnh hoàn toàn có thể có hướng. Một vật thị vô phía với 6 đỉnh (nút) cùng 7 cạnh. Mục lụcCác định nghĩaSửa đổiTrong những tài liệu, những định nghĩa trong định hướng đồ thị được phạt biểu theo rất nhiều kiểu. Dưới đó là kiểu truyền thống lâu đời của cuốn tự điển bách khoa này. Đồ thị vô hướngSửa đổi Đồ thị vô hướng hoặc đồ thị G là một trong cặp không tồn tại thứ trường đoản cú (unordered pair) G:=(V, E), vào đó V, tập những đỉnh hoặc nút,E, tập các cặp không sản phẩm công nghệ tự chứa những đỉnh phân biệt, được hotline là cạnh. Hai đỉnh trực thuộc một cạnh được gọi là các đỉnh đầu cuối của cạnh đó.Trong các tài liệu, tập những cạnh bao gồm cả những cặp đỉnh ko phân biệt, những cạnh này được call là những khuyên. V (và E) hay là các tập hữu hạn, đa số các kết quả nghiên cứu đã biết không nên (hoặc khác) khi áp dụng cho đồ thị vô hạn (infinite graph) bởi vì nhiều luận cứ không dùng được vào trường hòa hợp vô hạn. Đồ thị tất cả hướngSửa đổi Đồ thị bao gồm hướng G là một trong cặp có thứ từ bỏ G:=(V, A), vào đó V, tập các đỉnh hoặc nút,A, tập những cặp bao gồm thứ trường đoản cú chứa các đỉnh, được điện thoại tư vấn là các cạnh tất cả hướng hoặc cung. Một cạnh e = (x, y) được xem như là có hướng từ x tới y; x được gọi là điểm đầu/gốc và y được gọi là điểm cuối/ngọn của cạnh. Đơn đồ gia dụng thị với Đa vật thịSửa đổiĐơn trang bị thị là đồ vật thị mà không có khuyên và không tồn tại cạnh tuy vậy song. Đa đồ gia dụng thị là thứ thị mà lại không thỏa mãn đơn thiết bị thị. Đa thiết bị thị có hướng là 1 trong đồ thị tất cả hướng, vào đó, giả dụ x với y là hai đỉnh thì đồ dùng thị được phép gồm cả hai cung (x, y) cùng (y, x). Đơn đồ dùng thị tất cả hướng (hoặc Đơn vật thị bao gồm hướng) là 1 trong đồ thị tất cả hướng, trong đó, nếu x cùng y là hai đỉnh thì đồ dùng thị chỉ được phép bao gồm tối đa một trong hai cung (x, y) hoặc (y, x). Quiver thường xuyên được xem như là một đồ dùng thị gồm hướng. Dẫu vậy trong thực hành, nó là 1 trong đồ thị được bố trí theo hướng với các không khí vector (vector space) lắp với các đỉnh cùng các biến đổi tuyến tính lắp với những cung. Đồ thị láo hợpSửa đổiĐồ thị lếu hợp G là 1 trong những bộ tía có trang bị tự G:= (V,E,A) với V, E và A được có mang như trên. Các tư tưởng khácSửa đổiNhư đang được khái niệm ở trên, các cạnh của đồ dùng thị vô hướng tất cả hai đầu là nhị đỉnh phân biệt; E và A là những tập hòa hợp (với các phần tử phân biệt). Nhiều ứng dụng cần những khái niệm rộng lớn hơn, và những thuật ngữ cũng khác nhau. Một khuyên (loop) là 1 cạnh (vô hướng hoặc có hướng) nối xuất phát từ một đỉnh về thiết yếu nó; loại cạnh này có được chấp nhận hay không là tùy sinh hoạt ứng dụng. Trong văn cảnh này, một cạnh nối hai đỉnh khác nhau được gọi là 1 trong liên kết (link). Đôi khi, E và A được phép là những đa tập phù hợp (multiset), lúc ấy giữa nhì đỉnh gồm thể có không ít hơn một cạnh. Tất cả thể chất nhận được giữa nhì đỉnh có tương đối nhiều cạnh bằng cách cho E là 1 trong tập hợp chủ quyền với V, và xác định các điểm đầu của mỗi cạnh bằng một tình dục liên ở trong (incidence relation) thân V và E. Đối với thứ thị có hướng, ta áp dụng tương tự như cho tập đúng theo cạnh có hướng A, tuy nhiên, phải bao gồm hai dục tình liên thuộc, một mang đến đỉnh đầu và một mang lại đỉnh cuối của từng cung. Trong những sách, phụ thuộc vào ý của người sáng tác hoặc theo yêu ước của nhà đề rõ ràng mà từ bỏ "đồ thị" rất có thể hàm ý chất nhận được hoặc không có thể chấp nhận được khuyên hay đa cạnh. Nếu đồ dùng thị không có thể chấp nhận được đa cạnh (và không cho phép khuyên nếu như là thứ thị có hướng), trang bị thị được call là đơn đồ thị. Phương diện khác, nếu có thể chấp nhận được đa cạnh (và đôi khi cả khuyên), đồ thị được điện thoại tư vấn là đa thứ thị. Đôi khi, trường đoản cú giả đồ dùng thị (pseudograph) còn được dùng để làm hàm ý cả đa cạnh và khuyên gần như được phép. Trong số trường hợp quánh biệt, thậm chí còn cần đến các cạnh chỉ gồm một đỉnh, được điện thoại tư vấn là nửa cạnh (halfedge), hoặc không tồn tại đỉnh nào, (cạnh rời). Xem ví dụ tại signed graph. Hai cạnh của một đồ dùng thị được coi là kề nhau nếu chúng gồm chung một đỉnh. Tương tự, nhị đỉnh được coi là kề nhau nếu bọn chúng được nối với nhau bởi vì một cạnh. Một cạnh và đỉnh vị trí cạnh đó được coi là liên thuộc với nhau. Đồ thị chỉ gồm một đỉnh và không có cạnh làm sao được hotline là đồ thị khoảng thường. Đồ thị không có cả đỉnh lẫn cạnh được gọi là đồ thị rỗng Trong một đồ thị bao gồm trọng số, mỗi cạnh được đính thêm với một quý hiếm nào đó, được hotline là trọng số, độ dài, chi phí, hoặc các tên khác tùy thuộc vào ứng dụng; các đồ thị do vậy được dùng trong vô số ngữ cảnh, chẳng hạn trong các bài toán tối ưu hóa đường đi như bài toán người chào bán hàng. Ví dụSửa đổiHình bên là một trong biểu diễn hình ảnh của vật thị sau V:=1,2,3,4,5,6E:=Bản mẫu:1,2,1,5,2,3,2,5,3,4,4,5,Bản mẫu:4,6 Đôi khi, tin tức "đỉnh 1 được nối với đỉnh 2" được ký kết hiệu là 1 trong ~ 2. Trong kim chỉ nan phạm trù (category theory) một phạm trù rất có thể được xem như là một nhiều đồ thị được đặt theo hướng với các đối tượng người tiêu dùng là những đỉnh và những morphism là các cạnh tất cả hướng. Lúc đó, các hàm tử (functor) giữa những phạm trù là một trong những (nhưng không tuyệt nhất thiết vớ cả) digraph morphism.Trong Khoa học máy vi tính đồ thị có hướng được dùng để làm biểu diễn các ô-tô-mát hữu hạn (finite state machine) cùng nhiều cấu trúc rời rạc khác.Một quan liêu hệ đôi (binary relation) R trên tập X là một trong những đơn đồ gia dụng thị tất cả hướng. Nhì đỉnh x,y của X được nối với nhau bởi một cung nếu xRy.Các dạng vật thị quan lại trọngSửa đổiTrong một đồ gia dụng thị rất đầy đủ mỗi cặp đỉnh phần đông được nối với nhau bởi một cạnh, nghĩa là thứ thị chứa toàn bộ các cạnh tất cả thể.Một thứ thị phẳng rất có thể được vẽ xung quanh phẳng sao cho không tồn tại hai cạnh nào cắt nhau.Cây là 1 đồ thị liên thông không có chu trình.Đồ thị nhị phía (Bipartite graph)Đồ thị tuyệt vời và hoàn hảo nhất (Perfect graph)CographĐồ thị CayleyĐồ thị Petersen và các suy rộng của nóCác thao tác trên trang bị thịSửa đổiCó một trong những phép toán sản xuất đồ thị mới từ các đồ thị cũ. Các phép toán một ngôiSửa đổiĐồ thị đường (Line graph) (tạo trang bị thị mới bằng cách chuyển cạnh thành đỉnh và tạo những cạnh tương ứng)Đồ thị đối ngẫu (Dual graph) (tạo thiết bị thị mới từ 1 đồ thị phẳng bằng phương pháp tạo một đỉnh cho mỗi miền mặt phẳng và những cạnh được nối thân hai đỉnh tương ứng với nhì miền kề nhau)Đồ thị bù (Complement graph)Các phép toán nhị ngôiSửa đổiTích Đề-các của đồ thị (Cartesian product of graphs)Tích Ten-xơ của đồ gia dụng thị (Tensor product of graphs)Các suy rộngSửa đổiTrong vô cùng đồ thị (hypergraph), một cạnh có thể nối nhiều hơn thế hai đỉnh. Một thứ thị vô hướng có thể được coi là một phức đối kháng hình (simplicial complex) bao gồm các đơn hình một chiều (các cạnh) và những đơn hình 0 chiều (các đỉnh). Như vậy, nhiều hình là suy rộng lớn của đồ dùng thị vị chúng cho phép các solo hình nhiều chiều hơn. Mỗi thứ thị phần nhiều cho một matroid, tuy vậy nói chung, quan yếu tạo lại đồ thị trường đoản cú matroid của nó, vì đó, matroid không phải là suy rộng lớn của thứ thị. Trong kim chỉ nan mô hình (model theory), một thiết bị thị chỉ là một trong những cấu trúc. Nhưng khi đó, không tồn tại giới hạn về số cạnh: nó rất có thể là một số đếm bất kỳ. |