Grafın çapı#1796

Grafın çapı (Editoryal)

Çapı ve yarıçapı hesaplamak için, tüm köşe çiftleri arasındaki en kısa mesafelere ihtiyacımız var. Grafın köşelerini $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n ile, $v_{i}$ v_i ve $v_{j}$ v_j köşeleri arasındaki en kısa mesafeyi ise $d (v_{i}, v_{j})$ d(v_i, v_j) ile gösterelim. Tüm bu mesafelerin matrisini Floyd — Warshall algoritması kullanarak oluşturuyoruz.

Floyd — Warshall algoritması. Başlangıçta, $d (v_{i}, v_{j})$ d(v_i, v_j), $v_{i}$ v_i ve $v_{j}$ v_j köşeleri arasındaki kenarın ağırlığına eşittir, ya da böyle bir kenar yoksa sonsuza eşittir; $d (v_{i}, v_{i}) = 0$ d(v_i, v_i) = 0'dır. Daha sonra $v_{k}$ v_k köşelerini birer birer dolaşıyoruz ve her $(v_{i}, v_{j})$ (v_i, v_j) köşe çifti için, $v_{k}$ v_k köşesinden geçerek yolun daha kısa olup olmadığını kontrol ediyoruz:

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 köşesi işlendikten sonra, matris, tüm ara köşeleri $v_{1}, \dots, v_{k}$ v_1, \ldots, v_k arasında bulunan en kısa yolların uzunluklarını içerir. Dolayısıyla, $n$ köşenin tamamı işlendikten sonra, matris gerekli en kısa mesafeleri içerir.

Dışmerkezlikler (Eccentricities). $v_{i}$ v_i köşesinin dışmerkezliği $r (v_{i})$ r(v_i), en kısa mesafe matrisinin $i$ . satırının en büyük elemanına eşittir:

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)

Grafın çapı, bir köşe çifti arasındaki en büyük mesafedir, yani $r (v_{i})$ r(v_i) dışmerkezliklerinin en büyüğüdür. Grafın yarıçapı ise $r (v_{i})$ r(v_i) dışmerkezliklerinin en küçüğüdür.

Örnek

Örnekte verilen graf aşağıda gösterilmiştir. Sol şekilde uzunluğu çapa eşit olan en kısa yol vurgulanmıştır, sağ şekilde ise dışmerkezliği yarıçapa eşit olan köşe vurgulanmıştır.

Tüm köşe çiftleri arasındaki en kısa mesafeleri hesaplayalım. Örneğin, $2$ ve $3$ köşeleri arasında kenar yoktur. $2 \to 4 \to 3$ 2 \to 4 \to 3 yolunun uzunluğu $5 + 4 = 9$ 5 + 4 = 9'dur, oysa $2 \to 4 \to 1 \to 3$ 2 \to 4 \to 1 \to 3 yolu daha kısadır: $5 + 2 + 1 = 8$ 5 + 2 + 1 = 8, dolayısıyla $d (v_{2}, v_{3}) = 8$ d(v_2, v_3) = 8'dir. Benzer şekilde, $d (v_{3}, v_{4}) = 3$ d(v_3, v_4) = 3'tür: uzunluğu $1 + 2 = 3$ 1 + 2 = 3 olan $3 \to 1 \to 4$ 3 \to 1 \to 4 yolu, ağırlığı $4$ olan doğrudan kenardan daha kısadır.

En kısa mesafe matrisi ve köşelerin dışmerkezlikleri aşağıdaki gibidir:

	$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$

En büyük dışmerkezlik $8$ 'e eşittir ve $2$ ile $3$ köşelerinde elde edilir — bu, grafın çapıdır. En küçük dışmerkezlik $5$ 'e eşittir ve $4$ köşesinde elde edilir — bu, grafın yarıçapıdır.

Algoritmanın gerçekleştirilmesi

Sabitleri ve $g$ grafının ağırlık matrisini tanımlayalım. Eksik bir kenar, "sonsuz" $I N F = 0x3F3F3F3F$ INF = \mathrm{0x3F3F3F3F} ile gösterilir. Bu değer, kesinlikle herhangi bir en kısa yolun uzunluğundan (bu değer $99 \cdot 1000$ 99 \cdot 1000'i geçmez) büyüktür. Aynı zamanda, iki sonsuzun toplamı hâlâ $in t$ türüne sığar, dolayısıyla $g [i] [k] + g [k] [j]$ g[i][k] + g[k][j] hesaplanırken herhangi bir taşma (overflow) oluşmaz.

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

floyd fonksiyonu Floyd — Warshall algoritmasını gerçekleştirir. Dış döngü, ara köşe $k$ üzerinde dolaşır. Her $(i, j)$ köşe çifti için, $i$ 'den $j$ 'ye olan yolun $k$ köşesinden geçirilerek kısaltılıp kısaltılamayacağını kontrol ediyoruz. Eğer $g [i] [k] + g [k] [j] < g [i] [j]$ g[i][k] + g[k][j] < g[i][j] ise, $g [i] [j]$ g[i][j] değerini güncelliyoruz. En kısa mesafeler doğrudan $g$ matrisinde hesaplanı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++

Programın ana bölümü. Köşe sayısı $n$ 'yi ve grafın komşuluk matrisini okuyun. $- 1$ değeri, kenar olmadığı anlamına gelir; bunu $I N F$ ile değiştirin.

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++

Tüm köşe çiftleri arasındaki en kısa mesafeleri hesaplayın. $f l oy d$ çağrısından sonra, $g [i] [j]$ g[i][j] değeri $i$ ve $j$ köşeleri arasındaki en kısa mesafeye eşittir.

floyd();

Her $i$ köşesi için, dışmerkezliğini $ma x$ — $g$ matrisinin $i$ . satırının en büyük elemanını hesaplayın. Tüm dışmerkezliklerin en büyüğü grafın çapına $d iam$ eşittir, en küçüğü ise grafın yarıçapına $r a d i u s$ eşittir.

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++

Grafın çapını ve yarıçapını yazdırın.

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

Java gerçekleştirimi

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