Az A szomszédsági mátrix a_ij eleme lehetne logikai érték, attól függően, hogy az i. és j. pont között van-e él. Természetesen az értékek lehetnének számok, a többszörös élek megjelenítésével akár nem csak 0-k vagy 1-ek. A nem irányított gráf mátrixa biztosan szimmetrikus a főátló szerint. A szomszédsági mátrixban az élek tárolása ritka gráf esetén igencsak gazdaságtalan, ugyanakkor könnyen karbantartható és gyorsan lekérdezhető. Ha csak a meglévő éleket tároljuk el gazdaságossági megfontolásból (2 vektor is elegendő ennek megoldására), akkor nehézkesebb lesz az élek felvitele és törlése, valamint több keresést igényelnek majd a lekérdezések. 

Tekintsünk egy irányított gráfot. A 6 pont között kifeszített élek nem mindegyike kétirányú, de a kétirányúakat is egy vonallal, egy irányítás nélküli vonallal jelöljük.

A pontból pontba tartó közvetlen élek meglétét (+/-, igen/nem értékekkel) mátrixban tárolhatjuk, mely jelen esetben nem szimmetrikus (hiszen a gráf nem irányítatlan), és csupa '-' van a főátlójában (mert nincs benne hurok). Megegyezünk abban, hogy a mátrix i. sorában és j. oszlopában az i. pontból a j. pontba vezető élről tárolandó értéket (mint van/nincs vagy 0/n darab) tartjuk. A mátrix megnevezése szomszédsági mátrix vagy csúcsmátrix. A mátrixról mondhatjuk, hogy ritka, amennyiben kevés az él a gráfban.

A gráf éleinek tárolása

Tárolhatjuk csak a létező éleket a helyigény csökkentése miatt. A két mátrix egyikében a pontokat, a másikban a sorszámozott éleket tartjuk, például a kezdőpontok szerinti sorrendben:

Az alábbi lista segítségével írjuk fel az élek vektorát:

Hálózat

Amikor az él más jellemző(ke)t is képvisel, a gráfot hálózatnak vagy súlyozott gráfnak nevezzük (bár nagyon gyakran mégsem teszünk kivételt). Ilyen jellemző lehet: a költség, munkaóra, távolság, időtartam stb. Természetesen ilyenkor a pontoknak is lehetnek jellemzői: koordináták, besorolás vagy minősítés, indulás vagy végzés időpontja stb.

Súlyozott gráf ábrázolása

Tekintsük a fenti irányított gráfot súlyozott élekkel. A 6 pont között kifeszített élek most a közvetlen távolságot hordozzák. A kétirányú éleket továbbra is egy vonallal jelöljük, mert az oda- és visszafelé tartó út hossza jelen esetben egyforma.

A súlyozott gráf mátrix-reprezentációja

Egyik pontból sem vezet él önmagába, tehát a P pontból a Q pontba irányított élek súlya táblázatban elhelyezve egy olyan táblázatot eredményez, melynek a főátlójában csupa 0 van. A táblázat nem szimmetrikus a főátlóra, hiszen nem minden él kétirányú. A nem közvetlen kapcsolatok hossza egyelőre ismeretlen; minimalizáló számításokra felkészülve a kiindulási mátrixban végtelen vagy egy elég nagy szám kerül a helyükre.

A súlyozott gráf éleinek tárolása

A pontoknak most nincs semmilyen jellemzője, de az élek jellemzője a távolság:

Szakmai kihívásként a szakképzés folyamán többször kell majd megkeresni a két pont közötti legrövidebb utat, vagy az egyik pontból az összes többibe tartó minimális utat, esetleg a minden pontot tartalmazó minimális feszítőfát, amelyben az utak súlyainak összege a lehető legkisebb.

Segítségképpen már itt megismerkedhetünk két matematikai módszerrel, melyek számítógépes algoritmusát valamely szaktárgy keretében el is kell készíteni.

Alapfeladat: egy adott pontból akarjuk egy konkrét hálózat összes többi pontját ellátni a lehető legrövidebb úton, amikor a lehetséges pont-párok közötti távolságok ismertek.

Megoldási módszerek

Mátrix-reprezentációban a Warshall-eljárással megkapjuk bármely pontból bármely pontba a legrövidebb utat.

Minimális fa építése útján a Dijkstra-eljárással megkapjuk az adott kezdőpontból az összes többi pontba vezető minimális utakat.

A különböző kezdőpontokból felépített minimális fákat már érdemes összehasonlítani az összes utak hossza szerint, esetleg az élek össz-hossza szerint; bár a hálózat építésekor nem az egyszeri úthálózat kiépítésének minimalizálása a cél (összhangban az élek egyszeres hosszával), hanem az útvonalakon történő folyamatos/gyakori áramoltatás/közlekedés miatt inkább az utak hosszának az összegét célszerű minimalizálni.

Válasszunk egy nagyobb hálózatot a fent jelzett két módszer bemutatására!