Gráfok

A gráf egy olyan adatszerkezet, amely csúcsokból/pontokból, és azokat összekötő élekből áll.

Ez pl. egy gráf:

A gráfokat tipikusan olyan helyzetekben alkalmazzuk, amikor különféle dolgok kapcsolatáról beszélünk.

Ez lehet egy metróhálózat:

Vagy diákok, akiknek legjobb barátaik vannak:

Néhány hasznos kifejezés, szakszó

A gráf összefüggő, ha bármely pontjából bármely pontjába el lehet jutni.

Ez pl. egy nem összefüggő gráf:

A gráf irányított, ha ez éleknek van egy kiinduló és egy végpontja. A fenti legjobb barát gráf irányított, míg a metróhálózat irányítatlan.

Egy gráf pedig súlyozott, ha az élekhez egy-egy számértéket rendelünk. A metróhálózat gráf súlyozott, míg a legjobb barát súly nélküli.

Egy gráf egyszerű, ha nincsenek benne olyan élek, amiknek:

• Ugyanazt a két pontot kötik össze (többszörös él)
• A kezdő- és a végpontja megegyezik (hurokél)

A korábbi példák mind egyszerű gráfok, az alábbi viszont nem:

Egy gráf pedig fa, ha összefüggő, és nincs benne kör - azaz ha egy pontból elindulunk, nem lehet visszajutni anélkül, hogy élen kétszer átmennénk. Érdemes összevetni az adatszerkezeteknél tanult definícióval - a kettő végeredményben ugyanazt jelenti, de a megközelítés, a felhasználás módja különbözik. E legelső példa az nem fa, mert tartalmazza az “1-2-3” pontokból álló kört.

Sok más hasznos tulajdonságot is elmondhatunk a gráfokról, itt csak a legfontosabbakat szedtem össze. Egy teljesebb körű fogalomtár megtalálható itt.

Tárolási mód

A gráfokat természetesen el kell tárolni valahogy, hogy a számítógép dolgozni tudjon vele. Erre a két gyakran alkalmazott megoldási mód van: a csúcsmátrix és az éllista. Vegyük pl. az első példabeli gráfot:

Csúcsmátrix

Ez egy táblázat, ahol a sorok/oszlopok egy-egy csúcst jelképeznek. A táblázatban 1 szerepel, ha az adott élt összeköti egy él, és 0 (vagy üresen is hagyhatjuk), ha nem.

	1	2	3	4	5
1		1	1	1	1
2	1		1
3	1	1
4	1
5	1

Leolvasható, hogy az 1-3 pontokat összeköti egy él, mert a csúcsmátrixban az 1. sor 3. oszlopban szerepel egy 1-es. A 2-4 pontokat viszon nem köti össze, mert a 2. sor 4. oszlopában nincs 1-es.

Éllista

Szimplán felsoroljuk az éleket:

• 1-2
• 1-3
• 1-4
• 1-5
• 2-3