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

Bản tường trình. Nếu có một tuyến đường cho hai đỉnh kết nối chúng, thì phải có một tuyến đường tối thiểu kết nối các đỉnh này. Hãy biểu thị độ 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 khoảng cách giữa các đỉnh v, w . Khoảng cách này thỏa mãn các tiên đề của số liệu:

1) d(v,w) 0, vàd(v,w) = 0 khi 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ể giữa hai đỉ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ấ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

Dung dịch.

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 tôi và vj. Đối với điều này, chúng tôi sử dụng đại diện đồ họađồ thị. Lưu ý rằng ma trận D(g)đối xứng qua đườ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. Giá trị nhỏ nhất của các số thu được là bán kính của đồ thị g, cực đại là đường kính của đồ thị g. Có nghĩa, r(G) = 2 và D(G) = 3, các 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 các đỉnh của đồ thị - khoảng cách đến đỉnh cách 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 định nghĩa là số lượng các cạnh.

bán kínhđồ thị là độ lệch tâm tối thiểu 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 các đỉnh dạng đồ thị 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 của đồ 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 của đồ 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 bao 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 duy nhất và tất cả các chuỗi đường kính đều đi qua nó; nếu đường kính là số lẻ, thì có hai tâm và tất cả các chuỗi đường kính đều có một cạnh nối chúng.

Rõ ràng giá trị thực tiễn tâm của đồ thị. Nếu, ví dụ, chúng tôi đang nói chuyện về biểu đồ đường có đỉnh-thành phố, thì nên đặt ở trung tâm toán học 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. Là 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ị như hình vẽ. 12.1.

Dung dịch. 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 đầu 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ó xem tiếp theo:

Hãy tính độ lệch tâm của mỗi đỉnh. Giá trị này có thể được định nghĩa 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, 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ị đ là độ lệch tâm lớn nhất của các đỉnh. Trong trường hợp này đ= 3. Các đỉnh số 1 và số 3 có độ lệch tâm như vậy, đây là chu vi của đồ thị. Trong biểu đồ được 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ị bậc cao hơn.

Độ lệch tâm của các đỉnh của một đồ thị nhỏ có thể được tính dễ dàng bằng phép tính trực tiếp từ hình vẽ. Tuy nhiên, đồ thị 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ể có size lớn. Do đó, một cách khác để giải quyết vấn đề trước đó là cần thiết. Định lý sau đây được biết đến.

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

Việc giải các bài toán lý thuyết đồ thị bằ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 biểu đồ hiển thị trong hình. 12.1, bằng phương pháp đại số.

Dung dịch. 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 xét 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).

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 đỉnh 2 và 3, 1 và 4, v.v. có một số tuyến đường 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ế là sự tồn tại của tuyến đường và độ dài của nó rất quan trọng, được biểu thị bằng một phần tử khác 0 của cấp độ ma trận, không trùng với phần tử được lưu ý 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 xấp xỉ tiếp theo:

Khoảng cách giữa đỉnh 1 và 3 vẫn chưa biết, ta sẽ nhân ma trận kề trên chính nó cho đến khi ma trận phần tử không 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 cấp ma trận kề: . Ở bước tiếp theo, chúng tôi nhận được

Do đó, , 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) tìm được bằng phép tính trực tiếp từ hình vẽ.

Gọi G(V,X) là một đồ thị giả và đặt 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 đường nhỏ nhất 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ó đường đi 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 với số tổ hợp C n 2 .

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

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

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

Bán kính đồ thị: r(G) = tối thiểu r(v);

Trung tâm đồ thị: bất kỳ đỉnh vОV 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 số liệu của đồ thị.

Thí dụ. Tìm thấy thông số kỹ thuật số liệuđồ thị 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 d(v, w) = d(w, v).

Số khoảng cách trong cột đã 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 đỉ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.

Tâm đồ thị v 2 , v 3 , v 4 .

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

Một đồ thị G(V, X) được gọi là tải nếu trên tập các cạnh của đồ thị tồn tại một hàm gọi là hàm trọng số liên hệ 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.

Số lượng l(x) có thể được cho ý 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, lượng xăng tiêu thụ, v.v.

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

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

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

Chúng tôi giới hạn bản thân trong các đồ thị mà l(x)>0.

Khi tìm kiếm tuyến đường tối thiểu 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 biểu đồ không tải, cụ thể là:

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

Bây giờ xét bài toán tìm đường đi nhỏ nhất trong đồ thị đã tải.

Để đồ thị G(V,X) được tải, số đỉnh n ³ 2, cần dựng một lộ trình tối thiể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 tô màu v j thay đổi chỉ số theo quy tắc:

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

Tô màu đỉnh mà a(v j) là nhỏ nhất.. cũng tô màu 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 , kết thúc thủ tục vì đường đi ngắn nhất từ ​​v 1 đến v n . nếu v ¹ v n , thì chuyển sang bước 2.

Bình luận. 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 không thể truy cập được.

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

Bước 1. Tô màu cho đỉ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) = tối thiểu (¥, 0+¥) = ¥,

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

Chúng tôi 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) = tối thiểu(7, 3+¥) = 7,

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

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

Ta tô màu cho đỉ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) = tối thiểu(7, 4+3) = 7,

a(v 5) = tối thiểu(6, 4+2) = 6,

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

Chúng tôi 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) = tối thiểu(7, 6+¥) = 7,

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

Chúng 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 tôi tô màu đỉnh v 6 và cạnh (v 5 , v 6 ).

Vì đỉnh v 6 được tô màu, chúng tôi dừng công việc. Chúng tôi có tuyến đường tối thiểu 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à đường tối thiểu 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 cho cạnh (v 4 , v 5 ) thành cạnh (v 2 , v 5 ) thì ta sẽ được một đường đi khác có cùng độ dài.

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

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

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

Cây là đồ thị tuần hoàn 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 các đỉnh của đồ thị - khoảng cách đến đỉnh cách 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 định nghĩa là số lượng các cạnh.

bán kínhđồ thị là độ lệch tâm tối thiểu 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 hình 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 của đồ 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 của đồ 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 bao 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 duy nhất và tất cả các chuỗi đường kính đều đi qua nó; nếu đường kính là số lẻ, thì có hai tâm và tất cả các chuỗi đường kính đều có 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ề biểu đồ đường có đỉnh-thành phố, thì 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. Là 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ị như hình vẽ. 12.1.

Dung dịch. 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 định nghĩa 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, 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ị đ là độ lệch tâm lớn nhất của các đỉnh. Trong trường hợp này đ= 3. Các đỉnh số 1 và số 3 có độ lệch tâm như vậy, đây là chu vi của đồ thị. Trong biểu đồ được 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ị bậc cao hơn.

Độ lệch tâm của các đỉnh của một đồ thị nhỏ có thể được tính dễ dàng bằng phép tính trực tiếp từ hình vẽ. Tuy nhiên, đồ thị 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 đó, một cách khác để giải quyết vấn đề trước đó là cần thiết. Định lý sau đây được biết đến.

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

Việc giải các bài toán lý thuyết đồ thị bằ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 biểu đồ hiển thị trong hình. 12.1, bằng phương pháp đại số.

Dung dịch. 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 xét 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).

.

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 đỉnh 2 và 3, 1 và 4, v.v. có một số tuyến đường 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ế là sự tồn tại của tuyến đường và độ dài của nó rất quan trọng, được biểu thị bằng một phần tử khác 0 của cấp độ ma trận, không trùng với phần tử được lưu ý 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 xấp xỉ sau:

.

Khoảng cách giữa đỉnh 1 và 3 vẫn chưa biết, ta sẽ nhân ma trận kề trên chính nó cho đến khi ma trận phần tử không 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 cấp của ma trận kề: . Ở bước tiếp theo, chúng tôi nhận được