Bài này chỉ viết về những định nghĩa cơ bản. Để gọi rộng hơn, xin xem lý thuyết đồ thị. Về chân thành và ý nghĩa biểu diễn hàm số bên trên hệ tọa độ, xem trang bị thị hàm số.

Bạn đang xem: Trong toán học là gì


Trong toán học với tin học, đồ thị là đối tượng người dùng nghiên cứu giúp cơ bạn dạng của kim chỉ nan đồ thị. Một phương pháp không thiết yếu thức, đồ gia 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, thứ thị được vẽ bên dưới dạng một tập các điểm (đỉnh, nút) nối cùng nhau bởi các đoạn trực tiếp (cạnh). Tùy theo ứng dụng mà một trong những cạnh 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ục

Các định nghĩaSửa đổi

Trong những tài liệu, những định nghĩa trong kim chỉ nan đồ thị được phân phát biểu theo không ít kiểu. Dưới đó là kiểu truyền thống 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à 1 trong những cặp không tồn tại thứ từ bỏ (unordered pair) G:=(V, E), vào đó

V, tập các đỉnh hoặc nút,E, tập các cặp không máy tự chứa những đỉnh phân biệt, được hotline là cạnh. Hai đỉnh thuộc một cạnh được điện thoại tư vấn là những đỉnh đầu cuối của cạnh đó.

Trong những tài liệu, tập những cạnh bao gồm cả những cặp đỉnh không phân biệt, những cạnh này được hotline là các khuyên. V (và E) hay là các tập hữu hạn, phần nhiều các kết quả nghiên cứu vãn đã biết không đúng (hoặc khác) khi vận dụng cho đồ thị vô hạn (infinite graph) bởi nhiều luận cứ không dùng được vào trường vừa lòng vô hạn.

Đồ thị bao gồm hướngSửa đổi


*

Đồ thị có hướng G là một trong cặp bao gồm thứ trường đoản cú G:=(V, A), vào đó


V, tập những đỉnh hoặc nút,A, tập các cặp gồm thứ tự chứa các đỉnh, được call là những cạnh có hướng hoặc cung. Một cạnh e = (x, y) được xem như là có phía từ x tới y; x được hotline là điểm đầu/gốc cùng y được gọi là điểm cuối/ngọn của cạnh.

Đơn đồ dùng thị cùng Đa đồ vật thịSửa đổi

Đơn đồ vật thị là đồ thị mà không tồn tại khuyên và không tồn tại cạnh tuy nhiên song.

Đa đồ gia dụng thị là vật dụng thị nhưng mà không thỏa mãn nhu cầu đơn vật thị.

Đa vật thị gồm hướng là một đồ thị bao gồm hướng, trong đó, nếu như x và y là hai đỉnh thì thiết bị thị được phép bao gồm cả hai cung (x, y) cùng (y, x).

Đơn đồ dùng thị bao gồm hướng (hoặc Đơn vật dụng thị gồm hướng) là một trong những đồ thị bao gồm hướng, vào đó, giả dụ x và y là hai đỉnh thì đồ vật thị chỉ được phép có tối nhiều một trong hai cung (x, y) hoặc (y, x).

Quiver hay được xem là một đồ gia dụng thị gồm hướng. Nhưng lại trong thực hành, nó là một trong những đồ thị có hướng với các không gian vector (vector space) đính với những đỉnh với các đổi khác tuyến tính đính với những cung.

Đồ thị lếu hợpSửa đổi

Đồ thị lếu láo hợp G là 1 trong những bộ bố có sản phẩm công nghệ tự G:= (V,E,A) cùng với V, E và A được định nghĩa như trên.

Các định nghĩa khácSửa đổi

Như vẫn được định nghĩa ở trên, các cạnh của đồ thị vô hướng gồm hai đầu là nhì đỉnh phân biệt; E cùng A là những tập đúng theo (với các phần tử phân biệt). Nhiều vận dụng cần những khái niệm rộng lớn hơn, và các thuật ngữ cũng khác nhau.


Một khuyên (loop) là 1 trong cạnh (vô phía hoặc tất cả hướng) nối xuất phát điểm từ 1 đỉnh về bao gồm nó; phong cách cạnh này có được gật đầu hay ko là tùy sinh sống ứng dụng. Trong văn cảnh này, một cạnh nối nhị đỉnh minh bạch được gọi là một liên kết (link).

Đôi khi, E với A được phép là những đa tập thích hợp (multiset), khi đó giữa nhị đỉnh bao gồm thể có nhiều hơn một cạnh. Có thể có thể chấp nhận được giữa nhị đỉnh có nhiều cạnh bằng cách cho E là 1 tập hợp độc lập với V, và khẳng định các điểm đầu của mỗi cạnh bởi một quan hệ liên thuộc (incidence relation) thân V với E. Đối với đồ dùng thị có hướng, ta áp dụng tương tự cho tập hợp cạnh có hướng A, mặc dù nhiên, phải gồm hai dục tình liên thuộc, một mang lại đỉnh đầu và một mang lại đỉnh cuối của từng cung.

Trong những sách, tùy thuộc vào ý của người sáng tác hoặc theo yêu mong của công ty đề rõ ràng mà từ bỏ "đồ thị" có thể hàm ý cho phép hoặc không chất nhận được khuyên hay nhiều cạnh. Nếu đồ thị không có thể chấp nhận được đa cạnh (và không được cho phép khuyên nếu như là thiết bị thị gồm hướng), trang bị thị được call là đơn trang bị thị. Khía cạnh khác, nếu chất nhận được đa cạnh (và đôi khi cả khuyên), vật dụng thị được hotline là đa trang bị thị. Đôi khi, từ bỏ giả vật dụng thị (pseudograph) còn được dùng để làm hàm ý cả đa cạnh cùng khuyên đa số được phép. Trong các trường hợp quánh biệt, thậm chí là còn cần đến những cạnh chỉ có một đỉnh, được gọi là nửa cạnh (halfedge), hoặc không tồn tại đỉnh nào, (cạnh rời). Xem lấy một ví dụ tại signed graph.

Hai cạnh của một đồ vật thị được xem như là kề nhau ví như chúng tất cả chung một đỉnh. Tương tự, hai đỉnh được xem như là kề nhau nếu chúng được nối cùng với nhau vày một cạnh. Một cạnh với đỉnh nằm trong cạnh đó được coi là liên thuộc với nhau.

Đồ thị chỉ có một đỉnh và không tồn tại 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ị có trọng số, từng cạnh được thêm với một giá trị nào đó, được gọi 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; những đồ thị bởi thế được dùng trong vô số ngữ cảnh, chẳng hạn trong các bài toán buổi tối ưu hóa lối đi như bài toán người chào bán hàng.

Ví dụSửa đổi



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, thông tin "đỉ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 là một nhiều đồ thị có hướng với các đối tượng người tiêu dùng là các đỉnh và những morphism là các cạnh 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 độc nhất thiết vớ cả) digraph morphism.Trong Khoa học máy tính xách tay đồ thị có hướng được dùng để biểu diễn các ô-tô-mát hữu hạn (finite state machine) và nhiều cấu trúc rời rộc rạc khác.Một quan liêu hệ song (binary relation) R bên trên tập X là 1 trong đơn vật thị tất cả hướng. Hai đỉnh x,y của X được nối cùng với nhau vày một cung ví như xRy.

Các dạng đồ gia dụng thị quan lại trọngSửa đổi

Trong một vật dụng thị không thiếu mỗi cặp đỉnh những được nối cùng với nhau bằng một cạnh, nghĩa là trang bị thị chứa toàn bộ các cạnh gồm thể.Một đồ gia dụng thị phẳng hoàn toàn có thể được vẽ cùng bề mặt phẳng sao cho không tồn tại hai cạnh nào cắt nhau.Cây là 1 trong đồ thị liên thông không tồn tại chu trình.Đồ thị nhì phía (Bipartite graph)Đồ thị hoàn hảo (Perfect graph)CographĐồ thị CayleyĐồ thị Petersen và các suy rộng lớn của nó

Các làm việc trên vật dụng thịSửa đổi

Có một trong những phép toán tạo đồ thị mới từ những đồ 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 phương pháp chuyển cạnh thành đỉnh và tạo các cạnh tương ứng)Đồ thị đối ngẫu (Dual graph) (tạo vật dụng thị mới từ 1 đồ thị phẳng bằng cách tạo một đỉnh cho từng miền mặt phẳng và các cạnh được nối thân hai đỉnh tương ứng với hai miền kề nhau)Đồ thị bù (Complement graph)

Các phép toán nhì ngôiSửa đổi

Tích Đề-các của thiết bị thị (Cartesian product of graphs)Tích Ten-xơ của trang bị thị (Tensor product of graphs)

Các suy rộngSửa đổi

Trong rất đồ thị (hypergraph), một cạnh rất có thể nối nhiều hơn thế nữa hai đỉnh.

Một đồ vật thị vô hướng hoàn toàn có thể được xem như là một phức đối kháng hình (simplicial complex) bao hàm các đối kháng hình 1 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 của đồ dùng thị vì chưng chúng chất nhận được các đối kháng hình nhiều chiều hơn.

Mỗi vật dụng thị số đông cho một matroid, nhưng mà nói chung, tất yêu tạo lại trang bị thị từ matroid của nó, vì đó, matroid chưa hẳn là suy rộng lớn của thứ thị.

Trong kim chỉ nan mô hình (model theory), một trang bị thị chỉ là 1 trong những cấu trúc. Mà lại khi đó, không tồn tại giới hạn về số cạnh: nó rất có thể là một số trong những đếm bất kỳ.

Xem thêm: Hướng Dẫn Giải Bài Tập Hệ Thức Lượng Trong Tam Giác Vuông, Chuyên Đề Hệ Thức Lượng Trong Tam Giác Vuông

Đa giácBài toán lát gạch men (Tiling)Thuật ngữ lý thuyết đồ thịDanh sách những chủ đề định hướng đồ thịĐồ thị (cấu trúc dữ liệu)Các ấn phẩm triết lý đồ thị quan trọngWikimedia Commons có thêm hình hình ảnh và phương tiện đi lại truyền download về Đồ thị (lý thuyết đồ gia dụng thị).

Tham khảoSửa đổi