:Bài này chỉ viết về các định nghĩa cơ bản. Để hiểu rộng hơn, xin xem lý thuyết đồ thị. Về ý nghĩa biểu diễn hàm số trên hệ tọa độ, xem đồ thị hàm số.
phải|frame|Một đồ thị vô hướng với 6 đỉnh (nút) và 7 cạnh.
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.
Các định nghĩa
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
phải**Đồ thị vô hướng** hoặc **đồ thị** _G_ là một cặp không có thứ tự _(unordered pair)_ _G_:=(_V_, _E_), trong đó
* _V_, tập các **đỉnh** hoặc **nút**,
* _E_, tập các cặp không thứ tự chứa các đỉnh phân biệt, được gọi là **cạnh**. Hai đỉnh thuộc một cạnh được gọi là các **đỉnh** đầu cuối của cạnh đó.
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
phải**Đồ thị có hướng** _G_ là một cặp có thứ tự _G_:=(_V_, _A_), trong đó
* _V_, tập các **đỉnh** hoặc **nút**,
* _A_, tập các cặp có thứ tự chứa các đỉnh, được gọi là các **cạnh có hướng** hoặc **cung**. Một cạnh _e_ = (_x_, _y_) được coi 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 đồ thị và Đa đồ thị
**Đơ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_).
**Quiver** thường được coi là một đồ thị có hướng. Nhưng trong thực hành, nó là một đồ thị có hướng với các không gian vector (_vector space_) gắn với các đỉnh và các biến đổi tuyến tính gắn với các cung.
Đồ thị hỗn hợp
**Đồ thị hỗn hợp** _G_ là một bộ ba có thứ tự _G_:= (_V_,_E_,_A_) với _V_, _E_ và _A_ được định nghĩa như trên.
Các định nghĩa khác
Như đã được định nghĩa ở trên, các cạnh của đồ thị vô hướng có hai đầu là hai đỉnh phân biệt; E và A là các tập hợp (với các phần tử phân biệt). Nhiều ứng dụng cần các khái niệm rộng hơn, và các thuật ngữ cũng khác nhau.
Một **khuyên** (_loop_) là một cạnh (vô hướng hoặc có hướng) nối từ một đỉnh về chính nó; Kiểu cạnh này có được chấp nhận hay không là tùy ở ứng dụng. Trong ngữ cảnh này, một cạnh nối hai đỉnh phân biệt được gọi là một **liên kết** (_link_).
Đôi khi, E và A được phép là các đa tập hợp (multiset), khi đó giữa hai đỉnh có thể có nhiều hơn một cạnh. Có thể cho phép giữa hai đỉnh có nhiều cạnh bằng cách cho E là một tập hợp độc lập với V, và xác định các điểm đầu của mỗi cạnh bằng một quan hệ liên thuộc (incidence relation) giữa V và E. Đối với đồ thị có hướng, ta áp dụng tương tự cho tập hợp cạnh có hướng A, tuy nhiên, phải có hai quan hệ liên thuộc, một cho đỉnh đầu và một cho đỉnh cuối của mỗi cung.
Trong các sách, tùy theo ý của tác giả hoặc theo yêu cầu của chủ đề cụ thể mà từ "đồ thị" có thể hàm ý cho phép hoặc không cho phép khuyên hay đa cạnh. Nếu đồ thị không cho phép đa cạnh (và không cho phép khuyên nếu là đồ thị có hướng), đồ thị được gọi là **đơn đồ thị**. Mặt khác, nếu cho phép đa cạnh (và đôi khi cả khuyên), đồ thị được gọi là **đa đồ thị**. Đôi khi, từ **giả đồ thị** (pseudograph) còn được dùng để hàm ý cả đa cạnh và khuyên đều được phép.
Trong các trường hợp đặc biệt, thậm chí còn cần đến các cạnh chỉ có một đỉnh, được gọi là **nửa cạnh** (_halfedge_), hoặc không có đỉnh nào, (**cạnh rời**). Xem ví dụ tại signed graph.
Các định nghĩa khác
:Xem thêm thuật ngữ lý thuyết đồ thị.
Hai cạnh của một đồ thị được coi là kề nhau nếu chúng có chung một đỉnh. Tương tự, hai đỉnh được coi là kề nhau nếu chúng được nối với nhau bởi một cạnh. Một cạnh và đỉnh nằm trên cạnh đó được coi là liên thuộc với nhau.
Đồ thị chỉ có một đỉnh và không có cạnh nào được gọi là đồ thị tầm 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ố, mỗi cạnh được gắn 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 theo ứng dụng; các đồ thị như vậy được dùng trong nhiều 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 bán hàng.
Ví dụ
Tập tin:6n-graf.svg
Hình bên là một biểu diễn đồ họa của đồ thị sau
V:={1,2,3,4,5,6}
E:={1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}
Đôi khi, thông tin "đỉnh 1 được nối với đỉnh 2" được ký hiệu là 1 ~ 2.
Trong lý thuyết phạm trù (category theory) một phạm trù có thể được coi là một đa đồ thị có hướng với các đối tượng là các đỉnh và các morphism là các cạnh có hướng. Khi đó, các hàm tử (functor) giữa các phạm trù là một số (nhưng không nhất thiết tất cả) digraph morphism.
Trong Khoa học máy tính đồ 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 khác.
*Một quan hệ đôi (binary relation) R trên tập X là một đơn đồ thị có hướng. Hai đỉnh x,y của X được nối với nhau bởi một cung nếu xRy.
Các dạng đồ thị quan trọng
- Trong một đồ thị đầy đủ mỗi cặp đỉnh đều được nối với nhau bằng một cạnh, nghĩa là đồ thị chứa tất cả các cạnh có thể.
- Một đồ thị phẳng có thể được vẽ trên mặt phẳng sao cho không có hai cạnh nào cắt nhau.
- Cây là một đồ thị liên thông không có chu trình.
- Đồ thị hai phía (Bipartite graph)
- Đồ thị hoàn hảo (Perfect graph)
- Cograph
- Đồ thị Cayley
- Đồ thị Petersen và các suy rộng của nó
Các thao tác trên đồ thị
Có một số phép toán tạo đồ thị mới từ các đồ thị cũ.
Các phép toán một ngôi
- Đồ thị đường (Line graph) (tạo đồ thị mới bằng cách 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 đồ thị mới từ một đồ thị phẳng bằng cách tạo một đỉnh cho mỗi miền mặt phẳng và các cạnh được nối giữa hai đỉnh tương ứng với hai miền kề nhau)
- Đồ thị bù (Complement graph)
Các phép toán hai ngôi
- Tích Đề-các của đồ thị (Cartesian product of graphs)
- Tích Ten-xơ của đồ thị (Tensor product of graphs)
Các suy rộng
Trong siêu đồ thị (hypergraph), một cạnh có thể nối nhiều hơn hai đỉnh.
Một đồ thị vô hướng có thể được coi là một phức đơn hình (simplicial complex) bao gồm các đơn hình 1 chiều (các cạnh) và các đơn hình 0 chiều (các đỉnh). Như vậy, đa hình là suy rộng của đồ thị do chúng cho phép các đơn hình nhiều chiều hơn.
Mỗi đồ thị đều cho một matroid, nhưng nói chung, không thể tạo lại đồ thị từ matroid của nó, do đó, matroid không phải là suy rộng của đồ thị.
Trong lý thuyết mô hình (model theory), một đồ thị chỉ là một cấu trúc. Nhưng khi đó, không có giới hạn về số cạnh: nó có thể là một số đếm bất kỳ.
👁️
2 | 🔗 | 💖 | ✨ | 🌍 | ⌚
nhỏ|phải|Hình vẽ một đồ thị có 6 đỉnh và 7 cạnh Trong toán học và tin học, **lý thuyết đồ thị** (tiếng Anh: _graph theory_) nghiên cứu các tính chất của đồ thị. Một cách
phải|nhỏ|Ví dụ về bản đồ bốn màu **Định lý bốn màu** (còn gọi là _định lý bản đồ bốn màu_) phát biểu rằng đối với bất kỳ mặt phẳng nào được chia thành các vùng
:_Bài này chỉ viết về các định nghĩa cơ bản. Để hiểu rộng hơn, xin xem lý thuyết đồ thị. Về ý nghĩa biểu diễn hàm số trên hệ tọa độ, xem đồ thị hàm
Lưu ý: Danh sách **thuật ngữ lý thuyết đồ thị** này chỉ là điểm khởi đầu cho những người mới nhập môn làm quen với một số thuật ngữ và khái niệm cơ bản. Bài
**Đồ thị Turán** là một đồ thị nhiều phía đầy đủ tạo thành bằng cách chia đỉnh thành tập con, với kích thước gần nhau nhất có thể, và nối hai đỉnh bằng một cạnh
Trong lý thuyết đồ thị, một **đồ thị phẳng** là một đồ thị có thể được nhúng vào mặt phẳng, tức là có thể được vẽ trên mặt phẳng sao cho các cạnh chỉ gặp
Trong lý thuyết đồ thị, tồn tại một **phép đồng phôi** (tiếng Anh: _homeomorphism_, còn gọi là **phép biến đổi tôpô**) giữa hai đồ thị _G_ và _G_′nếu tồn tại một đồ thị _H_ sao
:_Bài này viết về thuật ngữ "bậc" dùng trong lý thuyết đồ thị. Mời xem các bài bậc (toán học) hoặc bậc để đọc về các nghĩa khác._ Trong Lý thuyết đồ thị, **bậc** của
phải|khung|Một cây có dán nhãn với 6 đỉnh và 5 cạnh **Cây** là khái niệm quan trọng trong lý thuyết đồ thị, cấu trúc dữ liệu và giải thuật. Cây là một đồ thị mà
Trong lý thuyết đồ thị, một **lát cắt** là một cách phân chia tập hợp các đỉnh của một đồ thị thành hai tập hợp con không giao nhau. **Tập hợp cắt** của lát cắt
Trong lý thuyết độ phức tạp tính toán (_Computational complexity theory_), **Đồ thị con đẳng cấu** là một bài toán quyết định (_decision problem_) thuộc loại NP-đầy đủ (_NP-complete_). Phát biểu của bài toán quyết
nhỏ|Đồ thị ngẫu nhiên có hướng, 20 nút, xác suất p = 0,1, trường hợp 1. Trong toán học, một **đồ thị ngẫu nhiên** là một đồ thị được sinh ra bởi một quá trình
Một đường đi trong G là một dãy luân phiên các đỉnh và cạnh: ( là đỉnh và là cạnh). Trong đồ thị thỏa mãn điều
phải|Một đồ thị đơn có chu trình. Trong lý thuyết đồ thị, **chu trình** trong đồ thị là một dây chuyền đóng. Đồ thị chỉ gồm một chu trình với n đỉnh được gọi là
phải|Một đồ thị đầy đủ K5 (5 đỉnh). Nếu đây là một đồ thị con thì tập đỉnh của nó sẽ tạo nên một clique kích thước 5. thumb|Đồ thị _G_ có: 23 clique 1
**Định lý năm màu** (còn gọi là _định lý bản đồ năm màu_): Mọi đồ thị phẳng (G) đều có số màu . Là một kết quả từ Lý thuyết đồ
Trong Lý thuyết đồ thị, **phép đồng cấu đồ thị** (tiếng Anh: _graph homomorphism_) là ánh xạ giữa hai đồ thị trong khi tôn trọng cấu trúc của chúng. Cụ thể hơn, nó ánh xạ
thumb|Ví dụ về đồ thị hai phía không có chu trình Trong Lý thuyết đồ thị, **đồ thị hai phía** (**đồ thị lưỡng phân** hay **đồ thị hai phần**) (tiếng Anh: bipartite graph) là một
Trong lý thuyết đồ thị, đồ thị **Petersen** là 1 đồ thị vô hướng với 10 đỉnh và 15 cạnh. Nó thường được sử dụng làm minh họa trong khi trình bày các lý thuyết
Trong lý thuyết đồ thị, **định lý Kirchhoff**, hay **định lý Kirchhoff cho ma trận và cây**, đặt tên theo Gustav Kirchhoff, là một định lý về số cây bao trùm của một đồ thị.
Trong lý thuyết đồ thị, **định lý Kuratowski**, được phát triển bởi nhà toán học người Ba Lan Kazimierz Kuratowski, là một đặc tính của đồ thị phẳng. ## Định lý 1 Đồ thị đủ
Trong lý thuyết đồ thị, có hai định lý được gọi là **định lý Dirac** (tiếng Anh: _Dirac's theorem_), cả hai đều được đặt theo tên nhà toán học Gabriel Andrew Dirac: :1. Cho _G_
Tính liên thông (connectivity) là một trong những tính chất quan trọng nhất của đồ thị nói riêng và lý thuyết đồ thị nói chung. ## Định Nghĩa Một đồ thị được gọi là liên
**Giả thuyết Kahn–Kalai**, hay còn gọi là **giả thuyết ngưỡng kì vọng**, là một giả thuyết trong nhánh lý thuyết đồ thị và cơ học thống kê, được đề xuất bởi Jeff Kahn và Gil
Trong lý thuyết đồ thị, một **đồ thị hai phía đầy đủ** (tiếng Anh: Complete bipartite graph hoặc biclique) là một dạng đồ thị hai phía đặc biệt, trong đó mỗi đỉnh của tập thứ
**Phép đẳng cấu đồ thị** (tiếng Anh: _graph isomorphism_) là một song ánh giữa các tập đỉnh của hai đồ thị và : : với tính chất rằng cặp đỉnh
Trong lý thuyết đồ thị, một **đồ thị chính quy**, còn gọi là **đồ thị đều** (tiếng Anh: _regular graph_) là một đồ thị trong đó mỗi đỉnh có số láng giềng bằng nhau, nghĩa
thumb|phải|[[Đồ thị Petersen là đồ thị cạnh đơn vị, nó có thể vẽ trong mặt phẳng với độ dài tất cả các cạnh đều bằng một.]] **Đồ thị cạnh đơn vị** (tiếng Anh: _unit distance
nhỏ|350x350px| Một trang trại đô thị ở [[Chicago ]] **Nông nghiệp** **đô thị** **, trồng trọt** **đô thị**, hoặc **làm vườn đô thị** là hoạt động trồng trọt, chế biến và phân phối thực phẩm
Trong Lý thuyết đồ thị, **đồ thị cánh bướm** (tiếng Anh: _butterfly graph_) hay còn gọi là **đồ thị hình nơ** (tiếng Anh: _bowtie graph_) là một đồ thị phẳng, có 5 đỉnh và 6
Trong lý thuyết đồ thị, **đồ thị bánh xe** (tiếng Anh: _wheel graph_) được tạo thành từ đồ thị chu trình bằng cách thêm 1 đỉnh và các cạnh nối đỉnh đó với
## Giới thiệu :Khi giải quyết nhiều bài toán lý thuyết đồ thị, ta luôn phải duyệt qua tất cả các đỉnh của đồ thị đó. Cho nên, cần có thuật toán duyệt toàn bộ
} ## Bối cảnh thực tế Bài toán tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị liên thông có nhiều ứng dụng thực tế như: * Bài toán chọn hành trình
Hình:Cycle Graphs.PNG| Các đồ thị chu trình . Trong lý thuyết đồ thị, **đồ thị chu trình** (tiếng Anh: _Cycle graph_) chính là chu trình đơn. Nó có hình dạng của đa
vừa|phải|Với _n_ bằng 5 Một đồ thị có e đỉnh, và có thể gán nhãn cho mỗi đỉnh với một số tự nhiên bất kỳ nằm giữa 0 và e sao cho: * mỗi đỉnh
thumb|Một đồ thị vô hướng với 3 đỉnh (vòng tròn màu xanh viền đen) và 3 cạnh. **Đồ thị vô hướng** là một đồ thị mà các cạnh của nó không có hướng. Mỗi cạnh
## Đồ thị tăng luồng * Giả sử f là một luồng trên mạng G = (V, E). Từ mạng G = (V, E) ta xây dựng đồ thị có trọng số trên cung Gf
Trong toán học, **đa đồ thị** (_multigraph_ hay _pseudograph_) là một đồ thị được phép có nhiều cạnh (còn gọi là cạnh song song), nghĩa là các cạnh có cùng một nút kết thúc. Do
**Đồ thị đầy đủ** n đỉnh (tiếng Anh: _complete graph_), ký hiệu là (chữ _K_ lấy từ tiếng Đức _komplett_), là đồ thị đơn vô hướng mà giữa hai đỉnh bất kì của nó
phải|27 vùng đô thị có ít nhất 10 triệu dân. Câu hỏi "các thành phố nào là các thành phố lớn nhất thế giới" là một câu hỏi phức tạp vì không có một câu
**Lý thuyết độ phức tạp tính toán** (tiếng Anh: _computational complexity theory_) là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại
**Các cuộc chống đối thuyết tiến hóa** bắt đầu kể từ khi các ý tưởng về sự tiến hóa gây được sự chú ý vào thế kỷ 19. Ban đầu, vào năm 1859, khi Charles
nhỏ|[[Trường Trung học phổ thông Nguyễn Thị Minh Khai, một địa điểm gắn liền với truyền thuyết đô thị Việt Nam về hồn ma áo tím.]] **Truyền thuyết đô thị Việt Nam** là những câu
thumb|Dụng cụ cho bài thi thực hành, tại kỳ thi Olympic Vật lý Quốc tế năm 1996 ở Oslo, Na Uy. **Olympic Vật lý Quốc tế** (tiếng Anh: _International Physics Olympiad_, viết tắt **IPhO**) là
là một bộ phim điện ảnh hoạt hình Nhật Bản thuộc thể loại lãng mạn – khoa học viễn tưởng – chính kịch ra mắt vào năm 2022, dựa trên cuốn light novel cùng tên
**Truyền thuyết đô thị Nhật Bản** là những câu chuyện được lưu truyền trong dân gian Nhật Bản và được cho là có thật, dù chưa có bằng chứng xác thực. Những truyền thuyết đô
Trong thuyết âm mưu UFO, **"Hangar 18"** là tên gọi được đặt cho một tòa nhà nghi có chứa các mảnh vỡ UFO hoặc thi thể người ngoài hành tinh. Cái tên này do nhà
**Vạn Lý Trường Thành** (), gọi tắt là **Trường Thành**, là tên gọi chung cho nhiều thành lũy kéo dài hàng ngàn cây số từ Đông sang Tây, được xây dựng bằng đất và đá
**Trường Trung học Phổ thông Nguyễn Thị Minh Khai** (Tên cũ: **Trường nữ Gia Long**, **Trường nữ sinh Áo Tím**; tên khác: **Miki**) là một trường trung học phổ thông công lập ở Thành phố
thế=|nhỏ|Về cơ bản, một độ đo có tính chấn của một [[hàm số đơn điệu|hàm đơn điệu theo nghĩa, nếu là tập con của khi này độ đo của nhỏ hơn hoặc