Graf o'lchovlar: uzunlik, masofa, diametr, ekssentriklik, radius, markaz

Eyler formulasi deb ataladi.
Eyler formulasi stereometriyada ham qo‘llaniladi: uchlari ta, yoqlari ta va qirralari ta ixtiyoriy ko‘pyoqli uchun Eyler formulasi o‘rinlidir. Bu tasdiqning negizida isboti o‘quvchiga havola qilinayotgan quyidagi tasdiq yotadi: stereometriyada berilgan ta’rifga ko‘ra aniqlangan ixtiyoriy ko‘pyoqliga mos tekis izomorf graf mavjuddir.
Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha umumlashtirish mumkin.

Tugunlar soni unchalik katta emas deb hisoblasak, oddiy yechim Floyd-Uorshall algoritmidan barcha tugun juftlari orasidagi eng qisqa yo'llarni topish va keyin eng kattasini olish uchun foydalanish bo'ladi. Quyidagi kod buni ko'rsatadi:

#include


using namespace std;


#define MAX 107
#define NOT_CONNECTED -1


int distance[MAX][MAX];


//number of nodes
int nodesCount;


//initialize all distances to
void Initialize(){
for (int i=0;i for (int j=0;j distance[i][j]=NOT_CONNECTED;
}
distance[i][i]=0;
}
}


int main(){


Initialize();


//get the nodes count
scanf("%d", &nodesCount);


//edges count
int m;
scanf("%d", &m);


while(m--){
//nodes - let the indexation begin from 1
int a, b;


//edge weight
int c;


scanf("%d %d %d", &a, &b, &c);
distance[a][b]=c;
}


//Floyd-Warshall
for (int k=1;k<=nodesCount;++k){
for (int i=1;i<=nodesCount;++i){
if (distance[i][k]!=NOT_CONNECTED){
for (int j=1;j<=nodesCount;++j){
if (distance[k][j]!=NOT_CONNECTED && (distance[i][j]==NOT_CONNECTED || distance[i][k]+distance[k][j] distance[i][j]=distance[i][k]+distance[k][j];

}
}


int diameter=-1;


//look for the most distant pair
for (int i=1;i<=nodesCount;++i){
for (int j=1;j<=nodesCount;++j){
if (diameter diameter=distance[i][j];
printf("%d %d\n", i, j);
}
}
}


printf("%d\n", diameter);


return 0;
}