Thuật ngữ lý thuyết đồ thị

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 này không trình bày các định nghĩa chính thức của các khái niệm và thuật ngữ này.

==B==
- Bậc ("degree" hoặc "valency")

- Bất biến đồ thị ("graph invariant")

==C==
- Cạnh(Edge): Cạnh nối đỉnh "x" với đỉnh "y" là một tập gồm hai phần tử {"x","y"}, thường được vẽ dưới dạng một "đoạn thẳng" nối hai đỉnh. Cạnh nối hai đỉnh "x" và "y" được ký hiệu là "xy" (không phải "x"⋅"y"). Tập cạnh của "G" thường được ký hiệu là "E"("G"), hoặc "E" nếu không có nguy cơ hiểu nhầm.
- Cạnh có hướng là một cặp đỉnh có thứ tự. Trong mỗi cặp có thứ tự đó, đỉnh thứ nhất được gọi là đỉnh đầu, đỉnh thứ hai là đỉnh cuối. Cạnh vô hướng không quan tâm đến hướng và coi hai đỉnh như nhau.
- Cạnh lá: Cạnh nối với một đỉnh lá.
- Cạnh cắt: xem Cầu.
- Cạnh kề nhau : Hai cạnh của một đồ thị được xem là kề nhau nếu chúng có một đỉnh chung.
- Cặp ghép: ("matching"): một cặp ghép "M" của đồ thị G = (V,E) là một tập các cạnh đôi một không kề nhau của G.
- Cặp ghép hoàn hảo ("perfect matching"): là cặp ghép phủ tất cả các đỉnh của đồ thị. Nghĩa là mỗi đỉnh của đồ thị đều liên thuộc với đúng một cạnh của cặp ghép.
- Cặp ghép lớn nhất, Cặp ghép tối đa: là cặp ghép chứa nhiều cạnh nhất có thể. Có thể có nhiều cặp ghép tối đa.
- Cấp ("order") của một đồ thị là số đỉnh của nó, nghĩa là |"V"("G")|.
- Cầu: là một cạnh mà nếu loại bỏ nó thì đồ thị tăng số thành phần liên thông.
- Cây: là một đồ thị đơn liên thông phi chu trình(không có chu trình).
- Cây bao trùm(cây khung): là một đồ thị con bao trùm có dạng cây. Chỉ có đồ thị liên thông mới có cây bao trùm.
- Cây (có gốc): thường được coi như các "đồ thị đơn có hướng phi chu trình" với các cung hướng từ phía gốc ra phía lá. Với mỗi cung, đỉnh tại gốc cung được gọi là "đỉnh cha" hoặc cha, các đỉnh tại điểm cuối của cung được gọi là đỉnh con hoặc "con" của đỉnh tại gốc cung.
- Cây con: một "cây con" của đồ thị "G" là một đồ thị con có dạng cây.
- Cây "k"-ary:(ví dụ: nhị phân, tam phân...) là cây có gốc mà mỗi đỉnh trong đều có không quá "k" "con".

- Chỉ số clique: "Chỉ số clique" ω("G") của đồ thị "G" là bậc của đồ thị con đầy đủ lớn nhất của "G".
- Chỉ số độc lập: "Chỉ số độc lập" của đồ thị "G", ký hiệu α("G"), là kích thước của tập độc lập lớn nhất của "G".
- Chu trình trong đồ thị: là một đường đi đóng trong đồ thị. Đồ thị chỉ gồm một "chu trình" với "n" đỉnh được gọi là đồ thị vòng, ký hiệu "C",
- Chu trình bao trùm: là cách gọi khác của chu trình Hamilton.
- Chu trình chẵn: là chu trình có độ dài chẵn.
- Chu trình có hướng: là một chu trình đơn mà mọi cung trong đó đều cùng hướng, nghĩa là mọi đỉnh đều có bậc trong và bậc ngoài bằng 1. Có thể gọi đơn giản là "chu trình" khi ngữ cảnh rõ ràng.
- Chu trình đơn: là chu trình đi qua mỗi đỉnh không quá một lần. Trong đồ thị ở hình trên, (1, 5, 2, 1) là một chu trình đơn. Nếu không chỉ rõ, "chu trình" thường được hiểu là một "chu trình đơn".
- Chu trình Euler: là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần.
- Chu trình lẻ: là chu trình có độ dài lẻ.
- Chu vi nhỏ ("girth"): Chu vi nhỏ của một đồ thị là độ dài của chu trình đơn ngắn nhất của đồ thị.
- Chu vi lớn ("circumference"): Chu vi lớn của một đồ thị là độ dài của chu trình đơn dài nhất của đồ thị. Đối với đồ thị không có chu trình, chu vi lớn và chu vi nhỏ được định nghĩa bằng giá trị vô cùng ∞.
- Chuỗi bậc ("degree sequence"): là danh sách các bậc của một đồ thị sắp xếp theo thứ tự giảm dần. (ví dụ, "d" ≥ "d" ≥ … ≥ "d"). Một chuỗi giảm dần các số tự nhiên được coi là hiện thực được ("realizable") nếu nó là chuỗi bậc của một đồ thị nào đó.
- Cung: là "cạnh có hướng".

==D==
- Dẫn xuất ("induced")

==Đ==
- Đẳng cấu

- Đỉnh: Xem Đồ thị. Đỉnh được vẽ dưới dạng một "nút" hoặc một "điểm". Tập đỉnh của đồ thị "G" thường được ký hiệu là "V"("G"), hoặc "V" khi không có nguy cơ hiểu nhầm.
- Đỉnh cha: Xem Cây (có gốc)
- Đỉnh con: Xem Cây (có gốc)
- Đỉnh cắt ("cut vertex"): là một đỉnh mà nếu loại bỏ nó thì đồ thị tăng số thành phần liên thông.
- Đỉnh gốc: là một đỉnh đặc biệt của cây có gốc. Trong trường hợp này, cây là đồ thị có hướng, "đỉnh gốc" là đỉnh duy nhất có bậc trong bằng 0.
- Đỉnh lá: Đỉnh có bậc 1, còn được gọi là lá. Thường dùng cho cây có gốc, khi đó lá là đỉnh không có con.
- Đỉnh phát ("source"): là đỉnh có bậc trong bằng 0.
- Đỉnh thu ("sink"): là đỉnh có bậc ngoài bằng 0.
- Đỉnh trong ("internal vertex"): Đỉnh không phải là đỉnh lá.
- Đồ thị: Gồm một tập các đỉnh được nối với nhau bằng các cạnh. Xem chi tiết tại Đồ thị (toán học). Nếu không không được chỉ rõ trong ngữ cảnh, "đồ thị" được hiểu là đồ thị đơn.
- Đa đồ thị: Đồ thị có đa cạnh nhưng không có khuyên. Có tài liệu quy định là: đồ thị có đa cạnh và có khuyên.
- Đồ thị cha: Một "đồ thị cha" của "G" là một đồ thị chứa "G" với danh nghĩa một đồ thị con. Ta nói rằng đồ thị "G" "chứa" đồ thị "H" nếu có một đồ thị con nào đó của "G" chính là "H" hoặc đẳng cấu với "H" (tùy theo yêu cầu của hoàn cảnh).
- Đồ thị chính quy: là đồ thị có bậc của tất cả các đỉnh bằng nhau.
- Đồ thị có hướng
- Đồ thị có trọng số: Trong đồ thị có trọng số, mỗi cạnh được gắn nhãn là một số, số này được gọi là trọng số của đỉnh. Nói cách khác, đồ thị có trọng số là một đồ thị cùng với một ánh xạ từ tập các cạnh vào tập số thực. Khi không chỉ rõ, một đồ thị luôn được coi là đồ thị không có trọng số.
- Đồ thị con: Một "đồ thị con" của đồ thị "G" là một đồ thị mà tập cạnh và tập đỉnh của nó là các tập con của các thành phần tướng ứng của "G".
- Đồ thị con bao trùm ("spanning subgraph"): Đồ thị con "H" là một "đồ thị con bao trùm" của đồ thị "G" nếu tập đỉnh của "H" trùng với tập đỉnh của "G". Ta nói rằng "H" bao trùm "G".
- Đồ thị đầy đủ: "Đồ thị đầy đủ" bậc "n", ký hiệu "K", là một đồ thị đơn gồm "n" đỉnh trong đó hai đỉnh bất kỳ đều được nối với nhau bởi một cạnh. Có tất cả "n"("n"-1)/2 cạnh. Đồ thị ví dụ không phải đồ thị đầy đủ.
- Đồ thị đơn: là đồ thị không có đa cạnh và không có khuyên.
- Đồ thị Euler có hướng: là một đồ thị có hướng mà mỗi đỉnh đều có bậc trong bằng bậc ngoài.
- Đồ thị hai phía: là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.
- Đồ thị hữu hạn: là đồ thị có hữu hạn cạnh và hữu hạn đỉnh. Nếu không được chỉ rõ tính chất, một đồ thị thường được hiểu là hữu hạn.
- Đồ thị hữu hạn địa phương: là đồ thị vô hạn trong đó mỗi cạnh đều có bậc hữu hạn.
- Đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng Euclid sao cho không có hai cạnh nào cắt nhau. Đồ thị ví dụ là đồ thị phẳng.
- Đồ thị phi chu trình: là đồ thị không có chu trình. Một đồ thị có hướng là phi chu trình nếu nó không chứa chu trình có hướng.
- Đồ thị phổ dụng (universal graph): Đồ thị phổ dụng của một lớp đồ thị K là một đồ thị đơn nhỏ nhất mà mọi đồ thị là phần tử của K đều là đồ thị con của nó.
- Đồ thị rỗng: là đồ thị không có cạnh và không có đỉnh. Hoặc, nó là một đồ thị không có cạnh nhưng có một số đỉnh formula_1 bất kỳ, khi đó, nó được gọi là đồ thị rỗng formula_1 đỉnh. (Không có sự thống nhất giữa các tài liệu).
- Đồ thị vòng: là đồ thị chứa một chu trình duy nhất đi qua tất cả các đỉnh, mỗi đỉnh đều có bậc đúng bằng 2.
- Đồ thị vô hạn: là đồ thị có vô hạn cạnh hoặc vô hạn đỉnh hoặc cả hai.
- Đồ thị vô hướng: là đồ thị gồm toàn các cạnh không có hướng.
- Độ dài

- Độc lập

- Đồng cấu

- Đường đi ("walk"/"path"): là một chuỗi luân phiên giữa đỉnh và cạnh, bắt đầu và kết thúc bởi một đỉnh. Trong đó, mỗi đỉnh là đỉnh đầu cuối của hai cạnh đứng liền trước và liền sau trong chuỗi, các đỉnh đứng liền trước và liền sau một cạnh là các đỉnh đầu cuối của cạnh đó. Khi có hai cạnh giống nhau trên chuỗi có thể loại bỏ bớt các cạnh trùng nhau, sao cho không có cạnh nào của đồ thị cómặt quá một lần trên đường đi. Một đường đi được coi là đónghay một "chu trình" nếu đỉnh đầu và đỉnh cuối trùng nhau, được coi là mở nếu đỉnh đầu và đỉnh cuối khác nhau. Đường đi qua "n" đỉnh được ký hiệu là "P".
- Đường đi có hướng: là một đường đi đơn trong đó mọi cung đều theo cùng một hướng, nghĩa là mọi đỉnh trên đó đều có bậc trong và bậc ngoài bằng 1. Trong đồ thị có hướng, đỉnh "v" được coi là đến được từ đỉnh "u" nếu có một đường đi có hướng xuất phát từ "u" và kết thúc tại "v". Có thể gọi đơn giản là "đường đi" khi ngữ cảnh rõ ràng.
- Đường đi đơn:là đường đi trong đó mỗi đỉnh chỉ được đi qua nhiều nhất một lần.
- Đường đi Euler ("Eulerian path"): là đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần. Đồ thị ví dụ không có đường đi Euler.
- Đường đi Hamilton ("Hamiltonian path"): là đường đi đơn qua tất cả các đỉnh trong đồ thị. Đồ thị ví dụ có đường đi Hamilton.

==G==
- Gắn nhãn đồ thị ("graph labelling")

- Gốc

==K==
- Kề
Hai đỉnh "u" và "v" được coi là "kề" nhau, ký hiệu "u" ↓ "v", nếu có một cạnh nối chúng. Trong đồ thị ví dụ, các đỉnh 1 và 2 kề nhau, nhưng các đỉnh 2 và 4 không kề.

- Khoảng cách

- Khuyên ("loop")

- Kích thước của đồ thị

==L==
- Lá

- Lát cắt đỉnh

- Lát cắt cạnh

- Liên thông

- Lưới (còn gọi là mạng, mạng lưới)

==M==
- Ma trận kề

==N==
- Nhân ("kernel")

- Nhúng: ("embedding")
- Phép nhúng thực hiện trên formula_3 (cho kết quả là đồ thị formula_4) là một hàm đơn ánh từ formula_5 tới formula_6 sao cho mỗi cạnh trong formula_7 tương ứng với một đường đi (các đường đi này đôi một không chung cạnh) trong đồ thị formula_8.
- Một đồ thị được coi là nhúng được trên một bề mặt nếu khi vẽ đồ thị trên đó, các đỉnh và cạnh của nó có thể được sắp xếp trên đó sao cho không có hai cạnh nào cắt nhau.
- Nút ("knot")

- Nút ("node")

==P==
- Phản cạnh ("anti-edge")

- Phần bù ("complement")

==Q==
- Quan hệ liên thuộc

==R==
- Rừng

==S==
- Sắc số
- Siêu cạnh ("hyperedge")
- Siêu đồ thị ("hypergraph")

==T==
- Tập cắt

- Tập láng giềng

- Tập thống trị ("dominating set")

- Tập ổn định

- Tập ổn định trong cùng nghĩa với tập độc lập.
- Tập ổn định ngoài cùng nghĩa với tập thống trị.
- Thành phần liên thông

- Thành phần liên thông mạnh

- Thống trị

- Trọng số

==Xem thêm==
- Đồ thị (toán học)
- Lý thuyết đồ thị
- Danh sách các chủ đề lý thuyết đồ thị

==Tham khảo==
- Bollobás, Béla (1998). "Modern Graph Theory". New York: Springer-Verlag. ISBN 0-387-98488-7. ["Nhiều chủ đề nâng cao kèm thêm tổng quan về quá trình phát triển tai cuối mỗi chương."]
- West, Douglas B. (2001). "Introduction to Graph Theory" (2ed). Upper Saddle River: Prentice Hall. ISBN 0-13-014400-2. ["Nhiều minh họa, tham khảo, và bài tập. Hướng dẫn hoàn chỉnh nhất về chủ đề này."]
- Eric W. Weisstein. "Graph." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/Graph.html
- Zaslavsky, Thomas. Glossary of signed and gain graphs and allied areas. "Electronic Journal of Combinatorics", Dynamic Surveys in Combinatorics, # DS 8. http://www.combinatorics.org/Surveys/