Grafo lau

Grafo teorian grafo lau deritzo planoan marraztu daitekeen grafo bati, ertzak haien artean gurutzatu gabe. Alboko adibideetan K₅ eta K_3,3 gutxieneko grafo ez lauak dira, eta horietatik abiatuta zehaztu daitezke gainerako grafo ez-lauen ezaugarriak.

Edozein grafo lau esferaren gainean marraztu daiteke, baita alderantziz.

Adibideak
Grafo laua	Grafo ez-laua
K6	K5
K4 grafo osoa	K3,3

Kuratowskiren Teorema

Kazimierz Kuratowski matematikari poloniarrak grafo lauen karakterizazio bat aurkitu zuen, Kuratowskiren teorema bezala ezagutzen dena.

Beste irizpide batzuk

Zaila da Kuratowskiren teorema erabiltzea grafo bat zaila den azkar erabakitzeko. Arazo hau konpontzeko algoritmo azkar bat dago: a ertz eta n erpin dituen grafo bat izanik, posiblea da grafoa laua den zehaztea Eulerren formularekin.

Eulerren formula

Eulerren formulak dio grafo lau lotu batek honakoa betetzen duela: Txantiloi:Teorema Aurreko adibideetan, lehen grafo lauan (K₆-a) honako hauek ditugu: v = 6, a = 7 eta c = 3. Bigarren grafoa ertz-elkargunerik gabe marraztuz, v = 4, a = 6 eta c = 4 izango genuke, grafoa laua izanik. Ohartu Eulerren formula poliedro sinpleetarako ere baliagarria da. Ez da kasualitatea: poliedro sinple bakoitza grafo lau eta lotu gisa ikus daiteke, poliedroaren erpinak grafoaren erpin gisa erabiliz, eta poliedroaren ertzak grafoaren ertz gisa. Grafo lauaren aurpegiak edo eskualdeak poliedroaren aurpegiak dira. Adibidetakoko bigarren grafo laua, adibidez, tetraedro bati dagokio.

Beste irizpide batzuk ondoko bi teoremak dira: Txantiloi:Teorema Hau da, n erpin dituen grafo lauak, $n\ge 3$ izanik, gehienez $3n-6$ ertz izango ditu. Txantiloi:FrogaTxantiloi:Teorema

Txantiloi:Froga 1 teorematik ondorioztatzen dugu K₅ ez dela laua, 5 ertzeko grafo lau batek gehienez 9 ertz izan ditzakelako, baina K₅-ek 10 ertz dituenez ez da laua. K_3,3-ren kasuan, 6 erpin ditu eta ez du 3 luzerako ziklorik, baina 9 ertz dituenez, 2. teoremak dio ezin dela laua izan.

Ohartu teorema hauek norabide bakarreko inplikazioarekin adierazita daudela, eta ez bi norabideetan. Hori dela eta, bakarrik erabili daitezke grafo bat laua ez dela ziurtatzeko, baina ez dute frogatzen grafo bat laua denik. Bi teoremek huts egiten badute, beste metodo batzuk erabili behar dira.