Mô hình toán học. Đặc điểm số liệu của đồ thị vô hướng

Tuyên bố. Nếu hai đỉnh có một đường nối chúng thì chắc chắn sẽ có một đường đi tối thiểu nối các đỉnh này. Chúng ta hãy biểu thị độ dài của tuyến đường này bằngd(v,w).

Sự định nghĩa. Kích cỡ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 đề 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ể có giữa hai đỉnh của nó.

Sự định nghĩa. Trung tâm một đồ thị được gọi 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ể có; 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. Đồ thị ví dụ 82

Giải pháp.

Xác định tâm, bán kính, đường kính của đồ thị G, hãy tìm ma trận D(G) khoảng cách giữa các đỉnh đồ thị, các phần tử d ijđó sẽ là khoảng cách giữa các đỉnh v tôi Và v j. Đối với điều này, chúng tôi sẽ sử dụng biểu 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 của đồ thị G Hãy xác định mức 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(v 1) = 3,r(v 2) = 2,r(v 3) = 2,r(v 4) = 2,r(v 5) = 3. Giá trị nhỏ nhất của các số kết quả là bán kính của đồ thị G, đường kính đồ thị tối đa G. Có nghĩa, R(G) = 2 Và D(G) = 3, tâm là các đỉnh v2,v 3,v 4.

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

Độ lệch tâmđỉnh đồ thị - khoảng cách đến đỉnh tối đa từ nó. Đối với một biểu đồ 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 bằng số 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ệch tâm tối đa 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 của đồ 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 đồ thị liên thông, đường kính không lớn hơn 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 liền kề.

Định lý 12.3.Nếu đường kính của cây 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 ý nghĩa thực tiễn tâm của đồ thị. Nếu, ví dụ, Chúng ta đang nói về về đồ thị các đường có đỉnh thành phố thì nên đặt vào 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 biểu đồ có trọng số, trong đó khoảng cách là trọng số của các cạnh. Dưới dạng 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.

Giải pháp. Trong nhiệm vụ này, thật thuận tiện khi sử dụng ma trận khoảng cách S. Một 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à đỉnh cao j. Đối với biểu đồ hiển thị trong Hình. 12.1, ma trận khoảng cách có lượt xem tiếp theo:

. (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ệch tâm tối thiểu của các đỉnh. TRONG 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ị. Đếm đường kính d– độ lệch tâm tối đa của các đỉnh. Trong trường hợp này d= 3. Đỉnh số 1 và số 3 có độ lệch tâm như vậy, đây là ngoại 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. Trong đồ thị bậc cao hơn, có các đỉnh khác.

Độ lệch tâm của các đỉnh của đồ thị nhỏ có thể được tính dễ dàng bằng cách 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 thiết kế của nó. Ngoài ra, đồ thị có thể có size lớn. Vì vậy, cần có một cách khác để giải quyết vấn đề trước đó. Định lý sau đây đã được biết.

Định lý 12.4. Gọi là ma trận kề của đồ thị G không có vòng lặp và , trong đó . Khi đó bằng số đường đi có độ dài k từ đỉnh này sang đỉnh khá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 đồ thị ở hình 2. 12.1, sử dụng phương pháp đại số.

Giải pháp. Ma trận kề của đồ thị này bằng:

.

Chúng ta sẽ điền vào ma trận khoảng cách bằng cách xem xét bậc của ma trận kề. Đơn vị của ma trận kề hiển thị các cặp đỉnh có khoảng cách giữa chúng là 1 (tức là chúng được nối 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 các đỉnh 2 và 3, 1 và 4, v.v. có một số tuyến đường có độ dài 2 nhất định (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ự hiện diện của một tuyến đường và độ dài của nó rất quan trọng, như được biểu thị bằng phần tử khác 0 của cấp độ ma trận, không trùng với phần tử được ghi chú khi tính toán tuyến đường chiều dài ngắn hơn. Chúng ta đặt 2 vào các phần tử trống của ma trận khoảng cách và nhận được phép tính gần đúng tiếp theo:

.

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

Ở đoạn trước chúng tôi đã nhấn mạnh rằng ma trận kề $A$ được giới thiệu ở đó, hay chính xác hơn là ma trận kề đỉnh của đồ thị, đóng vai trò rất quan trọng. Vai trò cốt yếu trong lý thuyết đồ thị. Chúng tôi đã ghi nhận những ưu điểm của ma trận này - nó là bình phương bằng số các hàng của ma trận tỷ lệ $B$, tức là, theo quy luật, chứa số nhỏ hơn các phần tử. Thứ hai, ma trận này lưu trữ tất cả thông tin về các cạnh của đồ thị và với số đỉnh cho trước, mô tả duy nhất đồ thị. Ma trận kề, giống như ma trận tỷ lệ của đồ thị, là ma trận (0,1), tức là các phần tử của nó có thể được coi là các phần tử của các cấu trúc đại số khác chứ không chỉ là các phần tử của tập hợp số nguyên. Đặc biệt, chúng tôi lưu ý rằng các phần tử của ma trận kề có thể được coi là các phần tử của đại số Boolean, tuân theo các định luật số học Boolean, nhưng chưa giải thích chính xác điều này. Trước khi lấp đầy khoảng trống này, chúng ta hãy nhấn mạnh những ưu điểm của ma trận kề do tính bình phương của nó.

Để làm điều này, hãy nhớ lại các quy tắc nhân ma trận. Cho các ma trận tùy ý có các phần tử số: ma trận $A$ có chiều $n\times m$ có các phần tử $a_(ik)$ và ma trận $B$ có chiều $m\times q$ có các phần tử $b_(kj)$ . Ma trận $C$ có chiều $n\times q$ được gọi là tích của ma trận $A$ với $B$ (thứ tự quan trọng) nếu các phần tử $c_(ij)$ của nó được xác định như sau: $c_(ij ) = \sum\limits_( k = 1)^m (a_(ik) b_(kj))$. Tích của ma trận được viết theo cách thông thường $AB=C$. Như chúng ta có thể thấy, tích của ma trận đòi hỏi sự nhất quán về kích thước của thừa số thứ nhất và thứ hai (số cột của ma trận thừa số thứ nhất bằng số hàng của ma trận thừa số thứ hai). Yêu cầu này sẽ biến mất nếu chúng ta xét các ma trận vuông có cùng bậc và do đó, chúng ta có thể xét các lũy thừa tùy ý của ma trận vuông. Đây là một trong những lợi thế ma trận vuông trước hình chữ nhật. Một ưu điểm khác là chúng ta có thể đưa ra cách diễn giải đồ thị cho các phần tử bậc của ma trận kề.

Cho ma trận kề $A$ có dạng: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & (a_ (1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (... ) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(array) )) \right)$, và bậc $ k$ thứ của cô ấy — $A^k = \left(((\begin(array)(*c) (a_(11)^((k)) ) & (a_(12)^((k)) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & (. . .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^( ( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(array) )) \right)$ , trong đó $k = 2,3,...$ Rõ ràng, $A^k$, giống như ma trận $A$, sẽ là ma trận đối xứng.

Đặt $k=2$. Khi đó $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), và mỗi số hạng $a_(il) a_(lj)$ bằng $0$ hoặc $1$. Trường hợp khi $a_(il) a_(lj) = 1$ có nghĩa là có hai cạnh trong đồ thị: cạnh $\(i,l\)$ (vì $a_(il) = 1)$ và cạnh $\( l,j\)$ (vì $a_(lj) = 1$) và do đó đường dẫn $\(( \(i,l\), \(l,j\) )\)$ từ $i $- đỉnh thứ đến đỉnh $j$th có độ dài hai (một đường dẫn có hai cạnh). Ở đây chúng ta đang nói về một đường đi, không phải một chuỗi, vì hướng được chỉ ra là từ đỉnh thứ $i$ đến đỉnh thứ $j$. Do đó, $a_(ij)^((2))$ cho chúng ta số lượng tất cả các đường dẫn trên đồ thị (theo cách giải thích hình học của đồ thị) có độ dài 2 dẫn từ đỉnh $i$-th đến $j$ -quần què.

Nếu $k=3$, thì $A^3 = A^2A = AA^2 = AAA$ và $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_(l_1 l_2 ) a_(l_2 j) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

Thuật ngữ $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $ nếu nó bằng 1, xác định một đường đi có độ dài 3 đi từ đỉnh $i$-th đến $j$-th và đi qua các đỉnh $l_1$ và $l_2$. Sau đó $a_(ij)^((3))$ cung cấp cho chúng ta số đường đi có độ dài 3 nối các đỉnh $i$th và $j$th. TRONG trường hợp chung$a_(ij)^((k))$ chỉ định số lượng đường dẫn có độ dài $k$ nối các đỉnh $i$-th và $j$-th. Trong trường hợp này, $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

Rõ ràng là giá trị $a_(ii)^((k)) $ cho chúng ta số lượng đường đi khép kín có độ dài $k$ bắt đầu và kết thúc tại đỉnh $i$. Do đó, một đường đi có độ dài 2 - $a_(il) a_(li)$, có nghĩa là một đường đi dọc theo cạnh $\( i,l \)$ từ đỉnh $i$ đến đỉnh $l$ và ngược lại. Do đó $a_(ii)^((2)) = s_i$, tức là các phần tử đường chéo của ma trận $A^2$ bằng bậc của các đỉnh tương ứng.

Bây giờ chúng ta hãy xem xét, cùng với ma trận $A$, ma trận $\dot (A)$, khác với ma trận $A$ ở chỗ các phần tử của nó (các số 0 hoặc 1) được coi là các phần tử của đại số Boolean. Vì vậy, các hành động với ma trận như vậy sẽ được thực hiện theo các quy tắc của đại số Boolean. Vì các thao tác cộng, nhân các ma trận có các phần tử Boolean được rút gọn thành các thao tác cộng, nhân các phần tử của các ma trận này theo các quy tắc số học Boolean nên chúng tôi hy vọng rằng việc này sẽ không gây khó khăn. Ma trận có các phần tử Boolean sẽ được gọi là ma trận Boolean. Rõ ràng các phép tính cộng, nhân các ma trận Boolean đều khép kín trên tập hợp các ma trận Boolean, tức là kết quả của các phép toán này sẽ lại là ma trận Boolean.

Rõ ràng, đối với việc đánh số các đỉnh cho trước, có sự tương ứng một-một giữa ma trận kề kề Boolean và đồ thị. Do đó, việc giải thích biểu đồ về các hành động cộng và lũy thừa của ma trận kề Boolean rất đáng quan tâm (trong trường hợp tổng quát, tích của hai ma trận đối xứng cùng cấp không nhất thiết phải là ma trận đối xứng).

Kết quả của việc cộng hai ma trận đối xứng Boolean có cùng cấp sẽ là ma trận đối xứng Boolean có cùng cấp với các số 0 ở những nơi mà cả hai số hạng đều có số 0 và ma trận 1 ở những nơi có ít nhất một số hạng có một số một. Trong việc diễn giải đồ thị, thao tác này được gọi là thao tác phép cộng đồ thị. Tổng của hai đồ thị, cho trên cùng một tập các đỉnh có cùng số thứ tự, một đồ thị được gọi là có các đỉnh i và j không kề nhau nếu chúng không liền kề trong cả hai thành phần đồ thị và các đỉnh i và j liền kề nhau nếu chúng kề nhau tại ít nhất một thuật ngữ đồ thị.

Bây giờ chúng ta hãy diễn giải cấp độ thứ hai của ma trận kề Boolean $\dot (A)^2$ với các phần tử $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\dot ( a)_(il) \dot (a)_(lj) )$. Rõ ràng là $\dot (a)_(ij)^((2)) = 1$ nếu có ít nhất một số hạng $\dot (a)_(il) \dot (a)_(lj) $ bằng nhau đến 1 và $\dot (a)_(ij)^((2)) = 0$ nếu tất cả các số hạng bằng 0. Nếu ma trận $\dot (A)$ là ma trận kề của một số đồ thị, tức là. là ma trận đối xứng (0,1) có đường chéo chính bằng 0, thì ma trận $\dot (A)^2$, nói chung, không phải là ma trận kề của đồ thị theo nghĩa mà chúng ta chấp nhận, vì tất cả các phần tử đường chéo của nó đều bằng 1 (nếu đồ thị không có đỉnh cô lập). Để các ma trận như vậy có thể được coi là ma trận kề, khi xem xét các kết nối giữa các đỉnh của một hệ thống liên thông nào đó xác định hệ thống này là một đồ thị, chúng ta phải cho phép một số đỉnh được kết nối với chính chúng. Một “cạnh” xác định sự kết nối của một đỉnh nhất định với chính nó được gọi là vòng. Hơn nữa, như trước đây, theo từ biểu đồ, chúng tôi muốn nói đến biểu đồ không có vòng lặp và về biểu đồ có vòng lặp, nếu điều này không rõ ràng trong ngữ cảnh, chúng tôi sẽ nói như vậy - biểu đồ có vòng lặp.

Xét tổng $\dot (A)^() = \dot (A) + \dot (A)^2$. Ma trận $\dot (A)^()$ cho chúng ta một biểu đồ thu được từ biểu đồ ban đầu bằng cách "bão hòa" nó với các kết nối bổ sung tương ứng với các đường đi có độ dài 2. Nghĩa là, trong biểu đồ mới, các đỉnh $i$ và $ j$ là liền kề nếu chúng liền kề trong biểu đồ gốc hoặc các đỉnh này được kết nối bằng một đường dẫn nào đó có độ dài 2 và các đỉnh $i$ và $j$ không liền kề nếu chúng không liền kề trong biểu đồ gốc và ở đó không có đường đi nào có độ dài 2 nối các đỉnh này.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ được định nghĩa tương tự. Tức là trong đồ thị được cho bởi ma trận$\dot (A)^()$ các đỉnh $i$ và $j$ là liền kề nếu chúng liền kề trong đồ thị $\dot (A)^()$ hoặc các đỉnh này được kết nối bởi một đường đi có độ dài 3 trong đồ thị đồ thị gốc, và các đỉnh $i$ và $j$ là không liền kề nếu chúng không liền kề trong đồ thị $\dot (A)^()$ và không có đường đi có độ dài 3 nối các đỉnh này trong đồ thị gốc. Và như thế.

Nói chung, $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. Dễ dàng thấy rằng mọi $\dot (A)^([k])$ cho $k \ge n - 1$, trong đó $n$ là thứ tự của ma trận $\dot (A)$, đều bằng nhau với nhau. Thật vậy, nếu các đỉnh $i$ và $j$ được kết nối thì sẽ có một đường dẫn (chuỗi) kết nối các đỉnh này, và do đó, có một đường dẫn đơn giản (chuỗi đơn) kết nối các đỉnh này. Đường đi đơn giản tối đa có thể có trong đồ thị $n$-vertex có độ dài $n-1$ (một đường dẫn đơn giản kết nối tất cả các đỉnh riêng biệt của đồ thị). Do đó, nếu trong ma trận $\dot (A)^()$ có số 1 ở vị trí $(i,j)$, thì cũng ở vị trí đó trong ma trận $\dot (A)^([k] )$ tại $k \ge n - 1$ cũng sẽ bằng 1, vì ma trận $\dot (A)^()$ được đưa vào dưới dạng số hạng Boolean trong định nghĩa của ma trận $\dot (A)^([ k])$. Nếu trong ma trận $\dot (A)^()$ có số 0 thay thế cho $(i,j)$, thì điều này có nghĩa là không có chuỗi đơn giản nào trong biểu đồ nối $i$-th và $j $- các đỉnh, và do đó, không có chuỗi nào nối các đỉnh này cả. Điều này có nghĩa là trong trường hợp đang xem xét và trong ma trận $\dot (A)^([k])$ với $k \ge n - 1$ sẽ có 0 tại chỗ ($i$,$j)$. Đây là những gì tuyên bố của chúng tôi chứng minh về sự bằng nhau của tất cả các ma trận $\dot (A)^([k])$ cho $k \ge n - 1$ với ma trận $\dot (A)^()$ và do đó , với nhau.

Ma trận $\dot (A)^()$ được gọi ma trận bao đóng bắc cầu của ma trận$\dot (A)$, cũng như ma trận kề của bao đóng bắc cầu của đồ thị được xác định bởi ma trận $\dot (A)$. Rõ ràng ma trận bao đóng bắc cầu của một đồ thị liên thông sẽ là ma trận kề đồ thị hoàn chỉnh, I E. một ma trận vuông chỉ gồm một ma trận. Quan sát này cũng cho chúng ta một phương pháp để xác định tính kết nối của đồ thị: một đồ thị được kết nối khi và chỉ khi ma trận đóng bắc cầu của ma trận kề của nó chỉ bao gồm các ma trận (sẽ là ma trận của đồ thị hoàn chỉnh).

Ma trận đóng bắc cầu cũng cho phép chúng ta giải bài toán phân chia đồ thị thành các thành phần liên thông.

Bây giờ chúng ta hãy chỉ ra cách thủ tục đóng bắc cầu cho phép chúng ta xây dựng cái gọi là “ma trận khoảng cách”. Để làm điều này, chúng ta xác định khoảng cách giữa các đỉnh $i$ và $j$. Nếu các đỉnh $i$ và $j$ được kết nối thì khoảng cách giữa chúng ta gọi độ dài tối thiểu (theo số cạnh đi qua) đường đơn giản nối các đỉnh này; nếu các đỉnh $i$ và $j$ bị ngắt kết nối, thì chúng ta đặt khoảng cách bằng 0 (số 0 là phủ định của bất kỳ đường đi nào nối các đỉnh này). Với định nghĩa về khoảng cách này, khoảng cách giữa đỉnh và chính nó bằng 2 (độ dài của đường đi dọc theo cạnh và mặt sau). Nếu có một vòng lặp ở đỉnh thì khoảng cách giữa đỉnh và chính nó bằng 1.

Để xây dựng ma trận khoảng cách cho đồ thị đỉnh $n$ với ma trận kề $A$, ma trận này cho biết khoảng cách giữa hai đỉnh bất kỳ, chúng tôi đưa vào xem xét ma trận $A^(\(k\)) = A^ ([k]) - A^()$, trong đó $k = 2,3,...,n - 1$ và $A^(\(1\)) = A^() = A$. Việc không có dấu chấm phía trên ký hiệu ma trận cho thấy rằng chúng tôi coi ma trận $A^([k])$ ($k = 1,2,...,n - 1)$ là ma trận số (0,1), thu được một cách tự nhiên từ các ma trận $\dot (A)^([k])$ (bây giờ chúng ta coi các phần tử Boolean 0 và 1 là các số 0 và 1). Từ phương pháp xây dựng ma trận $A^([k])$ suy ra $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$) và do đó, $A^(\(k\))$ ($k = 1,2,...,n - 1$) là ma trận (0,1). Hơn nữa, ma trận $A^(\(2\))$ chỉ chứa 1 ở những vị trí mà các đỉnh được xác định bởi vị trí này (số hàng và số cột) được kết nối bằng một đường dẫn nào đó có độ dài bằng hai và không được kết nối bằng một đường dẫn ngắn hơn. con đường. Tương tự, $A^(\(3\))$ chỉ chứa 1 tại những vị trí mà các đỉnh được xác định bởi vị trí này được kết nối bằng một đường dẫn có độ dài ba và không được kết nối bởi bất kỳ đường dẫn nào có độ dài ngắn hơn, v.v. Do đó, ma trận $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ sẽ là ma trận khoảng cách cần thiết. Phần tử $d_(ij)$ của ma trận này sẽ bằng khoảng cách giữa các đỉnh $i$ và $j$. Khoảng cách giữa các đỉnh $u$ và $v$ cũng sẽ được ký hiệu là $d(u,v)$.

Bình luận. Thuật ngữ sản phẩm cụ thể $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ phần tử $a_(ij ) ^((k))$ của lũy thừa $k$-th của ma trận kề $A^k$ chỉ định một $(i,j)$-path cụ thể $i\(i,l_1\)l_1 \(l_1 , l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ từ đỉnh $i$ -th đến $j$-th. Chuỗi các đỉnh và cạnh liền kề nối chúng $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ còn được gọi là tuyến đường $(i,j)$-. Một tuyến đường khác với một chuỗi chỉ bao gồm các cạnh liền kề khác nhau ở chỗ tuyến đường đó cho phép các cạnh bằng nhau. Một tuyến đường đơn giản bao gồm nhiều đỉnh và cạnh liền kề khác nhau, tức là thực tế trùng khớp với một chuỗi đơn giản.

Rõ ràng là phần tử $d_(ij) $ của ma trận khoảng cách xác định độ dài của chuỗi tối thiểu nối đỉnh $i$th với đỉnh $j$th.

Chúng ta hãy xem xét các ví dụ về đồ thị được đưa ra trong Hình 1 và 2, ma trận kề và ma trận khoảng cách của chúng.

Hình 1 (Đồ thị $\Gamma _1$, ma trận kề $A_1$, ma trận khoảng cách $D_1$).
$A_1 = \left(((\begin(array)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(array) )) \right), $
$D_1 = \left(((\begin(array)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(mảng) )) \right) $

Cơm. 2 (Đồ thị $\Gamma _2$, ma trận kề $A_2$, ma trận khoảng cách $D_2$).
$A_2 = \left(((\begin(array)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0\ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end(array) )) \right)$,
$D_2 = \left(((\begin(array)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2\ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end(mảng) )) \right). $

Từ ma trận $D_1$ và $D_2$ người ta có thể dễ dàng xác định đường kính$d_1$ của đồ thị $\Gamma _1$ và $d_2$ của đồ thị $\Gamma _2$, là giá trị lớn nhất của các phần tử của các ma trận này. Vậy $d_1 = 3$, và $d_2 = 6$.

Ngoài ma trận khoảng cách, lý thuyết đồ thị còn xem xét các ma trận khác, các phần tử của ma trận này được xác định thông qua độ dài của đường đi. Chẳng hạn như vậy là ma trận truyền tải. TRONG ma trận truyền tải phần tử thứ $(i,j)$ bằng chiều dàiđường đi dài nhất (chuỗi dài nhất) từ đỉnh $i$th đến đỉnh $j$th, và nếu không có đường đi nào như vậy cả, thì theo định nghĩa về khoảng cách, $(i,j)$ phần tử thứ của ma trận truyền tải được đặt bằng 0.

Chúng tôi sẽ ghi chú ở cuối phần về các phương pháp xác định chuỗi tối thiểu và tối đa bằng cách sử dụng ma trận khoảng cách nối các đỉnh $i$-th và $j$-th trong biểu đồ.

Bây giờ hãy đưa ra một số định nghĩa khác của lý thuyết đồ thị liên quan đến khoảng cách giữa các đỉnh và được xác định dễ dàng từ ma trận khoảng cách.

Độ lệch tâm$e(v)$ của một đỉnh $v$ trong một đồ thị liên thông $\Gamma$ được định nghĩa là $d(u,v)$ lớn nhất trên tất cả các đỉnh $u$ trong $\Gamma$. Bán kính$r(\Gamma)$ là độ lệch tâm nhỏ nhất của các đỉnh. Lưu ý rằng độ lệch tâm lớn nhất bằng đường kính của đồ thị. Đỉnh $v$ được gọi là đỉnh trung tâm của đồ thị $\Gamma$ nếu $e(v) = r(\Gamma)$; trung tâmđồ thị $\Gamma$ là tập hợp tất cả các đỉnh trung tâm.

Vì vậy, đối với đồ thị $\Gamma _1$ từ Hình 1, độ lệch tâm của đỉnh 13 sẽ bằng 2 ($e(13) = 2$). Các đỉnh 3, 5 và 10 sẽ có cùng độ lệch tâm ($e(3) = e(5) = e(10) = 2$). Độ lệch tâm bằng 2 sẽ là nhỏ nhất đối với đồ thị $\Gamma _1$, tức là. $r(\Gamma _1) = 2$. Tâm của đồ thị $\Gamma _1$ sẽ bao gồm các đỉnh 3, 5, 10 và 13. Độ lệch tâm lớn nhất sẽ là 3 và sẽ bằng, như đã lưu ý ở trên, với đường kính của đồ thị $\Gamma _1$.

Đối với đồ thị $\Gamma _2$ từ Hình. 2, đỉnh 4 duy nhất sẽ có độ lệch tâm nhỏ nhất ($e(4) = r(\Gamma _2) = 3$). Do đó, tâm của đồ thị $\Gamma _2$ bao gồm một đỉnh 4. Đường kính của đồ thị $\Gamma _2$, như đã lưu ý ở trên, là 6.

Đồ thị $\Gamma _2$ là một cây và cấu trúc tâm của bất kỳ cây nào được mô tả bằng định lý dưới đây.

Định lý Jordan–Sylvester. Mỗi cây có một tâm gồm một đỉnh hoặc hai đỉnh liền kề.

Bằng chứng. Chúng ta hãy biểu thị bằng $K_1$ một đồ thị bao gồm một đỉnh cô lập và bằng $K_2$ một đồ thị bao gồm hai đỉnh được nối với nhau bằng một cạnh. Theo định nghĩa, chúng ta đặt $e(K_1) = r(K_1) = 0$. Khi đó định lý sẽ đúng với $K_1$ và $K_2$. Hãy chứng minh rằng bất kỳ cây $T$ nào cũng có các đỉnh ở tâm giống như cây $(T)"$ thu được từ $T$ bằng cách loại bỏ tất cả các đỉnh treo của nó. Rõ ràng là khoảng cách từ một đỉnh cho trước $u$ đến bất kỳ đỉnh nào đỉnh khác $v$ có thể đạt tới giá trị cao nhất chỉ khi $v$ là một đỉnh treo.

Do đó, độ lệch tâm của mỗi đỉnh của cây $(T)"$ nhỏ hơn chính xác một điểm so với độ lệch tâm của cùng một đỉnh trong $T$. Suy ra rằng các đỉnh của cây $T$ có độ lệch tâm nhỏ nhất trong $ T$ trùng với các đỉnh có độ lệch tâm nhỏ nhất trong $(T)"$, tức là tâm của các cây $T$ và $(T)"$ trùng nhau. Nếu tiếp tục quá trình loại bỏ các đỉnh treo, chúng ta sẽ thu được một dãy các cây có cùng tâm với tâm của $T$. Vì $T$ là hữu hạn, nhất thiết chúng ta sẽ đạt đến $ K_1$ hoặc $K_2$. Trong mọi trường hợp, tất cả các đỉnh của cây thu được theo cách này tạo thành tâm của cây, do đó bao gồm một hoặc hai đỉnh liền kề đỉnh. Chứng minh hoàn tất.

Bây giờ chúng ta hãy chỉ ra cách sử dụng ma trận khoảng cách, chẳng hạn, chúng ta có thể xác định chuỗi tối thiểu nối đỉnh 4 với đỉnh 8 trên đồ thị $\Gamma _1$. Trong ma trận $D_1$ phần tử $d_(48) = 3$. Hãy lấy cột thứ 8 của ma trận $D_1$ và tìm trong cột tất cả các phần tử của cột này bằng 1. Sẽ tìm thấy ít nhất một phần tử như vậy do tính liên thông của đồ thị $D_1$. Trên thực tế, sẽ có ba đơn vị như vậy ở cột thứ 8 và chúng nằm ở hàng thứ 5, 6 và 7. Bây giờ chúng ta hãy lấy hàng thứ 4 và xem các phần tử trong đó nằm ở cột thứ 5, 6 và 7. Các phần tử này sẽ lần lượt là 2, 3 và 3. Chỉ phần tử ở cột thứ 5 bằng 2 và cùng với 1, nằm ở vị trí (5,8), cho tổng 3. Điều này có nghĩa là đỉnh 5 được bao gồm trong chuỗi $\( \(4, ?\), \(? ,5\), \(5,8\) \)$. Bây giờ chúng ta lấy cột thứ 5 của ma trận và xem xét 1 của cột này. Đây sẽ là các phần tử nằm ở dòng thứ 3, 6, 7, 8, 10 và 13. Chúng ta quay lại dòng thứ 4 và thấy rằng chỉ tại giao điểm của cột thứ ba và dòng thứ 4 mới có số 1, kết hợp với số 1 tại chỗ (3,5) sẽ có tổng là 2. Do đó, chuỗi mong muốn sẽ là $\( \ (4,3\), \(3,5\), \(5,8\) \)$. Bây giờ nhìn vào Hình 1, chúng tôi tin chắc về tính đúng đắn của giải pháp tìm được.

Mặc dù về ma trận truyền tải sách giáo khoa hiện đại họ nói rằng “không có phương pháp hiệu quả nào để tìm các phần tử của nó”, hãy nhớ rằng bằng cách sử dụng ma trận tỷ lệ, chúng ta có thể tìm thấy tất cả các chuỗi nối một cặp đỉnh trong một biểu đồ được kết nối và do đó các chuỗi có độ dài tối đa.

Giả sử G(V,X) là một đồ thị giả và nối các đỉnh v và w (v¹w) của đồ thị này bằng một tuyến đường. Khi đó phải có một đường đi tối thiểu nối các đỉnh này. Chúng ta hãy biểu thị độ dài của tuyến đường này là d(v, w). Chúng ta cũng đặt d(v, v) =0 cho bất kỳ đỉnh vÎV nào; d(v, w) = ¥ nếu không có đường nối 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 Cn 2 .

Cho đồ thị G(V,X) được nối. Chúng ta hãy xác định các khái niệm sau đây cho nó:

Đếm đường kính: 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) = min r(v);

Trung tâm đồ thị: mọi đỉ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 tính số liệu của đồ thị.

Ví dụ. Tìm các đặc tính số liệu của đồ thị được cho bởi sơ đồ:

Hãy 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 biểu đồ này C 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 của đồ 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.

Tâm của đồ thị là v 2, v 3, v 4.

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

Đồ thị G(V, X) được gọi là được nạp nếu một hàm gọi là hàm trọng số được chỉ định trên tập hợp các cạnh của đồ thị, gán cho mỗi cạnh x ОХ của đồ thị một số nhất định l(x). Giá trị l(x) được gọi là độ dài cung.

Giá trị 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, mức tiêu thụ xăng, v.v.

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

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

Một tuyến đường 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 tối thiểu trong số tất cả các tuyến đường trong đồ thị G(V, X) từ đỉnh v đến đỉnh w.

Chúng ta hãy giới hạn bản thân ở những đồ 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

Hãy 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 nào cũng là một mạch đơn giản.

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

Cho đồ thị G(V,X) được nạp, số đỉnh n ³ 2, cần xây dựng đường đi tối thiểu từ v 1 đến v n .

Hãy trình bày 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. Với mỗi đỉnh không tô 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 đỉnh mà a(v j) nhỏ nhất. Đồng thời tô màu cạnh dẫn đến đỉnh đã 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 là 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 không thể thực hiện được nếu tất cả a(v j)= ¥. Trong trường hợp này, đỉnh v n không thể chạm tới được.

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

Bước 1. Tô màu đỉnh v 1 . Hãy gán chỉ số cho các đỉnh: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Chúng ta giả sử v 1 = v.

a(v 2) = phút (¥, 0+4) = 4,

a(v 3) = phút (¥, 0+7) = 7,

a(v 4) = phút (¥, 0+3) = 3,

a(v 5) = phút (¥, 0+¥) = ¥,

a(v 6) = phút (¥, 0+¥) = ¥.

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, giả sử v = v 4 .

a(v 2) = phút (4, 3+¥) = 4,

a(v 3) = phút (7, 3+¥) = 7,

a(v 5) = phút (¥, 3+3) = 6,

a(v 6) = phút (¥, 3+¥) = ¥.

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 chúng ta thực hiện bước 2, giả sử v = v 2.

a(v 3) = phút (7, 4+3) = 7,

a(v 5) = phút (6, 4+2) = 6,

a(v 6) = phút (¥, 4+¥) = ¥.

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, giả sử v = v 5 .

a(v 3) = phút (7, 6+¥) = 7,

a(v 6) = phút (¥, 6+2) = 8.

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, giả sử v = v 3 .

a(v 6) = phút (8, 7+2) = 8.

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 ta ngừng làm việc. Chúng ta đã thu được một tuyến đường tối thiểu v 1 v 4 v 5 v 6 , độ dài của tuyến đường này là 8 .

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

4. Vấn đề về cây

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

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

Cây là một đồ thị tuần hoàn được kết nối.

Cho là đồ thị vô hướng liên thông. Vì hai đỉnh bất kỳ của đồ thị và được kết nối với nhau nên có các chuỗi đơn giản có đầu và . Có thể có một số chuỗi như vậy. Độ dài của chúng là số nguyên không âm. Do đó, giữa các đỉnh và phải tồn tại đơn giản chiều dài chuỗi ngắn nhất. Độ dài của chuỗi ngắn nhất nối các đỉnh và được ký hiệu bằng ký hiệu và được gọi là khoảng cách giữa các đỉnh và . A-Prior .

Thật dễ dàng để xác minh rằng khái niệm khoảng cách được đưa ra theo cách này thỏa mãn các tiên đề của thước đo:

2. nếu và chỉ nếu ;

3. ;

4. Bất đẳng thức tam giác đúng:

Đối với một đỉnh cố định của đồ thị, khoảng cách đến đỉnh xa nhất của đồ thị là: , gọi điện độ lệch tâm (tối đa xóa) đỉnh.

Đường kínhđồ thị được gọi là một số, bằng khoảng cách giữa các đỉnh của đồ thị cách xa nhau nhất:

.

Một chuỗi đơn giản có độ dài bằng nhau được gọi là đường kính xích. Rõ ràng, đường kính của đồ thị bằng độ lệch tâm lớn nhất trong số tất cả các độ lệch tâm của các đỉnh của đồ thị. Đỉnh được gọi là ngoại vi, Nếu như .

Độ lệch tâm nhỏ nhất của các đỉnh của đồ thị liên thông được gọi là bán kính và biểu thị:

Vì đường kính của đồ thị bằng độ lệch tâm lớn nhất của các đỉnh và bán kính bằng nhỏ nhất nên bán kính của đồ thị không thể lớn hơn đường kính của nó. Đỉnh được gọi là trung tâm, Nếu như . Tập hợp tất cả các đỉnh ở tâm của đồ thị được gọi là trung tâm. Tâm của đồ thị có thể là một đỉnh hoặc nhiều đỉnh. Có những đồ thị có tâm trùng với tập hợp tất cả các đỉnh của nó. Ví dụ, tâm của một chuỗi đơn giản bao gồm hai đỉnh khi số đỉnh của nó là số chẵn và một đỉnh khi số của nó là số lẻ, và đối với bất kỳ chu trình nào, tất cả các đỉnh đều là trung tâm.

Để minh họa, chúng ta hãy nhìn vào biểu đồ trong Hình. 4.29. Đây

Đó là lý do tại sao

Đỉnh 2 là tâm của đồ thị và tất cả các đỉnh khác của nó đều là ngoại vi. Chuỗi 1, 2, 3 là một trong những chuỗi đường kính.

Đối với một đồ thị liên thông, khoảng cách giữa các đỉnh và được định nghĩa là khoảng cách giữa các đỉnh và trong bản sao vô hướng của đồ thị này.

Bài toán tìm đỉnh tâm của đồ thị thường xuyên gặp phải trong hoạt động thực tế. Ví dụ: giả sử các đỉnh của đồ thị tương ứng với các ngôi làng nhỏ và các cạnh của nó tương ứng với các con đường giữa chúng. Cần phải bố trí tối ưu theo những điều này khu định cư, ví dụ, các cửa hàng. TRONG tình huống tương tự Tiêu chí tối ưu thường bao gồm việc tối ưu hóa trường hợp “xấu nhất”, tức là giảm thiểu khoảng cách từ cửa hàng đến ngôi làng xa nhất. Phương pháp tối ưu hóa này liên quan đến việc đặt các cửa hàng tại các ngôi làng đại diện cho các đỉnh trung tâm của biểu đồ.

Truyền tải đồ thị

Người ta đã lưu ý rằng sự khởi đầu của lý thuyết đồ thị gắn liền với bài toán về những cây cầu Königsberg. Nhiệm vụ này, nổi tiếng vào thời đó, như sau. Bảy cây cầu của thành phố Koenigsberg (nay là Kaliningrad) nằm trên sông Pregel như trong Hình 2. 4h30. Nhiệm vụ là phải rời khỏi nhà và quay trở lại, chỉ qua mỗi cây cầu một lần.

Vì chỉ có các cầu vượt là có ý nghĩa trong bài toán, nên sơ đồ thành phố có thể được rút gọn thành hình ảnh của một biểu đồ (chính xác hơn là một đồ thị đa giác), trong đó các cạnh tương ứng với các cây cầu và các đỉnh tương ứng với các phần được chia khác nhau của thành phố, được biểu thị bằng các chữ cái (Hình 4.30, bên phải). Euler đã chỉ ra rằng không thể đi bộ qua tất cả các cây cầu ở Königsberg một lần rồi quay trở lại. Trong công trình xuất bản năm 1736, ông đã xây dựng và giải quyết các vấn đề sau: vấn đề thường gặp lý thuyết đồ thị: trong những điều kiện nào một đồ thị liên thông chứa một chu trình đi qua mỗi cạnh của nó.

Một chu trình trong đồ thị được gọi là Euler, nếu nó chứa tất cả các cạnh của đồ thị. Đồ thị liên thông chứa chu trình Euler được gọi là Eulerđếm. Một biểu đồ như vậy có thể được vẽ mà không cần nhấc bút chì ra khỏi giấy và không lặp lại các đường nét.

Ví dụ: biểu đồ hiển thị trong Hình. Hình 4.31 là Euler vì nó chứa chu trình Euler 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. Đồ thị này còn có các chu trình Euler khác. Rõ ràng là hai chu trình bất kỳ như vậy chỉ khác nhau ở thứ tự chúng đi qua các cạnh.

Định lý 4.7.(L. Euler, 1736 .) Một đồ thị liên thông là Euler khi và chỉ nếu bậc của tất cả các đỉnh của nó là chẵn.

Chuỗi được gọi là Euler, nếu nó chứa tất cả các cạnh của đồ thị.

Định lý 4.8(L. Euler, 1736 .) Một đa đồ thị có một xích Euler khi và chỉ khi nó liên thông và số đỉnh bậc lẻ là 0 hoặc 2.

Bất chấp sự “tương tự” trong định nghĩa của chu trình Euler và chu trình Hamilton, các lý thuyết tương ứng thiết lập tiêu chí tồn tại và thuật toán tìm kiếm cho các chu trình đó có rất ít điểm chung. Định lý Euler (Định lý 4.7) giúp dễ dàng xác định xem một đồ thị có phải là Euler hay không. Các thuật toán đã được phát triển giúp dễ dàng tìm chu trình Euler của đồ thị Euler. Đối với đồ thị Hamilton, tình hình ở đây khác biệt đáng kể. Thông thường rất khó trả lời câu hỏi liệu một đồ thị nào đó có phải là đồ thị Hamilton hay không. Tiêu chí chung, tương tự như tiêu chuẩn Euler, không có ở đây. Nhưng hóa ra, trong tập hợp tất cả các đồ thị, có rất ít đồ thị Euler nhưng lại có khá nhiều đồ thị Hamilton.