Számítástudomány alapjai epizód tartalma:

Nézzük meg, hogy milyen típusú gráfok vannak. Az összefüggő körmentes gráf a fa. A teljes gráf pedig egy olyan gráf, ahol minden csúcsból minden csúcsba vezet él. De itt jönnek aztán a páros gráfok és további izgalmak. 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

Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.

A fa egy olyan gráf, ahol a lehető legkevesebb él felhasználásával kötjük össze a csúcsokat.

És bármely csúcsból bármely másik csúcsba pontosan egy út vezet.

A másik véglet, ha bármely csúcsból bármelyik másik csúcsba közvetlen él is vezet.

Ezeket a gráfokat teljes gráfnak nevezzük.

Ez egy négypontú teljes gráf:

Ez pedig egy ötpontú teljes gráf:

FA

TELJES GRÁF

Egy n csúcsból álló fának mindig n-1 darab éle van.

Az n pontú teljes gráf éleinek száma:

Ezek az információk később még jól jöhetnek…

Például olyan esetekben, amikor egyik ismerősünk előáll azzal, hogy tegnap látott egy olyan 8 pontú összefüggő gráfot, aminek 6 darab éle van.

Biztosak lehetünk benne, hogy az illető hazudik.

Azért hazudik, mert a 8 pontból álló összefüggő gráfok közül a legkevesebb éle a fának van.

Egy 8 pontból álló fának pedig 8-1=7 éle van.

Íme, itt van néhány gráf.

Lássuk, melyik milyen...

Körmentes

Összefüggő

Fa

Mivel minden fa összefüggő és körmentes, ezért a helyzet

valójában valahogy így néz ki:

Az összefüggő gráfok közül a legösszefüggőbbek a teljes gráfok.

Íme, itt a teljes kollekció:

A nem összefüggő körmentes gráfok neve erdő.

Ez itt például egy erdő:

Végül itt jön még egy vicces dolog.

Nézzük meg ezt a gráfot.

Ezt a gráfot páros gráfnak nevezzük.

Miért hívjuk így?

Ezért.

A gráf csúcsai két csoportra oszthatók.

Az egyik csoportban is olyan csúcsok vannak, melyek között nem vezet él…

és a másikban is.

A legegyszerűbb páros gráf ez:

Aztán itt jön egy bonyolultabb:

De azért még ezt is túl lehet élni…

Ez még érdekesebb:

Így persze már nehezebb róla megállapítani, hogy ez egy páros gráf…

Csomagoljuk szépen vissza.

Ha minden csúcs az egyik oldalon össze van kötve minden csúccsal a másik oldalon…

Akkor ez egy K2,2 teljes páros gráf.

A dolog még tovább fokozható:

Őrület!

Most pedig jó lenne tudni, hogy ezek a gráfok tulajdonképpen mire jók a valóságban.

Mégis mi értelme van gráfokkal foglalkozni?

Lássunk erre néhány példát.

Ez a vasúti hálózat például egy gráf.

Megmutatja, hogy mely állomások között vezetnek vasútvonalak.

Ha ellátjuk az éleket súlyokkal…

Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.

Vagy hány percig tart a két állomás közötti út.

Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.

Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…

akkor a gráfnak egy feszítőfáját kapjuk.

Feszítőfából általában több is van.

És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…

Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

Nézzük meg, hogy milyen típusú gráfok vannak. Az összefüggő körmentes gráf a fa. A teljes gráf pedig egy olyan gráf, ahol minden csúcsból minden csúcsba vezet él. De itt jönnek aztán a páros gráfok és további izgalmak. Egyszerű gráfok, Csúcsok, Élek, Út, Kör, Összefüggő gráf, Gráfok komponensei, Izolált pont, Körmentes gráfok, Fa

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez