Matrica susjedstva

Matrica susjedstva jedan je od načina prikaza grafa u memoriji.

Definicija

Jednostavan graf netežinski je, neusmjereni graf u kojem brid spaja dva različita vrha. Ne postoji više bridove između dva ista vrha.

Zadan je jednostavan graf čije vrhove (skup ) možemo poredati u niz. Neka je broj vrhova i označimo ih sa . Matrica susjedstva dimenzija dana je formulom po članovima:

Odnosno riječima, matrica susjedstva je kvadratna matrica sa , u kojoj na mjestu piše ako postoji brid koji spaja vrh i .

Primjer

Dan je graf i pripadajuća matrica susjedstva:

Svojstva

• Suma jedinica u redu je stupanj vrha , odnosno .
• Matrica susjedstva jednostavnog grafa ima sve nule na glavnoj dijagonali, budući da niti jedan vrh nema brid u samog sebe.
• Ukoliko je graf neusmjeren matrica susjedstva je simetrična, odnosno vrijedi .

Implementacija

Matricu susjedstva pamtimo kao polje. Ovaj isječak prikazuje učitavanje neusmjerenog grafa. Dolazi u obzir umjesto int tipa podataka koristiti bool radi uštede memorije. Isto tako, u C++ jeziku koristili bi vector i cin.

int N, graph[maxn][maxn];

void load() {
  int m, a, b;
  scanf("%d%d", &N, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    --a; --b;
    graph[a][b] = graph[b][a] = 1;
  }
}

Nastavak čitanja

Što možemo raditi s ovom matricom?

© 2014. Anton Grbin

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License