距離和同構圖之間的關係

Question

在圖論中，距離d_G（u，v）（圖G中任意兩個頂點u和v的最短長度）和同構圖之間是否有任何關係？如果存在兩個連通圖G和H，並且從V（G）到V（H）（V（G））的1對1函數'f'表示G中的頂點集合，使得d_G（ u，v）= d_H（f（u），f（v））爲G和H的每兩個頂點u和v是同構的嗎？如果存在兩個連通圖G和H，並且從V（G）到V（H）（V（G））的1對1函數'f'表示G中的頂點集合，使得d_G（ u，v）≠d_H（f（u），f（v））爲G的每兩個頂點u和v。G和H不同構嗎？

Answer 1

根據the definition of an isomorphism of graphs in graph theory，任何兩點u和G訴應在G是相鄰的，當且僅當ƒ（u）和ƒ（V）是H.

1. 相鄰順便提及，如果d（u，v）= 1，則u和v相鄰。假設，如果d（u，v）= 1，d（f（u），f（v））= 1，那麼如果u和v相鄰，則f（u）和f（v）是相鄰的。因此，給定的1對1函數f是圖的同構性。如果G，H是同構的，那麼就不存在任何兩個頂點u和v，d（u，v）≠d（f（u），f（v））的對偶問題。 ）」。但是，f存在。

Obviously, two graphs are isomorphic but

d(u_1, u_2) = 1 
d(u_1, u_3) = 2 
d(u_1, u_4) = 3 
d(u_2, u_3) = 1 
d(u_2, u_4) = 2 
d(u_3, u_4) = 1 

d(f(u_1), f(u_2)) = 2 
d(f(u_1), f(u_3)) = 1 
d(f(u_1), f(u_4)) = 1 
d(f(u_2), f(u_3)) = 3 
d(f(u_2), f(u_4)) = 1 
d(f(u_3), f(u_4)) = 2