Диаметр, радиус и центр графа — презентация

Старший преподаватель к афедры теоретической кибернетики Хадиев Р.М. КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Изображение слайда

int main() { int G[100][100], // граф транспортной сети R[100][100], // минимальные расстояния // между вершинами I,j,n, // n – число вершин cin >> n ; for ( i =1; i <=n; i ++) for (j=1; j<=n; j++) cin >> G[ i ][j];

Изображение слайда

int r[100]={0}, // 0 – расстояние не определено ob[100], // обработанные вершины For ( n_p =1; n_p <n; n_p ++) { Int a =1, // вершина из ob, которая обрабатывается p =2 ; // пустое место для записи новых вершин r[ n_p ]=1; // кратчайший путь в n_p – 1 ob[1]= n_p ; // while a<p do { for ( i =0; i <n; i ++ ) // ищем связанные с ob[a] if (G[ i ][ob[a]]==1 & r[ i ]==0) { //необработанные вершины r[ i ]=r[ob[a]]+1; ob[++p]=I; } a++; } for( i =1; i <=n; i ++) R( n_p ][ i ]=r[ i ]; }

Изображение слайда

Диаметр  - 3

Изображение слайда

int D=0; For( i =1; i <=n; i ++) For( i =1; i <=n; i ++) D:= max(D,R[ i ][j]); Cout << “ Диаметр графа = “ << D;

Изображение слайда

Диаметр  - 3

Изображение слайда

int Rad =0; for( i =1; i <=n; i ++) { int M=0; for( i =1 ; i <=n; i ++) M:= max(M,R[ i ][j]); if ( i ==1) Rad =M; else Rad =min( Rad,M ); } cout << “ Радиус графа = “ << Rad ;

Изображение слайда

Цен тр  - 2,3 или 4

Изображение слайда

// Rad – радиус графа for( i =1; i <=n; i ++) { int M=0; for( i =1; i <=n; i ++) M:= max(M,R[ i ][j]); if ( Rad == M cout << “ Центр графа = “ << i ; }

Изображение слайда