Diszkrét matematika epizód tartalma:

Itt röviden és szuper-érthetően elmondjuk, hogy miről szól az Euler-féle poliéder tétel. Megnézzük, mikor gömbre rajzolható és mikor síkbarajzolható egy gráf. Kiderül, hogy ha egy gráf pontosan akkor gömbre rajzolható, ha síkbarajzolható. Néhány szükséges feltétel síkbarajzolhatóságra.

A képsor tartalma

Réges-régen, egy messzi-messzi galaxisban létezett egy bolygó, amin különös lények éltek. Egy gátrendszert építettek a bolygó felszínére, a gátak végein tornyokkal. Ezekben a tornyokban laktak a fura lények, minden toronyban egy. A gátak medencékre osztották a bolygó felszínét. Mindegyik medence teljesen száraz volt, kivéve egyet, amiben viszont az egész bolygó felszínére elegendő víz volt. A fura lények egyszer elhatározták, hogy elárasztják bolygójukat vízzel. A terv az volt, hogy felrobbantják a medencéket elválasztó gátakat. És így medencéről medencére haladva szétterítik a vizet. A lények szerettek átjárni egymáshoz vendégségbe a tornyokat összekötő utakon. Az utak a gátak tetején vezettek. Így aztán a robbantások során vigyázniuk kellett, nehogy olyan gátat is felrobbantsanak, ami az egyik lény lakótornyát végleg elszigeteli. Arra jöttek rá, hogy ha mindig csak olyan gátat robbantanak föl, aminek az egyik oldalán víz van a másik oldalán szárazföld, akkor minden lakótorony megközelíthető marad. Legfeljebb nagyobb kört kell megtenni. A lények azt is kiszámolták, hogy ha a bolygón F darab medence van, akkor F-1 darab gátat kell felrobbantaniuk ahhoz, hogy mindent elárasszanak vízzel. Medencék száma: F Lakótornyok száma: V Gátak száma: E Felrobbantott gátak száma: F-1 Megmaradt gátak száma: V-1 V+F=E+2 Most nézzük, hogy hány darab gát marad meg. Amikor végeznek a robbantásokkal, a megmaradt gátak egy körmentes gráfot alkotnak. Ha ugyanis lenne benne kör, akkor lenne olyan rész, ahova még nem folyt volna be a víz. Ez a körmentes gráf egyben összefüggő is, mert a robbantásokat mindig úgy végzik, hogy ne szigeteljék el egyik lény lakótornyát sem. Vagyis a megmaradt gátak hálózata egy összefüggő körmentes gráf, tehát egy fa. Egy n csúcsú fának n-1 darab éle van. Ha a lakótornyok száma V, akkor a fel nem robbantott gátak száma V-1. A bolygón lévő E darab gát közül F-1 darabot felrobbantottak, V-1 darabot pedig nem, tehát: Ezt a képletet Euler-féle poliéder-tételnek hívjuk. Azt mondja az Euler-féle poliéder-tétel, hogy ha egy konvex poliéder csúcsainak száma V, lapjainak száma F és éleinek száma E… akkor csúcsok száma lapok száma élek száma Ez a tétel érvényes minden gömbre rajzolt gráfra is. Itt V a gráf csúcsainak a száma, E az élek száma, F pedig azoknak a tartományoknak a száma, amelyre a gráf felszabdalja a gömb felszínét. A gömbre rajzolt gráfot síkra tudjuk vetíteni egy ügyes kis trükk segítségével. Ezt sztereografikus vetítésnek nevezzük. A dolog oda-vissza működik, vagyis a gömb pontjait síkra tudjuk vetíteni, a sík pontjait pedig gömbre. Ez azt jelenti, hogy az Euler-tétel nem csak a gömbön, hanem a síkon is igaz. Azzal az apró kis módosítással, hogy a síkon a sok korlátos tartomány mellett létezik egy olyan tartomány is, amelyik nem korlátos. Mindez arra jó, hogy megpróbálhatunk találni néhány szabályt, hogy egy gráf mikor síkbarajzolható. Kezdjük az egyszerű gráfokkal. Ha egy gráf egyszerű gráf, legkevesebb 3 élre van szüksége ahhoz, hogy egy tartományt határoljon. Az is lehet, hogy többre, de 3 él mindenképpen kell. Ez azt jelenti, hogy Na persze egy él két tartományhoz is felhasználható. A helyzet tehát egy kicsit jobb. Ha egy egyszerű gráf síkbarajzolható, akkor meg kell felelnie ennek a feltételnek. Sajnos ez csak egy szükséges feltétel, tehát abból, hogy ez teljesül, még nem következik, hogy a gráf síkbarajzolható. Síkbarajzolható gráfok szükséges feltétele: Próbáljuk ki. Itt van K5. K5 nem teljesíti a feltételt, ezért nem síkbarajzolható. Most nézzük mi a helyzet K3,3-mal. Tudjuk, hogy ez sem síkbarajzolható, de lássuk, mit ad rá a kritérium. Hát, a kritérium K3,3-at átengedi… Ettől persze K3,3 továbbra sem síkbarajzolható. Ebből is látszik, hogy ez a kritérium csak szükséges feltétele a síkbarajzolhatóságnak, de nem elégséges. Ha még rémlik valami, a kritériumot úgy gyártottuk, hogy 3 hosszú körökkel számol. K3,3-ban, viszont minden kör 4 hosszú. Ez az oka annak, hogy nem működik itt. Ha egy egyszerű gráfban minden kör legalább k hosszú, akkor a tartományok száma így becsülhető felülről: És mivel egy él két tartományhoz is tartozik… Ha egy egyszerű gráfban minden kör legalább k hosszú, akkor a síkbarajzolhatóság szükséges feltétele: Gyorsan próbáljuk is ki ezt az új képletet. Lássuk, mi a helyzet K3,3-mal. Azért csak kijött, hogy K3,3 sem síkbarajzolható.

 

Az Euler-féle poliéder tétel

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

Itt röviden és szuper-érthetően elmondjuk, hogy miről szól az Euler-féle poliéder tétel. Megnézzük, mikor gömbre rajzolható és mikor síkbarajzolható egy gráf. Kiderül, hogy ha egy gráf pontosan akkor gömbre rajzolható, ha síkbarajzolható. Néhány szükséges feltétel síkbarajzolhatóságra.

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