Dora; // metaarhiva dobrih zadataka
Proizveo: Adrian Satja Kurdija
Ideja preuzeta od Školjke (by Ivica Kičić)

Prijava


Zaboravili ste lozinku?

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:

sh: 1: dot: not found

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 Creative Commons License

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