Qrafın diametri#1796

Qrafın diametri (Həll təhlili)

Diametri və radiusu hesablamaq üçün bizə bütün təpə cütləri arasındakı ən qısa məsafələr lazımdır. Qrafın təpələrini $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n ilə, $v_{i}$ v_i və $v_{j}$ v_j təpələri arasındakı ən qısa məsafəni isə $d (v_{i}, v_{j})$ d(v_i, v_j) ilə işarə edək. Bütün belə məsafələrin matrisini Floyd — Warshall alqoritmi vasitəsilə qururuq.

Floyd — Warshall alqoritmi. Əvvəlcə $d (v_{i}, v_{j})$ d(v_i, v_j) $v_{i}$ v_i və $v_{j}$ v_j təpələri arasındakı tilin çəkisinə bərabərdir, əgər belə til yoxdursa, sonsuzluğa bərabərdir; $d (v_{i}, v_{i}) = 0$ d(v_i, v_i) = 0. Sonra $v_{k}$ v_k təpələrini bir-bir gəzirik və hər $(v_{i}, v_{j})$ (v_i, v_j) təpə cütü üçün yolun $v_{k}$ v_k təpəsindən keçdikdə qısalıb-qısalmadığını yoxlayırıq:

d (v_{i}, v_{j}) = min (d (v_{i}, v_{j}), d (v_{i}, v_{k}) + d (v_{k}, v_{j}))

d(v_i, v_j) = \min(d(v_i, v_j), d(v_i, v_k) + d(v_k, v_j))

$v_{k}$ v_k təpəsi emal edildikdən sonra matrisdə bütün aralıq təpələri $v_{1}, \dots, v_{k}$ v_1, \ldots, v_k arasında olan ən qısa yolların uzunluqları saxlanılır. Beləliklə, bütün $n$ təpə emal edildikdən sonra matrisdə tələb olunan ən qısa məsafələr olacaq.

Eksentrisitetlər. $v_{i}$ v_i təpəsinin eksentrisiteti $r (v_{i})$ r(v_i) ən qısa məsafə matrisinin $i$ -ci sətrinin maksimum elementinə bərabərdir:

r (v_{i}) = 1 \leq j \leq n max d (v_{i}, v_{j})

r(v_i) = \max_{1 \le j \le n} d(v_i, v_j)

Qrafın diametri təpə cütləri arasındakı maksimum məsafədir, yəni $r (v_{i})$ r(v_i) eksentrisitetlərinin maksimumudur. Qrafın radiusu isə $r (v_{i})$ r(v_i) eksentrisitetlərinin minimumudur.

Misal

Misalda verilən qraf aşağıda göstərilmişdir. Sol şəkildə uzunluğu diametrə bərabər olan ən qısa yol, sağ şəkildə isə eksentrisiteti radiusa bərabər olan təpə qeyd edilmişdir.

Bütün təpə cütləri arasındakı ən qısa məsafələri hesablayaq. Məsələn, $2$ və $3$ təpələri arasında til yoxdur. $2 \to 4 \to 3$ 2 \to 4 \to 3 yolunun uzunluğu $5 + 4 = 9$ 5 + 4 = 9-dur, $2 \to 4 \to 1 \to 3$ 2 \to 4 \to 1 \to 3 yolu isə daha qısadır: $5 + 2 + 1 = 8$ 5 + 2 + 1 = 8, deməli $d (v_{2}, v_{3}) = 8$ d(v_2, v_3) = 8. Eynilə, $d (v_{3}, v_{4}) = 3$ d(v_3, v_4) = 3: $3 \to 1 \to 4$ 3 \to 1 \to 4 yolu uzunluğu $1 + 2 = 3$ 1 + 2 = 3 olmaqla $4$ çəkili birbaşa tildən qısadır.

Ən qısa məsafə matrisi və təpələrin eksentrisitetləri aşağıdakı kimidir:

	$1$	$2$	$3$	$4$	$r (v_{i})$ \boldsymbol{r(v_i)}
$1$	$0$	$7$	$1$	$2$	$7$
$2$	$7$	$0$	$8$	$5$	$8$
$3$	$1$	$8$	$0$	$3$	$8$
$4$	$2$	$5$	$3$	$0$	$5$

Maksimum eksentrisitet $8$ -ə bərabərdir və $2$ və $3$ təpələrində əldə edilir — bu qrafın diametridir. Minimum eksentrisitet $5$ -ə bərabərdir və $4$ təpəsində əldə edilir — bu qrafın radiusudur.

Alqoritmin implementasiyası

Sabitləri və qrafın çəki matrisi $g$ -ni elan edək. Olmayan til "sonsuzluq" $I N F = 0x3F3F3F3F$ INF = \mathrm{0x3F3F3F3F} ilə işarə olunur. Bu qiymət mütləq istənilən ən qısa yolun uzunluğundan böyükdür (bu uzunluq $99 \cdot 1000$ 99 \cdot 1000-dən çox ola bilməz). Eyni zamanda, iki sonsuzluğun cəmi hələ də $in t$ tipinə sığır, buna görə $g [i] [k] + g [k] [j]$ g[i][k] + g[k][j] hesablanarkən overflow baş vermir.

#define MAX 110
#define INF 0x3F3F3F3F
int g[MAX][MAX];

floyd funksiyası Floyd — Warshall alqoritmini implementasiya edir. Xarici dövr $k$ aralıq təpəsini gəzir. Hər $(i, j)$ təpə cütü üçün $i$ -dən $j$ -yə olan yolun $k$ təpəsindən keçməklə qısaldıla bilib-bilmədiyini yoxlayırıq. Əgər $g [i] [k] + g [k] [j] < g [i] [j]$ g[i][k] + g[k][j] < g[i][j] olarsa, $g [i] [j]$ g[i][j] qiymətini yeniləyirik. Ən qısa məsafələr birbaşa $g$ matrisində hesablanır.

void floyd(void)
{
  int i, j, k;
  for(k = 0; k < n; k++)
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if (g[i][k] + g[k][j] < g[i][j])
      g[i][j] = g[i][k] + g[k][j];
}

C++

Proqramın əsas hissəsi. $n$ təpə sayını və qrafın qonşuluq matrisini oxuyun. $- 1$ qiyməti tilin olmadığını bildirir; onu $I N F$ ilə əvəz edin.

scanf("%d",&n);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
  scanf("%d",&g[i][j]);
  if (g[i][j] < 0) g[i][j] = INF;
}

C++

Bütün təpə cütləri arasındakı ən qısa məsafələri hesablayın. $f l oy d$ funksiyası çağırıldıqdan sonra $g [i] [j]$ g[i][j] qiyməti $i$ və $j$ təpələri arasındakı ən qısa məsafəyə bərabərdir.

floyd();

Hər $i$ təpəsi üçün onun eksentrisitetini $ma x$ — $g$ matrisinin $i$ -ci sətrinin maksimum elementini hesablayın. Bütün eksentrisitetlərin maksimumu qrafın diametrinə $d iam$ , minimumu isə radiusuna $r a d i u s$ bərabərdir.

diam = 0; radius = INF;
for(i = 0; i < n; i++)
{
  max = 0;
  for(j = 0; j < n; j++)
    if (g[i][j] > max) max = g[i][j];
  if (max > diam) diam = max;
  if (max < radius) radius = max;
}

C++

Qrafın diametrini və radiusunu çap edin.

printf("%d\n%d\n",diam,radius);

Java implementasiyası

import java.util.Scanner;

public class Main
{
  static final int INF = 0x3F3F3F3F;
  static int g[][];
  static int n;

  static void floyd()
  {
    for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if (g[i][k] + g[k][j] < g[i][j])
        g[i][j] = g[i][k] + g[k][j];
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new int[n][n];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
      g[i][j] = con.nextInt();
      if (g[i][j] < 0) g[i][j] = INF;
    }
    floyd();
    int diam = 0, radius = INF;
    for(int i = 0; i < n; i++)
    {
      int max = 0;
      for(int j = 0; j < n; j++)
        if (g[i][j] > max) max = g[i][j];
      if (max > diam) diam = max;
      if (max < radius) radius = max;
    }

    System.out.println(diam + "\n" + radius);
    con.close();
  }
}

Java