Lý thuyết đồ thị - Thuộc tính cơ bản
Đồ thị có các thuộc tính khác nhau được sử dụng để mô tả đặc điểm của đồ thị tùy thuộc vào cấu trúc của chúng. Các thuộc tính này được định nghĩa theo các thuật ngữ cụ thể liên quan đến lĩnh vực lý thuyết đồ thị. Trong chương này, chúng ta sẽ thảo luận về một vài tính chất cơ bản phổ biến trong tất cả các đồ thị.
Khoảng cách giữa hai đỉnh
Nó là số cạnh trên đường đi ngắn nhất giữa đỉnh U và đỉnh V. Nếu có nhiều đường đi nối hai đỉnh thì đường đi ngắn nhất được coi là khoảng cách giữa hai đỉnh.
Kí hiệu - d (U, V)
Có thể có bất kỳ số lượng đường đi nào từ đỉnh này sang đỉnh khác. Trong số đó, bạn chỉ cần chọn một cái ngắn nhất.
Example
Hãy xem biểu đồ sau:
Ở đây, khoảng cách từ đỉnh 'd' đến đỉnh 'e' hoặc đơn giản là 'de' là 1 vì có một cạnh giữa chúng. Có nhiều đường đi từ đỉnh 'd' đến đỉnh 'e' -
- da, ab, be
- df, fg, ge
- de (Nó được coi là khoảng cách giữa các đỉnh)
- df, fc, ca, ab, be
- da, ac, cf, fg, ge
Độ lệch tâm của đỉnh
Khoảng cách lớn nhất giữa một đỉnh với tất cả các đỉnh khác được coi là độ lệch tâm của đỉnh.
Kí hiệu - e (V)
Khoảng cách từ một đỉnh cụ thể đến tất cả các đỉnh khác trong đồ thị được lấy và trong số các khoảng cách đó, độ lệch tâm là khoảng cách cao nhất.
Example
Trong đồ thị trên, độ lệch tâm của 'a' là 3.
Khoảng cách từ 'a' đến 'b' là 1 ('ab'),
từ 'a' đến 'c' là 1 ('ac'),
từ 'a' đến 'd' là 1 ('ad'),
từ 'a' đến 'e' là 2 ('ab' - 'be') hoặc ('ad' - 'de'),
từ 'a' đến 'f' là 2 ('ac' - 'cf') hoặc ('ad' - 'df'),
từ 'a' đến 'g' là 3 ('ac' - 'cf' - 'fg') hoặc ('ad' - 'df' - 'fg').
Vì vậy, độ lệch tâm là 3, là cực đại từ đỉnh 'a' và khoảng cách giữa 'ag' là cực đại.
Nói cách khác,
e (b) = 3
e (c) = 3
e (d) = 2
e (e) = 3
e (f) = 3
e (g) = 3
Bán kính của một đồ thị được kết nối
Độ lệch tâm nhỏ nhất từ tất cả các đỉnh được coi là bán kính của Đồ thị G. Giá trị nhỏ nhất trong số tất cả các khoảng cách lớn nhất giữa một đỉnh với tất cả các đỉnh khác được coi là bán kính của Đồ thị G.
Kí hiệu - r (G)
Từ tất cả các độ lệch tâm của các đỉnh trong một đồ thị, bán kính của đồ thị liên thông là nhỏ nhất của tất cả các độ lệch tâm đó.
Example
Trong đồ thị trên, r (G) = 2, là độ lệch tâm nhỏ nhất của 'd'.
Đường kính của một đồ thị
Độ lệch tâm lớn nhất từ tất cả các đỉnh được coi là đường kính của Đồ thị G. Giá trị lớn nhất trong số tất cả các khoảng cách giữa một đỉnh đến tất cả các đỉnh khác được coi là đường kính của Đồ thị G.
Notation − d(G) - Từ tất cả các độ lệch tâm của các đỉnh trong một đồ thị, đường kính của đồ thị liên thông là cực đại của tất cả các đường lệch tâm đó.
Example
Trong đồ thị trên, d (G) = 3; là độ lệch tâm tối đa.
Tâm điểm
Nếu độ lệch tâm của đồ thị bằng với bán kính của nó thì nó được gọi là điểm chính giữa của đồ thị. Nếu
e (V) = r (V),
thì 'V' là điểm chính giữa của Đồ thị 'G'.
Example
Trong đồ thị ví dụ, 'd' là điểm chính giữa của đồ thị.
e (d) = r (d) = 2
Trung tâm
Tập hợp tất cả các điểm chính giữa của 'G' được gọi là trọng tâm của Đồ thị.
Example
Trong biểu đồ ví dụ, {'d'} là tâm của Biểu đồ.
Chu vi
Các number of edges in the longest cycle of ‘G’ được gọi là chu vi của 'G'.
Example
Trong biểu đồ ví dụ, chu vi là 6, mà chúng tôi suy ra từ chu kỳ dài nhất acfgeba hoặc acfdeba.
Đường tròn
Số cạnh trong chu kỳ ngắn nhất của 'G' được gọi là Girth của nó.
Notation: g (G).
Example - Trong đồ thị ví dụ, Girth của đồ thị là 4, chúng ta suy ra từ chu trình ngắn nhất acfda hoặc dfged hoặc abeda.
Định lý tổng bậc của các đỉnh
Nếu G = (V, E) là một đồ thị không có hướng với các đỉnh V = {V 1 , V 2 ,… V n } thì
Corollary 1
Nếu G = (V, E) là một đồ thị có hướng với các đỉnh V = {V 1 , V 2 ,… V n } thì
Corollary 2
Trong bất kỳ đồ thị không hướng nào, số đỉnh có bậc Lẻ là Chẵn.
Corollary 3
Trong đồ thị không có hướng, nếu tung độ của mỗi đỉnh là k thì
Corollary 4
Trong đồ thị không có hướng, nếu tung độ của mỗi đỉnh ít nhất là k, thì
| Corollary 5
Trong đồ thị không hướng, nếu tung độ của mỗi đỉnh nhiều nhất là k thì