Luận án Nghiên cứu các thuật toán rút gọn đồ thị và ứng dụng để phát hiện cộng đồng trên mạng xã hội

0 (2.4) 
46 
(ii) CB(e) = (|V| - 1) (2.5) 
Chứng minh. 
(i) Vì v là đỉnh treo nên σst(v) = 0, theo công thức (2.1) thì CB(v) = 0 
(ii) G là liên thông nên với mọi v’ ∈ V - {v} đều có đường đi tới v, nghĩa là có 
đường đi ngắn nhất giữa v và v’. Vì v là đỉnh treo của đồ thị nên mọi đường đi 
ngắn nhất giữa chúng đều đi qua e = (v, w). Theo định nghĩa độ đo trung tâm 
trung gian của cạnh thì CB(e) = (|V| - 1). n 
Định nghĩa 2.2. Cho trước đồ thị vô hướng liên thông G = (V, E) với u, w Î V là hai 
đỉnh treo, u tương đương bậc 1 với w, ký hiệu u »1 w khi và chỉ khi chúng cùng liền 
kề với v (N(u) = N(w) = {v}), N(u) là tập các đỉnh lân cận của u. [84] 
Dễ nhận ra quan hệ »1 là quan hệ tương đương. Ta ký hiệu V1 là tập tất cả các 
đỉnh treo của đồ thị G thì: V1 = { u Î V | deg(u) = 1}. 
V1/»1 sẽ tạo ra các lớp các đỉnh treo tương đương với nhau, V1/»1 = {C1, C2, 
, Ck}. Những đỉnh treo cùng liền kề với một đỉnh sẽ cùng lớp tương đương và 
chúng có cùng bậc 1 và cùng độ đo trung tâm trung gian là 0. 
Như vậy, u »1 w thì u, w Î Ci, i = 1..k và deg(u) = deg(w) = 1, CB(u) = CB(w) = 0. 
Ví dụ 2.1. Xét đồ thị vô hướng liên thông G sau: 
Hình 2.1. Đồ thị vô hướng liên thông G 
Như trên đã phân tích, tất cả các đỉnh treo đều có độ đo trung tâm trung gian bằng 0, 
nghĩa là: 
 CB(1) = CB(2) = CB(3) = CB(10) = CB(11) = CB(12) = 0 
47 
Đỉnh số 4 có 3 đỉnh treo liền kề, N(4) = {1, 2, 3}, 1 »1 2 »1 3, tương tự N(9) = {10, 
11} và 10 »1 11. 
Nhiệm vụ chính là tính độ đo trung tâm trung gian của các đỉnh trên đồ thị, nên 
việc kết hợp những đỉnh tương đương với nhau (về độ đo trung tâm trung gian) thành 
một đỉnh đại diện cho những lớp có số phần tử lớn hơn hoặc bằng 2, sẽ làm giảm 
đáng kể các đỉnh cần tính độ đo trung tâm trung gian. Sau khi kết hợp tất cả những 
đỉnh tương đương của lớp Ci, | Ci | ³ 2, i = 1..k, thành đỉnh đại diện C’i (cũng là đỉnh 
treo), ta nhận được đồ thị G1 = (V1, E1), trong đó: 
• V1 = V - V1 È {C’1, C’2, , C’k} (*) 
• E1 = E - {(u, v) | u Î V1, v = N(u)} È {(v, C’i) | i = 1..k, v = N(u) với u Î Ci} 
Đồ thị G1 nhận được từ đồ thị G sau khi loại bỏ đi những đỉnh treo tương đương 
với nhau và các cạnh liền kề với chúng, thay thế bằng một đỉnh có tên trùng với tên 
của lớp và một cạnh liền kề với một đỉnh đại diện cho mỗi lớp tương đương. 
Ví dụ 2.2. Xét đồ thị G từ ví dụ 2.1 có V = {đỉnh 1, đỉnh 2, , đỉnh 12}, ta thấy các đỉnh 1, 
đỉnh 2, đỉnh 3 là các đỉnh treo liền kề với đỉnh 4, do vậy chúng tương đương bậc 1 với nhau. 
Tương tự, đỉnh 10, đỉnh 11 liền kề với đỉnh 9 và tương đương bậc 1 với nhau. Ở đồ thị này 
có 2 lớp tương đương bậc 1 có nhiều hơn 1 phần tử là: C1 = {đỉnh 1, đỉnh 2, đỉnh 3}, C2 = 
{đỉnh 10, đỉnh 11}. Kết hợp các đỉnh treo tương đương của, ta có đồ thị G1. 
Hình 2.2. Đồ thị G1 kết hợp các đỉnh treo tương đương 
48 
Ví dụ 2.3. Các mạng xã hội có nhiều đỉnh treo tương đương [22], [83]. 
Hình 2.3. Minh họa các mạng xã hội xuất hiện nhiều đỉnh treo 
Để chứng minh rằng được độ đo trung tâm trung gian của các đỉnh trong đồ thị 
G1 cũng chính là độ đo trung tâm trung gian của các đỉnh trên đồ thị G ban đầu, nghĩa 
là đồ thị rút gọn bảo toàn độ đo trung tâm trung gian của các đỉnh, ta sử dụng các tính 
chất sau: 
Tính chất 2.2. Với mọi đỉnh treo u Î V hay deg(u) = 1, v Î V là đỉnh liền kề với 
đỉnh u. Tập các đỉnh treo liền kề với v ký hiệu N1(v) = { w Î V | (w, v) Î E, deg(w) = 
1}. Khi đó, ta có các tính chất sau: 
(i) dut = dvt, với mọi t Î V - {u, v} (2.6) 
(ii) dut(w) = dvt(w), với mọi w Î V - {sÎ V| deg(s) = 1}, t Î V - {u, v, w} (2.7) 
(iii) tut(v) = 1, với mọi đỉnh t Î V - {u, v} (2.8) 
(iv) CB(v)=|N1(v)|*(|N1(v)|-1)/2+|N1(v)|*|V-{v}-N1(v)|∑ ~s(8)~s@B8B9∈:3jn(8) (2.9) 
Chứng minh. 
(i) u là đỉnh treo và liền kề với v, nên mọi đường đi từ u đến t đều phải đi qua v, 
nên dut(v) = duv * dvt = dvt, vì duv = 1 (deg(u) = 1). 
(ii) u là đỉnh treo và liền kề với v, nên mọi đường đi từ u đến t đều phải đi qua v, 
nên dut(w) = duv * dvt(w) = dvt(w) vì duv = 1. 
(iii) Mọi đường đi ngắn nhất đi từ đỉnh treo u (deg(u) = 1) đến t Î V - {u, v} (những 
đỉnh còn lại của đồ thị) đều phải đi qua đỉnh liền kề với u là v, vậy suy ra dut(v) 
= dut, nghĩa là tut(v) = 1. 
49 
(iv) N1(v) là tập các đỉnh treo liền kề với v. Nếu |N1(v)| > 1 thì giữa 2 đỉnh treo liền 
kề với v sẽ có 1 đường đi ngắn nhất đi qua v. Khi đó ta có: 
|N1(v)|*(|N1(v)|-1)/2| đường đi ngắn nhất giữa 2 đỉnh treo liền kề với v và đi qua 
v. Với mỗi đỉnh treo u liền kề với v, tiếp tục dựa vào tính chất 2.2 (i) ta có: |V- 
{N1(v), v}| đường đi ngắn nhất đi từ u tới những đỉnh còn lại. Đỉnh v có |N1(v)| 
đỉnh treo liền kề, do vậy sẽ có |N1(v)|*|V- {u, v}| đường đi ngắn nhất từ các đỉnh 
treo liền kề với v, đi qua v để đến những đỉnh còn lại của đồ thị. Còn lại, ∑ ~s(8)~s@B8B9,@,9∈:3jn(8) là tổng các độ phụ thuộc các cặp đỉnh còn lại (V- 
{N1(v)}- {v}) vào v (đi qua v). n 
Tính chất 2.3. Giả sử G1 là đồ thị rút gọn của đồ thị G sau khi kết hợp đỉnh tương 
đương bậc một. Ta có tính chất sau: 
(i) tst(v) = |Ci| * tut(v) nếu s = C’i, i = 1..k, u = N(C’i), v≠tÎ V1 - {u, C’i} (2.10) 
(ii) tst(v) = |Ci| * tsw(v) nếu t = C’i, i = 1..k, w = N(C’i), v≠tÎ V1 - {w, C’i} (2.11) 
(iii) tst(v) = |Ci| * |Cj| * tuw(v) nếu s = C’i, t = C’j, i, j = 1..k, u = N(C’i), w = N(C’j), 
v Î V1 - {u, w, C’i , C’j} (2.12) 
Chứng minh. 
(i) Đỉnh đầu s = C’i đại diện cho lớp tương đương có |Ci| ³ 2 phần tử. Vì s cũng là 
đỉnh treo, nên mọi đường đi ngắn nhất từ s = C’i đến t qua v đều phải đi qua một 
đỉnh liền kề của s là u. Trên đồ thị G1, mỗi đỉnh C’i sẽ đại diện cho |Ci| đỉnh treo 
tương đương ở đồ thị G, nên số đường đi ngắn nhất từ s đến t qua v: tst(v) sẽ 
tương ứng với |Ci| * tut(v). 
(ii) Đỉnh cuối t = C’i đại diện cho lớp tương đương có |Ci| ³ 2 phần tử. Vì t cũng là 
đỉnh treo, nên mọi đường đi ngắn nhất từ s đến t = C’i qua v đều phải đi qua một 
đỉnh liền kề (tiền tố) của t là w. Trên đồ thị G1, mỗi đỉnh C’i sẽ đại diện cho |Ci| 
đỉnh treo tương đương ở đồ thị G, nên số đường đi ngắn nhất từ s đến t qua v: 
tst(v) = |Ci| * tsw(v). 
(iii) Trường hợp đỉnh đầu s = C’i đại diện cho lớp tương đương có |Ci| ³ 2 phần tử 
và đỉnh cuối t = C’j đại diện cho lớp tương đương có |Cj| ³ 2 phần tử. Vì s, t 
50 
cũng đều là đỉnh treo, nên mọi đường đi ngắn nhất từ s = C’i đến t qua v đều 
phải đi qua một đỉnh liền kề (hậu tố) của s là u và phải đi qua một đỉnh liền kề 
(tiền tố) của t là w. Trên đồ thị G1, mỗi đỉnh C’i sẽ đại diện cho |Ci| đỉnh treo 
tương đương và mỗi đỉnh C’j sẽ đại diện cho |Cj| đỉnh treo tương đương ở đồ thị 
G, nên số đường đi ngắn nhất từ s đến t qua v: tst(v) = |Ci| * |Cj| * tuw(v). n 
2.2.2. Các lớp đỉnh sườn tương đương 
Mục này đề xuất một số các tính chất, hệ quả về lớp đỉnh sườn tương đương 
trên đồ thị làm cơ sở để thực hiện thuật toán kết hợp lớp đỉnh sườn tương đương về 
độ đo trung tâm trung gian thành một đỉnh đại diện bảo toàn độ đo trung tâm trung 
gian, nhằm giảm thiểu không gian tính toán của đồ thị mạng xã hội. Các tính chất sau 
khẳng định độ đo trung tâm trung gian của các đỉnh đại diện trong đồ thị rút gọn cũng 
chính là độ đo trung tâm trung gian của các đỉnh trong lớp tương đương trên đồ thị 
ban đầu. 
Định nghĩa 2.3. Cho đồ thị vô hướng, liên thông G = (V, E), u Î V được gọi là đỉnh 
sườn (Side vertex) [84] của G nếu đồ thị con sinh bởi tập các đỉnh liền kề N(u) là 
clique (đồ thị con đầy đủ). 
Ở đây, ta chỉ xét những đỉnh sườn có |N(u)| ³ 2, vì trường hợp ngược lại, |N(u)| 
= 1 thì u là đỉnh treo đã được nghiên cứu ở trên. 
Nhận xét 2.1. Nếu u là đỉnh sườn và G không phải là clique thì chắc chắn có ít nhất 
một đỉnh v Î N(u) có bậc khác với bậc của đỉnh sườn u (deg(v) > deg(u)) trên đồ thị 
G. 
Ký hiệu G(u) = {u} È N(u) là tập các đỉnh liền kề với u và kể cả u. 
Nhận xét 2.2. Đồ thị con sinh bởi G(u) cũng là clique, vì bản thân N(u) đã sinh ra là 
clique, và u lại liền kề với tất cả các đỉnh của N(u). 
G1(u) = { v Î G(u) | deg(v) = deg(u)} - Tập những đỉnh có cùng bậc với đỉnh 
sườn u trong clique sinh bởi G(u). 
Nhận xét 2.3. Nếu G không phải là clique thì G2(u) = G(u) - G1(u) ≠ f, nghĩa là chắc 
chắn có ít nhất một đỉnh v Î G2(u) trên clique sinh bởi N(u) (hay G(u)) có bậc khác 
với bậc của đỉnh sườn (deg(v) > deg(u)). 
51 
Để thực hiện thuật toán tính độ đo trung tâm trung gian của các đỉnh trên đồ thị 
một cách hiệu quả, người ta thường sử dụng phương pháp duyệt theo chiều rộng BFS 
(Breadth-First Search) [55]. Thuật toán duyệt theo chiều rộng tìm kiếm các đường đi 
ngắn nhất từ đỉnh gốc qua các cạnh tới tất cả các đỉnh khác trong đồ thị. Các cạnh 
giữa các mức của quá trình duyệt BFS bắt đầu từ đỉnh gốc X sẽ tạo thành đồ thị định 
hướng, phi chu trình, được gọi DAGX. 
Tính chất 2.4. Nếu u là đỉnh sườn của đồ thị G = (V, E), thì u hoặc là gốc hoặc là lá 
trên cây DAG duyệt theo chiều rộng (BFS). 
Chứng minh. 
Giả sử u không phải là đỉnh gốc và cũng không phải là lá trên cây DAG duyệt 
theo BFS. Vì u là đỉnh trong trên DAG, nên có đường đi ngắn nhất đi qua u. Mọi 
đường đi ngắn nhất từ gốc đi qua đỉnh u thì phải đi qua ít nhất hai đỉnh v, w liền kề 
với đỉnh u. Khi u là đỉnh sườn, theo định nghĩa thì N(u) là clique, nghĩa là (v, w) Î 
E, với mọi v, w liền kề với u. Khi đó đường đi qua u không phải đường đi ngắn nhất 
trên DAG, điều này mâu thuẫn với tính chất là mọi đường đi trên DAG là đường đi 
ngắn nhất. n 
Tính chất 2.5. Giả sử S là tập các đỉnh sườn tương đương, S = {v1, v2, , vh} và nếu 
chọn một đỉnh sườn vi, i = 1..h, làm gốc để duyệt BFS, thì h-1 đỉnh còn lại đều là lá 
có độ dài từ gốc là 2 và độ đo trung tâm trung gian của các cạnh liền kề của đỉnh sườn 
với các đỉnh liền kề tương ứng trên DAGvi là như nhau, CB((v, vj)) = 1/ |N(S)|, với 
mọi j ≠ i, v Î N(S). 
Chứng minh. 
Theo giả thiết, các đỉnh vi, i = 1..h, là các đỉnh sườn tương đương, chúng có 
cùng tập các đỉnh liền kề N(S) = N(vi), i = 1..h. Khi lấy một đỉnh vi để duyệt BFS, 
thì có |N(S)| đỉnh liền kề với vi đều ở mức 1 (có khoảng cách tới gốc là 1), đồng thời v 
Î N(S) lại là cha của tất cả các đỉnh sườn tương đương còn lại vj (ở mức 2), nghĩa là vj 
sẽ có |N(S)| đỉnh cha, và do vậy, tỷ số đường đi ngắn nhất từ vi (đỉnh gốc) đến các đỉnh 
sườn tương đương khác trên DAGvi và đi qua mỗi cạnh (v, vj) là 1 / |N(S)|. n 
52 
Tính chất 2.6. Giả sử S là tập các đỉnh sườn tương đương, S = {v1, v2, , vh} và 
N(S) = N(vi), i = 1..h, thì độ đo trung tâm trung gian của các cạnh nối đỉnh sườn với 
các đỉnh liền kề tương ứng là như nhau: CB((vi, v)) = CB((vj, v)), với mọi vi, vj Î S, v 
Î N(S). 
Chứng minh. 
Theo giả thiết, các đỉnh vi, i = 1..h là các đỉnh sườn tương đương, nên chúng có 
cùng tập các đỉnh liền kề N(S) = N(vi), i = 1..h. Khi đó, với mọi đỉnh v Î N(S), đều 
có cạnh ei = (vi, v) Î E, với mọi i = 1..h. Theo tính chất 2.4 mọi đỉnh sườn chỉ có thể 
là đỉnh gốc hoặc là đỉnh lá trên các DAG, suy ra CB(ei) = CB(ej), với mọi i, j = 1..h. 
 n 
Tính chất 2.7. Giả sử S là tập các đỉnh sườn tương đương, S = {v1, v2, , vh} và 
N(S) = N(vi), i = 1..h. Khi đó các đồ thị DAGv duyệt theo BFS, với mọi v Î S đều có 
chung một đồ thị con sinh bởi tập đỉnh VS = V - S. 
Đồ thị con sinh chung của DAGv, v Î S, là đồ thị thu được từ DAGv, sau khi bỏ 
đi các đỉnh sườn tương đương S cùng các cạnh liên thuộc với chúng. Đồ thị chung 
này có thể không liên thông. 
Tính chất 2.8. Nếu u là đỉnh sườn của đồ thị G, thì 
(i) dst(v) = 0, với mọi v Î G1(u), s ≠ u ≠ t Î V (2.13) 
(ii) CB(v) = 0, với mọi v Î G1(u) (2.14) 
Chứng minh. 
(i) Trường hợp s ≠ v ≠ t Î V, mọi đường đi ngắn nhất đi qua một đỉnh u thì chúng 
phải đi qua ít nhất 2 đỉnh v, w liền kề với đỉnh u. Khi u là đỉnh sườn, theo định 
nghĩa thì N(u) là clique, nghĩa là (v, w) Î E. Theo các tính chất của đường đi 
ngắn nhất thì dvw(u) = 0 vì dG( v, w) < dG( v, u) + dG( u, w). Như vậy ta có 
dst(u) = dsv * dvw(u) * dwt = 0. 
(ii) Như nhận xét ở trên thì đồ thị con sinh bởi G(u) là clique và deg(v) = deg(u), nên 
theo tính chất của đường đi ngắn nhất và tính chất 2.8 (i) suy ra dst(v) = 0, với mọi 
v Î G1(u). n 
53 
Định nghĩa 2.4. Cho u, v Î V, có quan hệ »2 với nhau, ký hiệu u »2 v khi và chỉ khi 
u, v là hai đỉnh sườn của G và N(u) = N(v). [84] 
Nhận xét: Quan hệ »2 là quan hệ tương đương. 
Từ định nghĩa và tính chất 2.8 suy ra, u »2 v thì deg(u) = deg(v) = |N(u)| - 1| và CB(u) 
= CB(v) = 0. 
Ví dụ 2.4. Xét đồ thị G được cho như trong Hình 2.4 dưới đây. 
Hình 2.4. Đồ thị G có các đỉnh sườn tương đương 
Các đỉnh 1, 2 là hai đỉnh sườn tương đương, 1 »2 2, bởi N(1) = N(2) = {3, 4, 5} 
và đồ thị con sinh bởi {3, 4, 5} là clique. Ngoài ra, các đỉnh 6, 8, 9, 10, 11 cũng là 
các đỉnh sườn vì đồ thị con sinh bởi tập liền kề với chúng cũng đều là clique (2 đỉnh 
có 1 cạnh nối với nhau), trong đó 6 »2 8, bởi N(6) = N(8) = {7, 9}. 
Những đỉnh sườn tương đương có thể kết hợp thành một đỉnh đại diện để rút gọn 
số đỉnh sườn tương đương trên đồ thị. Giả sử G = (V, E) có các lớp đỉnh sườn tương 
đương Si, i = 1..h, mỗi lớp có ít nhất 2 đỉnh sườn tương đương với nhau. Kết hợp 
những đỉnh tương đương trong cùng lớp thành một đỉnh sườn đại diện, ta nhận được 
đồ thị G2 = (V2, E2), trong đó: 
• V2 = V - V2 È {S’1, S’2, , S’h}, với V2 = S1 È S2 È  È Sh. (**) 
• E2 = E - {(u, v) | u Î V2, v Î N(u)} È {(v, S’i) | i = 1..h, v Î N(u) với u Î Si} 
Ví dụ 2.5. Đồ thị mạng xã hội câu lạc bộ Karate của Zachary [31] xuất hiện các đỉnh 
sườn tương đương. 
54 
Hình 2.5. Đồ thị mạng xã hội câu lạc bộ karate của Zachary xuất hiện nhiều 
đỉnh sườn. 
 Trên đồ thị mạng xã hội câu lạc bộ karate của Zachary [31] gồm có 34 đỉnh và 
68 cạnh thì đỉnh số 18 và đỉnh số 22 là những đỉnh sườn và chúng có thể kết hợp với 
nhau thành một đỉnh đại diện. Tương tự như vậy các đỉnh số 15, đỉnh số 16, đỉnh số 
19, đỉnh số 21 và đỉnh số 23 cũng là những đỉnh sườn tương đương và chúng có thể 
kết hợp với nhau thành một đỉnh đại diện duy nhất. Như vậy có thể kết hợp các đỉnh 
sườn tương đương ta thu được đồ thị mạng xã hội rút gọn gồm 29 đỉnh và 58 cạnh đã 
giảm 5 đỉnh và 10 cạnh so với đồ thị mạng xã hội ban đầu. 
Để chứng minh được độ đo trung tâm trung gian của các đỉnh trong đồ thị G2 
rút gọn cũng chính là độ đo trung tâm trung gian của các đỉnh trên đồ thị G ban đầu, 
nghĩa là đồ thị rút gọn bảo toàn độ đo trung tâm trung gian của đồ thị ban đầu, ta sử 
dụng các tính chất sau: 
Tính chất 2.9. Giả sử G2 là đồ thị rút gọn của đồ thị G sau khi kết hợp các đỉnh sườn 
tương đương của các lớp Si thành một đỉnh đại diện S’i, i = 1..h. Ký hiệu G2(S’i) = 
G2(u), với u Î Si. Ta có tính chất sau: 
(i) t€U9 (v) = |Si| * dut, uÎ G2(S’i), i =1..h, u = v, t Ï {u, S’1, S’2, , S’h} (2.15) 
(ii) t€U9 (v) = |Si| * tut(v), uÎG2(S’i), i = 1..h, u ≠ v, t Ï {u, v, S’1, S’2, , S’h. (2.16) 
55 
(iii) t@€U (v) = |Si|*dsw, wÎ G2 (S’i), i = 1..h, w = v, s Ï {v, S’1, S’2, , S’h} (2.17) 
(iv) t@€U (v) = |Si|*tsw(v), wÎ G2 (S’i), i =1..h, v ≠ w, s Ï {w, S’1, S’2, , S’h} 
 (2.18) 
(v) t€U	€V(v)=|Si|*|Sj|*t‚	ƒ(𝑣), uÎG2(S’i), wÎG2(S’j), i, j =1..h, vÏ{u,w,S’i,S’j} 
(2.19) 
Chứng minh. 
(i) Đỉnh đầu s = S’i đại diện cho lớp tương đương có |Si| ³ 2 phần tử. Vì s cũng là 
đỉnh sườn, nên mọi đường đi ngắn nhất từ s = S’i đến t qua v đều phải đi qua 
một đỉnh liền kề của s là u, u Î G2 (S’i), u không phải là đỉnh sườn. Trên đồ thị 
G2, mỗi đỉnh S’i sẽ đại diện cho |Si| đỉnh sườn tương đương ở đồ thị G, nên số 
đường đi ngắn nhất từ s đến t qua v: tst(v) = |Si| * dut khi v = u. 
(ii) Tương tự (2.15), trên đồ thị G2, mỗi đỉnh S’i sẽ đại diện cho |Si| đỉnh sườn tương 
đương ở đồ thị G, nên số đường đi ngắn nhất từ s đến t qua v: tst(v) = |Si| * tut(v), 
khi v ≠ u. 
(iii) Đỉnh cuối t = S’i đại diện cho lớp tương đương có |Si| ³ 2 phần tử. Vì t cũng là 
đỉnh sườn, nên mọi đường đi ngắn nhất từ s đến t = S’i qua v đều phải đi qua 
một đỉnh liền kề (tiền tố) của t là w Î G2(S’i), w không phải là đỉnh sườn. Trên 
đồ thị G2, mỗi đỉnh S’i sẽ đại diện cho |Si| đỉnh sườn tương đương ở đồ thị G, 
nên số đường đi ngắn nhất từ s đến t qua v: tst(v) = |Si| * dsw khi v = w. 
(iv) Tương tự (2.17), trên đồ thị G2, mỗi đỉnh S’i sẽ đại diện cho |Si| đỉnh sườn tương 
đương ở đồ thị G, nên số đường đi ngắn nhất từ s đến t qua v: tst(v) = |Si| * tsw(v) 
khi v ≠ w. 
(v) Trường hợp đỉnh đầu s = S’i đại diện cho lớp tương đương có |Si| ³ 2 phần tử và 
đỉnh cuối t = S’j đại diện cho lớp tương đương có |Sj| ³ 2 phần tử. Vì s, t cũng 
đều là đỉnh sườn, nên mọi đường đi ngắn nhất từ s = S’i đến t qua v đều phải đi 
qua một đỉnh liền kề (hậu tố) của s là u và phải đi qua một đỉnh liền kề (tiền tố) 
của t là w. Trên đồ thị G2, mỗi đỉnh S’i sẽ đại diện cho |Si| đỉnh sườn tương 
đương và mỗi đỉnh S’j sẽ đại diện cho |Sj| đỉnh sườn tương đương ở đồ thị G, 
56 
nên số đường đi ngắn nhất từ s đến t qua v: tst(v) = |Ci| * |Cj| * tuw(v) khi v ≠ u, 
v ≠ w. n 
Ví dụ 2.6. Xét đồ thị G2 được rút gọn từ G cho trước trong Hình 2.1. 
Các đỉnh 1 và đỉnh 2 là hai đỉnh sườn tương đương, đỉnh 1 »2 đỉnh 2, được kết 
hợp với nhau thành đỉnh đại diện S’1 và các đỉnh 6 kết hợp với đỉnh 8 thành S’2 như 
trong hình 2.6 
Hình 2.6. Đồ thị G2 được rút gọn bằng cách kết hợp đỉnh 1 và đỉnh 2 thành 
đỉnh sườn S’1, còn đỉnh 6 và đỉnh 8 kết hợp thành S’2. 
2.2.3. Các lớp đỉnh đồng nhất tương đương 
Định nghĩa 2.5. Cho đồ thị vô hướng, liên thông G = (V, E). Hai đỉnh u, v Î V được 
gọi là đồng nhất (Identical vertex) [84] trên G, ký hiệu là u »3 v khi và chỉ khi N(u) = 
N(v) ³ 2 và đồ thị con sinh bởi N(u) không phải clique (đồ thị con đầy đủ). 
Ví dụ 2.7. Xét đồ thị G được cho như trong Hình 2.1. 
Ta thấy các đỉnh 5, đỉnh 8 là hai đỉnh đồng nhất, đỉnh 5 »3 đỉnh 8, bởi N(đỉnh 5) = 
N(đỉnh 8) = {đỉnh 4, đỉnh 6, đỉnh 7, đỉnh 9}. Đồ thị G có một lớp D’1 = {đỉnh 5, đỉnh 
8} hai đỉnh đồng nhất với nhau. Kết hợp đỉnh 5 và đỉnh 8 thành một đỉnh đại diện D’1 
để được đồ thị rút gọn G3 như hình 2.7 
57 
Hình 2.7. Đồ thị G3 sau khi kết hợp các đỉnh đồng nhất tương đương 
Những đỉnh đồng nhất có thể kết hợp thành một đỉnh đại diện để rút gọn số đỉnh 
trên đồ thị. Giả sử G = (V, E) có các lớp đỉnh đồng nhất Di, i = 1..l, mỗi lớp có ít nhất 
2 đỉnh đồng nhất với nhau. Kết hợp những đỉnh đồng nhất (trong cùng lớp) thành một 
đỉnh đồng nhất đại diện, ta nhận được đồ thị G3 = (V3, E3), trong đó: 
• V3 = V - V3 È {D’1, D’2, , D’h}, với V3 = D1 È D2 È  È Dl. (***) 
• E3 = E - {(u, v) | u Î V3, v Î N(u)} È {(v, D’i) | i = 1..l, v Î N(u), với u Î Si} 
Ký hiệu N(D’i) = N(u), u Î Di. 
Tính chất 2.10. Nếu u, v là hai đỉnh đồng nhất (u »3 v) trên đồ thị G, thì: 
dst(u) = dst(v), với mọi s ≠ v, u ≠ t Î V (2.20) 
Chứng minh. 
 Trường hợp s ≠ v, u ≠ t Î V, mọi đường đi ngắn nhất đi qua một đỉnh u thì, trước 
khi đi đến u, chúng phải đi qua ít nhất một đỉnh p liền kề với đỉnh u (p Î N(v)), sau 
đó phải đi qua một đỉnh q khác liền kề với u (q Î N(u)) sau khi đã qua u. Vì u » v, 
nên theo định nghĩa N(u) = N(v), do đó cũng sẽ có đường đi ngắn nhất. qua đỉnh v. 
Do vậy, dst(u) = dsp * dpq(u) * dqt = dsp * dpq(v) * dqt = dsp(v). n 
Tính chất 2.11. Nếu u, v là hai đỉnh đồng nhất (u »3 v) trên đồ thị G, thì: 
 dst(e1) = dst(e2), với mọi s ≠ v, u ≠ t Î V, với mọi wÎN(u) = N(v), e1= (u, w), e2 = 
(v, w) (2.21) 
Chứng minh. 
Tương tự như tính chất 2.10, nhưng thay vì xét số đường đi ngắn nhất qua đỉnh, ở 
tính chất 2.11 xét số đường đi ngắn nhất qua cạnh liên thuộc với hai đỉnh tương đương 
58 
u, v và vì tập các đỉnh liền của u, v bằng nhau, nên số các đường đi ngắn nhất qua e1, 
e2 luôn bằng nhau. n 
Tính chất 2.12. Giả sử G3 là đồ thị rút gọn của đồ thị G sau khi kết hợp các đỉnh 
đồng nhất của các lớp Di thành một đỉnh đại diện D’i, i = 1l. Ta có các tính chất 
sau: 
(i) δD'it(v) = |Di| * δut, uÎ N(D’i), i =1..l, u = v, t Ï {u, D’1, D’2, , D’l} (2.22) 
(ii) δD'it (v) = |Di| * δut(v), uÎ N(D’i), i =1..l, u ≠ v, t Ï {u, D’1, D’2, , D’l} (2.23) 
(iii) δsD'i (v) = |Di|*δsw, wÎ N(D’i), i = 1..l, w = v, s Ï {v, D