Barion Pixel A gráfok precíz bevezetése | mateking
 

Diszkrét matematika 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.
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez