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.

Ví dụ một đồ thị đơn với tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = Bản mẫu:1,2, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, Bản mẫu:4,6.

B

• Bậc (degree hoặc valency)

Bậc của đỉnh v trong đồ thị G, ký hiệu d_G(v), là số cạnh liên thuộc với v, trong đó, khuyên được tính hai lần. Một đỉnh có bậc 0 là đỉnh cô lập. Đỉnh có bậc 1 là một đỉnh treo hay lá. Trong đồ thị ví dụ, các đỉnh 1 và 3 có bậc là 2, các đỉnh 2, 4 và 5 có bậc bằng 3, đỉnh 6 có bậc 1.

Nếu tập cạnh E là hữu hạn thì tổng giá trị bậc của các đỉnh gọi là bậc của đồ thị. Bậc của đồ thị bằng hai lần số cạnh. Số các đỉnh bậc lẻ luôn là số chẵn.

Bậc cực đại của đồ thị G, ký hiệu Δ(G), là bậc lớn nhất của các đỉnh trong đồ thị; bậc cực tiểu, δ(G), là bậc nhỏ nhất của các đỉnh trong đồ thị.Ví dụ

Trong đồ thị có hướng Γ, bậc ngoài d_Γ⁺(v), số cung xuất phát từ đỉnh v(số cung đi ra đỉnh v), và bậc trong d_Γ^-(v), số cung đi vào đỉnh v. Bậc d_Γ(v) của đỉnh v bằng tổng bậc ngoài và bậc trong của đỉnh đó. Bậc ngoài cực đại và cực tiểu được ký hiệu Δ⁺_(Γ) và δ⁺_(Γ); bậc trong cực đại và cực tiểu, Δ^-_(Γ) và δ^-_(Γ). Trong ngữ cảnh rõ ràng, có thể bỏ qua chỉ số dưới Γ.

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

là một tính chất của một đồ thị G, thường là một số hoặc một đa thức chỉ phụ thuộc vào lớp đẳng cấu của G. Ví dụ: bậc của đồ thị.

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.

Cây đơn phân chỉ là một đường đi.

Cây nhị phân là cây mà mỗi đỉnh có không quá 2 con.

Cây nhị phân đầy đủ là cây mà mỗi đỉnh trong có đúng 2 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_n,
  • 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_n). 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)

Đồ thị con H của đồ thị G được coi là dẫn xuất nếu: với mỗi cặp đỉnh x và y của H, xy là một cạnh của H khi và chỉ khi xy là một cạnh của G. Nếu H được chọn dựa trên tập đỉnh S là tập con của V(G), thì H còn được ký hiệu là G[S] và được coi là dẫn xuất từ S.

Đ

• Đẳng cấu

Hai đồ thị G và H được coi là đẳng cấu, ký hiệu G ~ H, nếu có một quan hệ tương ứng một-một giữa hai tập đỉnh của hai đồ thị sao cho hai đỉnh của đồ thị G kề nhau khi và chỉ khi các đỉnh tương ứng của chúng trong đồ thị H cũng kề nhau.

• Đỉ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_n, 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 ${\displaystyle n}$ bất kỳ, khi đó, nó được gọi là đồ thị rỗng ${\displaystyle n}$ đỉ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

Độ dài của một đường đi là số cạnh mà nó đi qua. Đường đi P_n có độ dài n - 1. Trong đồ thị ví dụ, (1, 2, 5, 1, 2, 3) là đường đi có độ dài 5, còn (5, 2, 1) là đường đi đơn có độ dài 2.

Độ dài của một chu trìnhlà số cạnh của nó, số này cũng bằng số đỉnh nó đi qua (tính cả bội, nếu một đỉnh được đi qua nhiều lần). C_n có độ dài n. Khác với đường đi, chu trình không được phép có độ dài 0. Các chu trình độ dài 1 là các khuyên. Các chu trình độ dài 2 là các cặp đa cạnh. Trong đồ thị ví dụ, (1, 2, 3, 4, 5, 1) là chu trình độ dài 5.

• Độc lập

Hai đường đi được coi là độc lập nếu chúng không có chung đỉnh nào, ngoại trừ đỉnh đầu và đỉnh cuối.

Một đỉnh cô lập hoặc đỉnh độc lập là đỉnh không liên thuộc với một cạnh nào, cũng có nghĩa là đỉnh có bậc 0.

Một tập độc lập, hay tập ổn định, là tập các đỉnh đôi một không kề nhau. Đồ thị con dẫn xuất từ một tập độc lập là một đồ thị rỗng. Trong ví dụ trên, các đỉnh 1, 3 và 6 hợp thành một tập độc lập; các đỉnh 3, 5 và 6 hợp thành một tập độc lập khác.

Số độc lập (indepndence number) của một đồ thị là số cực đại các đỉnh của tập độc lập ứng với đồ thị đó

• Đồng cấu

Một đồ thị G được coi là đồng cấu với đồ thị H nếu có một ánh xạ từ V(G) tới V(H) sao cho: nếu hai đỉnh kề nhau trong G thì các đỉnh tương ứng của nó cũng kề nhau trong đồ thị H.

• Đườ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_n.
  • Đườ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)

Việc gán các nhãn phân biệt (thường là các số) cho các cạnh và đỉnh của đồ thị.

• Gốc

xem Đỉnh 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

Khoảng cách d_G(u, v) giữa hai đỉnh (không nhất thiết phân biệt u và v trong đồ thị G là độ dài đường đi ngắn nhất giữa chúng. Có thể bỏ chỉ số dưới G nếu không sợ hiểu nhầm. Khi u và v là một, khoảng cách giữa chúng bằng 0. Khi giữa u và v không có đường đi, khoảng cách giữa chúng là vô cùng ∞.

• Khuyên (loop)

Cạnh có hai đầu trùng nhau (cùng một đỉnh).

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

Kích thước của một đồ thị là số cạnh của nó, nghĩa là |E(G)|.

L

• Lá

Xem Đỉnh lá.

• Lát cắt đỉnh

là tập các đỉnh mà khi loại bỏ chúng sẽ làm cho đồ thị mất tính liên thông.

• Lát cắt cạnh

là tập tất cả các cạnh có một đầu thuộc tập đỉnh con S và đầu kia thuộc V(G)\S.

• Liên thông

Nếu giữa hai điểm bất kỳ của một đồ thị đều có thể thiết lập một đường đi từ đỉnh này đến đỉnh kia, đồ thị được coi là liên thông; nếu không, đồ thị được coi là không liên thông. Một đồ thị được coi là hoàn toàn không liên thông nếu không có đường đi giữa hai đỉnh bất kỳ trong đồ thị. Đây chỉ là một cái tên khác để miêu tả một đồ thị rỗng hoặc một tập độc lập.

Một đồ thị có hướng được coi là liên thông mạnh nếu từ mọi đỉnh đều đến được mọi đỉnh khác. Ngược lại, đồ thị có hướng được coi là liên thông yếu nếu đồ thị vô hướng nền tảng của nó là đồ thị liên thông.

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

Trong một số tài liệu về lý thuyết đồ thị, thuật ngữ lưới (network) được coi là từ đồng nghĩa với đồ thị có trọng số. Một lưới có thể có hướng hoặc vô hướng. Lưới có thể chứa các đỉnh (nút) đặc biệt, chẳng hạn đỉnh phát hoặc đỉnh thu.

M

• Ma trận kề

Một ma trận kích thước n×n, trong đó mỗi phần tử tại dòng i cột j cho biết số cạnh nối từ đỉnh thứ i tới đỉnh thứ j.

N

• Nhân (kernel)

là một tập độc lập ổn định ngoài. Một đồ thị có hướng được gọi là nhân hoàn hảo (kernel perfect) nếu mọi đồ thị con dẫn xuất đều có một nhân.

• Nhúng: (embedding)
  • Phép nhúng thực hiện trên ${\displaystyle G_{1}=(V_{1},E_{1})}$ (cho kết quả là đồ thị ${\displaystyle G_{2}=(V_{2},E_{2})}$) là một hàm đơn ánh từ ${\displaystyle V_{1}}$ tới ${\displaystyle V_{2}}$ sao cho mỗi cạnh trong ${\displaystyle E_{1}}$ 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ị ${\displaystyle G_{2}}$.
  • 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)

trong một đồ thị có hướng, nút là một tập các đỉnh và cung với tính chất: mọi đỉnh trong nút đều có cung từ đó đi ra, và mọi cung xuất phát từ các đỉnh trong nút đều có đích là các đỉnh nằm trong nút. Do đó, không thể ra khỏi nút nếu đi theo hướng của các cung.

Trong trường hợp đồ thị là sơ đồ sử dụng tài nguyên (general resource graph), một nút là điều kiện đủ cho deadlock.

• Nút (node)

Trong một số ngữ cảnh, một đỉnh của đồ thị cũng được gọi là một nút. Chẳng hạn, các đỉnh trong một cây có gốc thường được gọi là nút.

P

• Phản cạnh (anti-edge)

Là một cạnh "không tồn tại".

Cho hai đỉnh ${\displaystyle u}$ và ${\displaystyle v}$, ${\displaystyle \{u,v\}}$ là một phản cạnh của đồ thị ${\displaystyle G}$ nếu ${\displaystyle (u,v)}$ không phải là cạnh của ${\displaystyle G}$. Nghĩa là: hoặc không có cạnh nào nối hai đỉnh, hoặc chỉ có một cung ${\displaystyle (v,u)}$ từ ${\displaystyle v}$ tới ${\displaystyle u}$ nếu ${\displaystyle G}$ là đồ thị có hướng.

• Phần bù (complement)

Phần bù ${\displaystyle {\bar {G}}}$ của một đồ thị G là một đồ thị có cùng tập đỉnh như G nhưng lại có tập cạnh thỏa mãn điều kiện: xy là một cạnh của ${\displaystyle {\bar {G}}}$ khi và chỉ khi xy không phải là cạnh của G.

Q

• Quan hệ liên thuộc

Quan hệ giữa cạnh và đỉnh là một trong hai đầu của cạnh đó.

R

• Rừng

là hợp của các cây; tương đương với một đồ thị phi chu trình.

S

• Sắc số

Sắc số χ(G) của một đồ thị G là số nhỏ nhất các màu cần thiết để tô màu đồ thị đó, nghĩa là tô màu các đỉnh của nó sao cho hai đỉnh kề nhau có màu khác nhau.

• Siêu cạnh (hyperedge)

Là cạnh có thể có số đỉnh đầu cuối tùy ý, có thể lớn hơn 2. Khi không nói rõ, một cạnh luôn được hiểu là có nhiều nhất 2 đỉnh.

• Siêu đồ thị (hypergraph)

Đồ thị cho phép có siêu cạnh. Khi không chỉ rõ, đồ thị không bao giờ bị hiểu nhầm là siêu đồ thị

T

• Tập cắt

xem lát cắt đỉnh.

• Tập láng giềng

Tập láng giềng, còn gọi là tập láng giềng (mở) của một đỉnh v, ký hiệu N_G(v), bao gồm tất cả các đỉnh kề với v không kể v. Nếu kể cả v, tập này được gọi là tập láng giềng đóng, ký hiệu N_G[v]. Nếu không nói rõ, một tập láng giềng được coi là mở. Chỉ số dưới G thường được bỏ qua nếu không gây nhầm lẫn. Trong đồ thị ví dụ, đỉnh 1 có hai hàng xóm: các đỉnh 2 và 5. Đối với đồ thị đơn, số láng giềng của một đỉnh trùng với bậc của đỉnh đó.

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

Một tập thống trị của một đồ thị là một tập con của tập đỉnh, trong đó hợp của các tập láng giềng đóng của các đỉnh trong tập con đó bao gồm tất cả các đỉnh của đồ thị.

• Tập ổn định

Xem Độc lập.

• 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

Quan hệ liên thông trong đồ thị vô hướng là quan hệ tương đương, quan hệ này chia tập các đỉnh của đồ thị thành các lớp tương đương, mỗi lớp được gọi là một thành phần liên thông của một đồ thị.

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

Thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con, trong đó từ mỗi đỉnh của nó đều có đường đi đến mọi đỉnh khác.

• Thống trị

Đỉnh v thống trị đỉnh u nếu có một cạnh từ v tới u. Một tập đỉnh V thống trị một tập đỉnh U khác nếu mọi đỉnh trong U đều thuộc V hoặc kề với một đỉnh nào đó trong V. Kích thước của tập thống trị nhỏ nhất được gọi là chỉ số thống trị γ(G).

Tập đỉnh S được gọi là thống trị ngoài (out-dominating) nếu mọi đỉnh ngoài S đều bị thống trị bởi một đỉnh nào đó thuộc S; gọi là thống trị trong (in-dominating) nếu mọi đỉnh thuộc S đều bị thống trị bởi một đỉnh nào đó không thuộc S.

• Trọng số

là các giá trị thường được gán cho các cạnh của đồ thị. Trọng số thường là các số thực. Chúng có thể bị giới hạn trong phạm vi số hữu tỷ hoặc số nguyên. Một số thuật toán có thể đòi hỏi các giới hạn khác đối với trọng số. Chẳng hạn, thuật toán Dijkstra chỉ dùng được cho các trọng số dương. Trọng số của đường đi hoặc trọng số của cây trong một đồ thị có trọng số là tổng trọng số của các cạnh được chọn. Đôi khi một cạnh không tồn tại được gán một trọng số đặc biệt để biểu diễn giá trị vô cùng. Từ chi phí đôi khi được dùng để chỉ 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/ Lưu trữ 2005-12-29 tại Wayback Machine