connectivity là gì

Bách khoa toàn thư phanh Wikipedia

Tính liên thông (connectivity) là 1 trong trong mỗi đặc điểm cần thiết nhất của vật dụng thị trình bày riêng rẽ và lý thuyết vật dụng thị trình bày cộng đồng.

Bạn đang xem: connectivity là gì

Định Nghĩa[sửa | sửa mã nguồn]

Một vật dụng thị được gọi là liên thông (connected) nếu như sở hữu lối đi thân ái từng cặp đỉnh phân biệt của vật dụng thị. trái lại, vật dụng thị này được gọi là ko liên thông (disconnected).^[1]

Cho vật dụng thị G = (X,U) vô phía hoặc được đặt theo hướng. Ta khái niệm một mối quan hệ <=> như hệ sau bên trên tập luyện đỉnh X:

Với từng i, j nằm trong X, i xấp xỉ j <=> i = j hoặc sở hữu dây chuyền sản xuất đỉnh đầu là i và đỉnh cuối là j.

Quan hệ này còn có 3 tính chất: bản năng, đối xứng và bắc cầu nên nó là 1 trong mối quan hệ tương tự. Do cơ tập luyện X được phân hoạch trở thành những lớp tương tự. Ta toan nghĩa:

Xem thêm: publications là gì

• Một bộ phận liên thông của vật dụng thị là 1 trong lớp tương tự được xác lập vì như thế mối quan hệ "xấp xỉ" trình bày trên;
• Số bộ phận liên thông của vật dụng thị là con số những lớp tương đương;
• Một vật dụng thị liên thông là 1 trong những vật dụng thị chỉ có một bộ phận liên thông.

Thành phần liên thông[sửa | sửa mã nguồn]

Một vật dụng thị ko liên thông tiếp tục bao hàm nhiều vật dụng thị con cái liên thông, những vật dụng thị con cái này được gọi là những bộ phận liên thông (connected component). Đồ thị liên thông khi và chỉ khi sở hữu một bộ phận liên thông.

Xem thêm: squawk là gì

Trong hình bên trên sở hữu 4 bộ phận liên thông. (Đỉnh k đứng riêng rẽ lẻ theo đuổi quy ước cũng tính là 1 trong những bộ phận liên thông)

Các toan lý[sửa | sửa mã nguồn]

• Định lý về lối đi thân ái 2 đỉnh bậc lẻ: Nếu một vật dụng thị G (không quan hoài liên thông hoặc không) sở hữu đích 2 đỉnh bậc lẻ, chắc chắn rằng sẽ sở hữu được một lối đi nối 2 đỉnh này.
• Định lý về số cạnh của vật dụng thị (Định lý bắt tay): Số cạnh tối nhiều của một đơn vật dụng thị ko liên thông G bao gồm n đỉnh và k bộ phận là .

Tính chất[sửa | sửa mã nguồn]

• Đồ thị liên thông sở hữu hướng
  • Liên thông mạnh (strongly connected): Đồ thị được đặt theo hướng gọi là liên thông mạnh nếu như sở hữu lối đi kể từ a cho tới b và kể từ b cho tới a với từng cặp đỉnh a và b của vật dụng thị. Xem thêm thắt bộ phận liên thông mạnh.
  • Liên thông yếu (weakly connected): Đồ thị được đặt theo hướng gọi là liên thông yếu hèn nếu như sở hữu lối đi thân ái 2 đỉnh ngẫu nhiên của vật dụng thị vô phía ứng với vật dụng thị vẫn mang đến. Tức là bỏ quăng quật những phía của những cạnh nhập vật dụng thị.
  • Liên thông một phần (unilaterally connected): Đồ thị được đặt theo hướng gọi là liên thông 1 phần nếu như với từng cặp đỉnh a, b ngẫu nhiên, sở hữu tối thiểu một đỉnh cho tới được đỉnh còn sót lại.

• Đỉnh khớp (cut vertex/ articulation point): của một vật dụng thị vô phía là đỉnh tuy nhiên nếu như xóa đỉnh này ngoài vật dụng thị và những cạnh nối cho tới nó thì số bộ phận liên thông của vật dụng thị tiếp tục gia tăng.
• Cạnh cầu (bridge): của một vật dụng thị vô phía là cạnh tuy nhiên nếu như xóa cút ngoài vật dụng thị thì số bộ phận liên thông của vật dụng thị tiếp tục gia tăng.
• Đồ thị tuy vậy liên thông (biconnectivity): là vật dụng thị ko chứa chấp đỉnh khớp.

Tham khảo[sửa | sửa mã nguồn]