Bevezetés a számításelméletbe 2 epizód tartalma:
Itt röviden és szuper-érthetően elmeséljük, hogy mik azok a gráfok, hogyan lehet őket precízen definiálni, és milyen alapvető tulajdonságaik vannak. Gráfok, Gráfok precíz definíciója, Egyszerű gráfok, Csúcsok, Élek, Út, Kör, Összefüggő gráf, Gráfok komponensei, Izolált pont, Körmentes gráfok, Fa
A képsor tartalma
Itt az ideje, hogy egy kicsit precízebben is elkezdjünk foglalkozni a gráfokkal.
A G gráf csúcsainak halmazát V(G)-vel jelöljük. Itt a V az angol vertex=csúcs szóra utal.
A G gráf éleinek halmazát E(G)-vel jelölünk. Itt E az angol edge=él.
Teljesen tudományosan megfogalmazva a G gráf egy (V(G), E(G)) rendezett pár, ahol V(G) egy nem üres halmaz, E(G) pedig a V(G)-ből képezhető párok egy halmaza.
Ha a gráf egyik csúcsából elindulunk, és teszünk egy sétát a gráfon…
akkor egy élsorozatot kapunk.
Azokat az élsorozatokat, amelyek a gráf semelyik pontján nem haladnak át többször útnak nevezzük.
Ez itt nem egy út, mert V10-en kétszer is áthaladunk.
Ez viszont igen.
Ha egy élsorozat ugyanabból a csúcsból indul, mint ahova érkezik, akkor körsétának nevezzük.
Ez itt például egy körséta.
Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsba.
Íme, itt egy kör.
Egy gráf összefüggő, ha bármely csúcsából bármelyikbe vezet út.
Ha ez nincs így, akkor a gráf több különböző komponensből áll.
Idáig ez nem túl bonyolult.
Ennyire még Piroska néni, a jósnő is járatos a gráfokban.
De az izgalmak csak most jönnek.
Egy csúcs fokszáma azt mondja meg, hogy hány él vezet az adott csúcsba.
Ennek a csúcsnak itt, a fokszáma például három.
Ennek pedig kettő.
És ennek itt egy.
Egy tetszőleges V csúcs fokszámát d(V)-vel jelöljük.
Ha egy gráfban megszámoljuk a csúcsok fokszámait, akkor minden élt pontosan kétszer számolunk meg.
Egyszer az egyik csúcsnál…
aztán a másiknál.
Vagyis minden gráfban a csúcsok fokszámainak összege az élek számának a kétszerese.
Egy gráfot egyszerű gráfnak nevezünk, ha nincsen benne hurokél…
és nincsen benne párhuzamos él.
HUROKÉL
PÁRHUZAMOS ÉL
A csillagképek mindig egyszerű gráfok.
Mert nincs olyan őrült csillagász, aki előállna azzal, hogy ugyanazt a két csillagot kétszer is összekösse.
Vagy éppen egyetlen csillagot sajátmagával.
A gráfelméletben viszont nem ritkák az olyan gráfok, ahol van hurokél, vagy párhuzamos él.
Annyira nem, hogy a világ legelső gráfjában is voltak párhuzamos élek.
Ezt a híres gráfot Leonhard Euler alkotta meg a königsbergi hidak problémájának megfejtésekor.
A Königsberg nevű városka lakóit az a kérdés nyugtalanította, hogy körbe tudnak-e sétálni a város hídjain úgy, hogy minden hídon pontosan egyszer haladnak át és a séta végén visszaérnek a kiindulópontra.
A kérdés úgy fogalmazható át, hogy létezik-e ebben a gráfban olyan körséta, amely minden élen pontosan egyszer halad át.
Az ilyen körsétákat Euler-körnek (helyesen Euler-körsétának) nevezik.
Euler bebizonyította, hogy egy gráfban pontosan akkor létezik Euler-körséta, ha minden csúcs fokszáma páros.
Így aztán a königsbergieket el kellett keserítenie.
A gráfokkal való ismerkedésünket néhány speciális gráffal fogjuk folytatni.
Itt jön egy izgalmas
Bevezetés a számításelméletbe 2 epizód.
Bevezetés a számításelméletbe 2 epizód.