Đồ thị của mạng lưới đường và các thuật toán để làm việc với chúng. Mô hình toán học

Tuyên bố. Nếu có một tuyến cho hai đỉnh nối chúng thì phải có một tuyến cực tiểu nối các đỉnh này. Hãy biểu thị chiều dài của tuyến đường này làd (v,w).

Sự định nghĩa. giá trịd (v,w) (hữu hạn hoặc vô hạn) sẽ được gọi là khoảng cách giữa các đỉnh v, w . Khoảng cách này thỏa mãn tiên đề của hệ mét:

1) d (v,w) 0 vàd (v,w) = 0 nếu và chỉ khiv =w;

2) d (v, w) = d (w, v);

3) d (v, w) d (v, u) + d (u, w).

Sự định nghĩa. đường kính của một đồ thị liên thông là khoảng cách lớn nhất có thể có giữa hai trong số các đỉnh của nó.

Sự định nghĩa. Trung tâmĐồ thị là một đỉnh sao cho khoảng cách tối đa giữa nó và bất kỳ đỉnh nào khác là đỉnh nhỏ nhất có thể; khoảng cách này được gọi là bán kínhđồ thị.

Ví dụ 82.

Đối với đồ thị G được hiển thị trong hình. 3.16, tìm bán kính, đường kính và tâm.

Cơm. 3,16. Đếm ví dụ 82

Quyết định.

Để xác định tâm, bán kính, đường kính của đồ thị G, tìm ma trận D (g) khoảng cách giữa các đỉnh đồ thị, các phần tử dijđó sẽ là khoảng cách giữa các đỉnh v i và vj. Đối với điều này, chúng tôi sử dụng biểu diễn đồ họađồ thị. Lưu ý rằng ma trận D (g)đối xứng về đường chéo chính.

Sử dụng ma trận kết quả cho mỗi đỉnh đồ thị G xác định loại bỏ lớn nhất khỏi biểu thức: vì tôi,j = 1, 2,…, 5. Kết quả là, chúng tôi nhận được: r (v1) = 3,r (v2) = 2,r (v3) = 2,r (v4) = 2,r (v5) = 3. Số nhỏ nhất trong số các số thu được là bán kính của đồ thị G, đường kính lớn nhất là đường kính của biểu đồ G. Có nghĩa, R (G) = 2 và D (G) = 3, các trung tâm là các đỉnh câu 2,câu 3,câu 4.

Tính toán khoảng cách và xác định đường đi trong đồ thị là một trong những vấn đề thực tế và rõ ràng nhất nảy sinh trong lý thuyết đồ thị. Hãy để chúng tôi giới thiệu một số định nghĩa cần thiết.

Độ lệch tâmđỉnh của đồ thị - khoảng cách đến đỉnh xa nó nhất. Đối với một biểu đồ mà nó không được xác định cân nặng các cạnh của nó, khoảng cách được xác định là số cạnh.

Bán kínhđồ thị là độ lệch tâm nhỏ nhất của các đỉnh, và đường kính đồ thị là độ lệch tâm lớn nhất của các đỉnh.

Trung tâm biểu đồ dạng đỉnh có độ lệch tâm bằng bán kính. Tâm đồ thị có thể bao gồm một, một số hoặc tất cả các đỉnh đồ thị.

Ngoại vi các đỉnh có độ lệch tâm bằng đường kính.

Một chuỗi đơn giản có chiều dài bằng đường kính đồ thị được gọi là đường kính .

Định lý 12.1.Trong một đồ thị liên thông, đường kính nhiều nhất là hạng của ma trận kề của nó.

Định lý 12.2.(Jordan) Mọi cây đều có tâm gồm một hoặc hai đỉnh kề nhau.

Định lý 12.3.Nếu đường kính của cây là chẵn thì cây có một tâm và tất cả các chuỗi đường kính đều đi qua nó; nếu đường kính lẻ thì có hai tâm và tất cả các chuỗi đường kính đều chứa một cạnh nối chúng.

Chắc chắn giá trị thực tiễn tâm của đồ thị. Ví dụ: chúng tôi đang nói chuyện về một biểu đồ đường với các đỉnh-thành phố, thì trong trung tâm toán học, bạn nên đặt Trung tâm hành chính, nhà kho, v.v. Cách tiếp cận tương tự có thể được áp dụng cho đồ thị có trọng số, trong đó khoảng cách là trọng số của các cạnh. Như một trọng lượng, bạn có thể lấy khoảng cách Euclide, thời gian hoặc chi phí di chuyển giữa các điểm.

Ví dụ 12.5. Tìm bán kính, đường kính và tâm của đồ thị được hiển thị trong hình. 12.1.

Quyết định. Trong vấn đề này, nó là thuận tiện để sử dụng ma trận khoảng cách S. Phần tử của ma trận đối xứng vuông này bằng khoảng cách giữa đỉnh tôi và hàng đầu j. Đối với đồ thị được hiển thị trong Hình. 12.1, ma trận khoảng cách có lần xem tiếp theo:

Hãy tính độ lệch tâm của mỗi đỉnh. Giá trị này có thể được xác định là phần tử lớn nhất của cột tương ứng của ma trận khoảng cách (hoặc hàng, vì ma trận Sđối xứng). Chúng tôi nhận được

Bán kính đồ thị r là độ lệch tâm nhỏ nhất của các đỉnh. TẠI trường hợp này r= 2. Các đỉnh số 2, số 4 và số 5 có độ lệch tâm như vậy, các đỉnh này tạo thành tâm của đồ thị. Đường kính đồ thị d là độ lệch tâm lớn nhất của các đỉnh. Trong trường hợp này d= 3. Các đỉnh số 1 và số 3 có độ lệch tâm như vậy, đây là ngoại vi của đồ thị. Trong đồ thị đã nghiên cứu, các đỉnh hóa ra là trung tâm hoặc ngoại vi. Có các đỉnh khác trong đồ thị có bậc cao hơn.

Độ lệch tâm của các đỉnh của một đồ thị nhỏ có thể dễ dàng tính được bằng cách tính trực tiếp từ hình vẽ. Tuy nhiên, biểu đồ không phải lúc nào cũng được xác định bởi hình vẽ của nó. Ngoài ra, biểu đồ có thể có size lớn. Do đó, cần có một cách khác để giải quyết vấn đề trước đó. Định lý sau đây đã biết.

Định lý 12.4. Giả sử ma trận kề của đồ thị G không có vòng lặp và, trong đó. Khi đó nó bằng số tuyến có độ dài k từ đỉnh đến đỉnh.

Giải các bài toán của lý thuyết đồ thị bằng cách sử dụng các phép biến đổi khác nhau của ma trận kề được gọi là phương pháp đại số .

Ví dụ 12.6. Tìm ma trận khoảng cách của đồ thị được hiển thị trong hình. 12.1, bằng phương pháp đại số.

Quyết định. Ma trận kề của đồ thị này là:

Chúng ta sẽ điền vào ma trận khoảng cách bằng cách xem xét các bậc của ma trận kề. Các đơn vị ma trận kề hiển thị các cặp đỉnh có khoảng cách giữa chúng là một (nghĩa là chúng được nối với nhau bằng một cạnh duy nhất).

Các phần tử đường chéo của ma trận khoảng cách là số không. Nhân ma trận kề với chính nó:

Theo định lý giữa các đỉnh 2 và 3, 1 và 4, v.v. có một số tuyến có độ dài 2 (vì bậc của ma trận là hai). Số lượng tuyến đường không được sử dụng ở đây, thực tế về sự tồn tại của một tuyến đường và độ dài của nó là rất quan trọng, được biểu thị bằng phần tử khác 0 của mức độ của ma trận, phần tử này không trùng với phần tử được ghi chú khi tính toán một tuyến đường có độ dài nhỏ hơn. Chúng tôi đặt 2 vào các phần tử trống của ma trận khoảng cách và nhận được ước tính tiếp theo:

Khoảng cách giữa các đỉnh 1 và 3 vẫn chưa biết. Chúng ta sẽ nhân ma trận kề trên chính nó cho đến khi ma trận phần tử non-null sẽ không xuất hiện . Sau đó, phần tử tương ứng của ma trận khoảng cách bằng mức độ ma trận kề: . Ở bước tiếp theo, chúng tôi nhận được

vì thế, , và cuối cùng

Ma trận kết quả trùng với ma trận khoảng cách S(12.2) được tìm thấy bằng các tính toán trực tiếp từ hình.

Gọi G (V, X) là một giả và để các đỉnh v và w (v¹w) của đồ thị này được nối với nhau bằng một tuyến đường. Khi đó nhất thiết phải tồn tại một tuyến đường tối thiểu nối các đỉnh này. Biểu thị độ dài của tuyến đường này d (v, w). Chúng tôi cũng đặt d (v, v) = 0 cho bất kỳ đỉnh nào vнV; d (v, w) = ¥ nếu không có lộ trình giữa v và w.

Giá trị d (v, w) được xác định theo cách này cho mọi đỉnh v và w của đồ thị G (V, X) được gọi là khoảng cách giữa v và w.

Số khoảng cách trong đồ thị có n đỉnh bằng số tổ hợp C n 2.

Cho đồ thị G (V, X) là liên thông. Hãy để chúng tôi xác định các khái niệm sau cho nó:

Đường kính đồ thị: d (G) = maxd (v, w).

Độ lệch tâm (độ lệch lớn nhất) của đỉnh: r (v) = maxd (v, w);

Bán kính đồ thị: r (G) = min r (v);

Trung tâm đồ thị: đỉnh vОV bất kỳ sao cho r (v) = r (G).

Đường kính của đồ thị, độ lệch tâm của các đỉnh, bán kính của đồ thị và tâm của đồ thị được gọi là các đặc trưng metric của đồ thị.

Ví dụ. Để tìm thông số kỹ thuật số liệuđồ thị được cho bởi sơ đồ:

Hãy để chúng tôi tìm tất cả các khoảng cách, có tính đến rằng d (v, w) = d (w, v).

Số khoảng cách trong đồ thị đã cho С 5 2 = 5! / 3! 2! = 10: d (v 1, v 2) = 1, d (v 1, v 3) = 2, d (v 1, v 4) = 2, d (v 1, v 5) = 3, d (v 2, v 3) = 1, d (v 2, v 4) = 1, d (v 2, v 5) = 2, d (v 3, v 4) = 1, d (v 3, v 5) = 2, d (v 4, v 5) = 1.

Đường kính đồ thị d (G) = 3.

Độ lệch tâm của đỉnh: r (v 1) = 3, r (v 2) = 2, r (v 3) = 2, r (v 4) = 2, r (v 5) = 3.

Bán kính đồ thị r (G) = 2.

Đồ thị tâm v 2, v 3, v 4.

3. Các tuyến đường tối thiểu trong đồ thị được tải

Một đồ thị G (V, X) được gọi là có tải nếu trên tập các cạnh của đồ thị có một hàm gọi là hàm trọng số liên kết với mỗi cạnh x нX của đồ thị một số l (x). Giá trị l (x) được gọi là độ dài cung tròn.

Số lượng l (x) có thể được ý nghĩa khác nhau: chi phí vận chuyển, thời gian di chuyển, khoảng cách giữa các điểm, mức tiêu thụ xăng dầu, v.v.

Tổng độ dài của các cạnh có trong tuyến được gọi là độ dài của tuyến.

Lưu ý rằng nếu với mọi x н X l (x) = 1, thì đồ thị có thể được coi là không tải.

Một tuyến trong đồ thị G (V, X) từ đỉnh v đến đỉnh w (v¹w) được gọi là cực tiểu nếu nó có độ dài nhỏ nhất trong số tất cả các tuyến trong đồ thị G (V, X) từ đỉnh v đến đỉnh w.

Chúng ta tự giới hạn mình trong các đồ thị mà l (x)> 0.

Khi tìm kiếm tuyến đường nhỏ nhất trong biểu đồ được tải với l (x)> 0

chúng tôi sử dụng câu lệnh tương tự như đối với một biểu đồ không tải, cụ thể là:

bất kỳ tuyến đường tối thiểu nào là một con đường đơn giản.

Bây giờ hãy xem xét vấn đề tìm đường đi nhỏ nhất trong một đồ thị được tải.

Để tải đồ thị G (V, X), số đỉnh n ³ 2, cần dựng một giao tuyến cực tiểu từ v 1 đến v n.

Hãy đưa ra một thuật toán.

Bước 1. Gán chỉ số a (v i) cho mỗi đỉnh: a (v 1) = 0, a (v i) = ¥, i ¹ 1. Tô màu đỉnh v 1 và đặt v = v 1.

Bước 2. Đối với mỗi đỉnh không màu v j thay đổi chỉ số theo quy tắc:

a (v j) = min (a (v j), a (v) + l (v, v j)).

Tô màu cho đỉnh mà a (v j) là nhỏ nhất .. cũng tô màu cho cạnh dẫn đến nút đã chọn. bước nàyđỉnh v j. Đặt v = v j.

Bước 3. Nếu v = v j, hãy kết thúc thủ tục kể từ khi con đường ngắn nhất từ ​​v 1 đến v n. nếu v ¹ v n, thì chuyển sang bước 2.

Nhận xét. Bước 2 là không thể nếu tất cả a (v j) = ¥. Trong trường hợp này, đỉnh v n là không thể truy cập được.

Hãy để chúng tôi áp dụng thuật toán trên cho đồ thị được cho bởi sơ đồ. Hãy tìm trong đó đường đi ngắn nhất từ ​​v 1 đến v 6.

Bước 1. Tô màu đỉnh v 1. Gán chỉ số cho các đỉnh: a (v 1) = 0, a (v 2) = a (v 3) =… = a (v n) = ¥. Ta đặt v 1 = v.

a (v 2) = min (¥, 0 + 4) = 4,

a (v 3) = min (¥, 0 + 7) = 7,

a (v 4) = min (¥, 0 + 3) = 3,

a (v 5) = min (¥, 0 + ¥) = ¥,

a (v 6) = min (¥, 0 + ¥) = ¥.

Ta tô màu đỉnh v 4 và cạnh (v 1, v 4).

Bước 3. Vì đỉnh v 6 không được tô màu nên ta thực hiện bước 2, đặt v = v 4.

a (v 2) = min (4, 3 + ¥) = 4,

a (v 3) = min (7, 3 + ¥) = 7,

a (v 5) = min (¥, 3 + 3) = 6,

a (v 6) = min (¥, 3 + ¥) = ¥.

Ta tô màu đỉnh v 2 và cạnh (v 1, v 2).

Bước 3. Vì đỉnh v 6 không được tô màu nên ta thực hiện bước 2, đặt v = v 2.

a (v 3) = min (7, 4 + 3) = 7,

a (v 5) = min (6, 4 + 2) = 6,

a (v 6) = min (¥, 4 + ¥) = ¥.

Chúng ta tô màu đỉnh v 5 và cạnh (v 4, v 5).

Bước 3. Vì đỉnh v 6 không được tô màu nên ta thực hiện bước 2, đặt v = v 5.

a (v 3) = min (7, 6 + ¥) = 7,

a (v 6) = min (¥, 6 + 2) = 8.

Ta tô màu đỉnh v 3 và cạnh (v 1, v 3).

Bước 3. Vì đỉnh v 6 không được tô màu nên ta thực hiện bước 2, đặt v = v 3.

a (v 6) = min (8, 7 + 2) = 8.

Chúng ta tô màu đỉnh v 6 và cạnh (v 5, v 6).

Vì đỉnh v 6 được tô màu nên chúng tôi dừng công việc. Chúng tôi nhận được tuyến đường nhỏ nhất v 1 v 4 v 5 v 6, độ dài của nó bằng 8.

Lưu ý rằng trong trường hợp này, đây không phải là tuyến đường tối giản duy nhất cho các đỉnh v 1 và v 6, bởi vì trong thuật toán, có thể tô màu thay vì cạnh (v 4, v 5) cạnh (v 2, v 5), sau đó chúng ta sẽ nhận được một tuyến đường khác có cùng độ dài.

4. Nhiệm vụ trên cây

Một đồ thị được gọi là xoay chiều nếu không có chu trình nào.

Một đồ thị không có chu trình được gọi là một khu rừng.

Cây là một đồ thị mạch hở liên thông.

Tính toán khoảng cách và xác định đường đi trong đồ thị là một trong những vấn đề thực tế và rõ ràng nhất nảy sinh trong lý thuyết đồ thị. Hãy để chúng tôi giới thiệu một số định nghĩa cần thiết.

Độ lệch tâmđỉnh của đồ thị - khoảng cách đến đỉnh xa nó nhất. Đối với một biểu đồ mà nó không được xác định cân nặng các cạnh của nó, khoảng cách được xác định là số cạnh.

Bán kínhđồ thị là độ lệch tâm nhỏ nhất của các đỉnh, và đường kính đồ thị là độ lệch tâm lớn nhất của các đỉnh.

Trung tâmĐồ thị được tạo thành bởi các đỉnh có độ lệch tâm bằng bán kính. Tâm đồ thị có thể bao gồm một, một số hoặc tất cả các đỉnh đồ thị.

Ngoại vi các đỉnh có độ lệch tâm bằng đường kính.

Một chuỗi đơn giản có chiều dài bằng đường kính đồ thị được gọi là đường kính .

Định lý 12.1.Trong một đồ thị liên thông, đường kính nhiều nhất là hạng của ma trận kề của nó.

Định lý 12.2.(Jordan) Mọi cây đều có tâm gồm một hoặc hai đỉnh kề nhau.

Định lý 12.3.Nếu đường kính của cây là chẵn thì cây có một tâm và tất cả các chuỗi đường kính đều đi qua nó; nếu đường kính lẻ thì có hai tâm và tất cả các chuỗi đường kính đều chứa một cạnh nối chúng.

Ý nghĩa thực tế của trung tâm của đồ thị là rõ ràng. Ví dụ, nếu chúng ta đang nói về một biểu đồ đường với các đỉnh là thành phố, thì nên đặt trung tâm hành chính, nhà kho, v.v. ở trung tâm toán học. Cách tiếp cận tương tự có thể được áp dụng cho đồ thị có trọng số, trong đó khoảng cách là trọng số của các cạnh. Như một trọng lượng, bạn có thể lấy khoảng cách Euclidean, thời gian hoặc chi phí di chuyển giữa các điểm.

Ví dụ 12.5. Tìm bán kính, đường kính và tâm của đồ thị được hiển thị trong hình. 12.1.

Quyết định. Trong vấn đề này, nó là thuận tiện để sử dụng ma trận khoảng cách S. Phần tử của ma trận đối xứng vuông này bằng khoảng cách giữa các đỉnh tôi và hàng đầu j. Đối với đồ thị được hiển thị trong Hình. 12.1, ma trận khoảng cách có dạng sau:

. (12.2)

Hãy tính độ lệch tâm của mỗi đỉnh. Giá trị này có thể được xác định là phần tử lớn nhất của cột tương ứng của ma trận khoảng cách (hoặc hàng, vì ma trận Sđối xứng). Chúng tôi nhận được

№

Bán kính đồ thị r là độ lệch tâm nhỏ nhất của các đỉnh. Trong trường hợp này r= 2. Các đỉnh số 2, số 4 và số 5 có độ lệch tâm như vậy, các đỉnh này tạo thành tâm của đồ thị. Đường kính đồ thị d là độ lệch tâm lớn nhất của các đỉnh. Trong trường hợp này d= 3. Các đỉnh số 1 và số 3 có độ lệch tâm như vậy, đây là ngoại vi của đồ thị. Trong đồ thị đã nghiên cứu, các đỉnh hóa ra là trung tâm hoặc ngoại vi. Có các đỉnh khác trong đồ thị có bậc cao hơn.

Độ lệch tâm của các đỉnh của một đồ thị nhỏ có thể dễ dàng tính được bằng cách tính trực tiếp từ hình vẽ. Tuy nhiên, biểu đồ không phải lúc nào cũng được xác định bởi hình vẽ của nó. Ngoài ra, đồ thị có thể lớn. Do đó, cần có một cách khác để giải quyết vấn đề trước đó. Định lý sau đây đã biết.

Định lý 12.4. Giả sử ma trận kề của đồ thị G không có vòng lặp và, trong đó. Khi đó nó bằng số tuyến có độ dài k từ đỉnh đến đỉnh.

Giải các bài toán của lý thuyết đồ thị bằng cách sử dụng các phép biến đổi khác nhau của ma trận kề được gọi là phương pháp đại số .

Ví dụ 12.6. Tìm ma trận khoảng cách của đồ thị được hiển thị trong hình. 12.1, bằng phương pháp đại số.

Quyết định. Ma trận kề của đồ thị này là:

.

Chúng ta sẽ điền vào ma trận khoảng cách bằng cách xem xét các bậc của ma trận kề. Các đơn vị ma trận kề hiển thị các cặp đỉnh có khoảng cách giữa chúng là một (nghĩa là chúng được nối với nhau bằng một cạnh duy nhất).

.

Các phần tử đường chéo của ma trận khoảng cách là số không. Nhân ma trận kề với chính nó:

.

Theo định lý giữa các đỉnh 2 và 3, 1 và 4, v.v. có một số tuyến có độ dài 2 (vì bậc của ma trận là hai). Số lượng tuyến đường không được sử dụng ở đây, thực tế về sự tồn tại của một tuyến đường và độ dài của nó là rất quan trọng, được biểu thị bằng phần tử khác 0 của mức độ của ma trận, phần tử này không trùng với phần tử được ghi chú khi tính toán một tuyến đường có độ dài nhỏ hơn. Chúng tôi đặt 2 vào các phần tử trống của ma trận khoảng cách và nhận được giá trị gần đúng sau:

.

Khoảng cách giữa các đỉnh 1 và 3 vẫn chưa biết. Chúng ta sẽ nhân ma trận kề trên chính nó cho đến khi ma trận phần tử non-null sẽ không xuất hiện . Khi đó phần tử tương ứng của ma trận khoảng cách bằng bậc của ma trận kề: . Ở bước tiếp theo, chúng tôi nhận được