Gráfelmélet GYIK

Mi is az a gráf?
A gráf pontok, és azokat összekötő vonalak összessége a síkban. A pontokat csúcspontoknak, a vonalakat éleknek nevezzük.

Mi egy csúcspont fokszáma?
Egy csúcspont fokszáma meghatározza, hogy oda mennyi él fut be.

Mi a teljes gráf?
Teljes gráfról beszélünk, ha az összes csúcspont össze van kötve egymással. Ez esetben minden pont fokszáma ugyanannyi. Ez fordítva is igaz, ha egy gráfban minden pont fokszáma megegyezik, tehát ugyanannyi él fut be az adott pontokba, akkor teljes gráffal állunk szemben. Egy teljes gráf összes éleinek száma n alatt 2.

Mi a hurok?
A hurok egy pontot önmagával összekötő él.

Mikor beszélünk többszörös élről?
Ha két pont között több él húzódik.

Mi a fa?
A fa a matematikában olyan gráf, melyben nincsen kör, tehát nincs legalább három olyan pontja, melyek élei egy zárt síkidomot alkotnak.

Végül: Hol használják a gráfokat gyakorlatban?
Programozásnál útvonalkereső algoritmusokhoz rendkívül hasznos, illetve a logisztikai szakterületen fordulhat még elő. Emellett ritkábban, de használják a kémiában is, ahol a pontok atomokat, az élek pedig kötéseket jelölnek.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöljük.