Tasokaavio

Tasograafi  on graafi , joka voidaan piirtää tasolle ylittämättä muita reunoja kuin kärkipisteissä. Mitä tahansa tiettyä tasograafin kuvaa tasossa ilman, että kulmat risteävät kärjessä, kutsutaan tasograafiksi . Toisin sanoen tasograafi on isomorfinen jollekin tasolle kuvattulle tasograafille siten, että sen kärjet ovat tason pisteitä ja reunat ovat tason käyriä, jotka, jos ne leikkaavat toisensa, niin vain pitkin. kärjet. Alueita, joihin kuvaaja jakaa tason, kutsutaan sen pinnoiksi . Tason rajaton osa on myös pinta, jota kutsutaan ulkopinnaksi . Mikä tahansa tasograafi voidaan suoristaa, eli piirtää uudelleen tasolle niin, että sen kaikki reunat ovat viivasegmenttejä.

Ominaisuudet

Eulerin kaava

Yhdistetyssä tasograafissa seuraava suhde pätee kärkien , reunojen ja pintojen (mukaan lukien ulkopinnan) välillä:

Euler löysi sen vuonna 1736 [1] tutkiessaan kuperan polyhedran ominaisuuksia . Tämä suhde pätee myös muille pinnoille Euler-ominaiskäyräksi kutsuttuun tekijään asti . Tämä on pintainvariantti , tasolle tai pallolle se on kaksi, ja esimerkiksi toruksen pinnalla se  on nolla.

Kaavalla on monia hyödyllisiä vaikutuksia. Ensinnäkin, kaikilla yhden graafin tasomaisilla pinoilla on sama määrä pintoja. Toiseksi, jos kutakin pintaa rajoittaa vähintään kolme reunaa (edellyttäen, että kaaviossa on enemmän kuin kaksi reunaa) ja jokainen reuna erottaa kaksi pintaa ,

Näin ollen

eli suuremmalle määrälle reunoja tällainen graafi on ilmeisesti ei-tasomainen. Päinvastoin ei pidä paikkaansa: Petersenin graafi voidaan ottaa vastaesimerkkinä . Tästä seuraa, että tasograafissa on aina mahdollista löytää korkeintaan 5 asteen kärki.

Yleinen kaava on myös helppo yleistää irrotetun graafin tapaukseen:

missä  on kaavion yhdistettyjen komponenttien lukumäärä.

Kaksi esimerkkiä ei-tasoisista kaavioista

Täydellinen graafi, jossa on viisi kärkeä

Lemma. Täydellistä graafia , jossa on viisi kärkeä (K 5 ), ei voi litistää.

Todiste. Se ei toimi hänelle .

"Talot ja kaivot"

Kolmen kaivon ongelma . Siellä on kolme taloa ja kolme kaivoa. Onko mahdollista rakentaa polkuja talojen ja kaivojen väliin siten, että jokaisesta talosta jokaiseen kaivoon johtaa polku, eikä kahta polkua risteäisi. Siltoja ei voi rakentaa.

Lemma. Täydellistä kaksiosaista graafia , jossa on kolme kärkeä kussakin osassa (K 3,3 ), ei voida asettaa tasolle.

Todiste. Eulerin kaavan mukaan kaaviossa on 5 pintaa.

Toisaalta: mikä tahansa pinta (mukaan lukien ulompi) sisältää parillisen määrän reunoja, mikä tarkoittaa vähintään 4. Koska jokainen reuna sisältyy tasan kahteen pintaan, saadaan relaatio , F  on pintojen lukumäärä, E  on reunojen lukumäärä. Korvaamme F = 5 ja E = 9 tähän epäyhtälöön ja näemme, että se ei täyty.

Pontrjagin-Kuratovsky-lause

Väite on ilmeinen: jos graafi G sisältää aligraafin , joka on homeomorfinen K 5 :n tai K 3,3 :n kanssa, niin sitä ei voida hajottaa tasossa. Osoittautuu, että myös päinvastoin on totta.

Graafi on tasomainen silloin ja vain, jos se ei sisällä aligraafia , jotka ovat homeomorfisia viiden kärjen täydelliselle graafille (K 5 ) tai "talot ja kaivot" -graafille (K 3,3 ).

Lause voidaan ilmaista myös seuraavassa variantissa (jota joskus kutsutaan Wagnerin lauseeksi ).

Graafi on tasomainen silloin ja vain, jos se ei sisällä K 5 :een tai K 3,3 :een supistuvia osagraafia .

Tietokone tarkistaa tasomaisuuden

Ensimmäisen algoritmin Kuratowskin aligraafin löytämiseksi lineaarisessa ajassa kehittivät Hopcroft ja Tarjan vuonna 1974 [2] .

Ei-tasokaavioiden ominaisuudet

Tasograafit tehtävissä

Värityskortti . Tasainen kartta on väritettävä tietyllä määrällä värejä, jotta kahdella maalla, joilla on yhteinen rajaosuus, on eri värit. Osoittautuu, että erillisalueiden puuttuessa neljä väriä riittää aina, mutta tätä väitettä on erittäin vaikea todistaa, katso Neljän värin ongelma .

Graafin oikaisu ( Farin lause ). Mikä tahansa tasograafi voidaan piirtää uudelleen niin, että se pysyy tasomaisena ja reunoista tulee viivasegmenttejä.

Yleistykset

Graafi sopii jollekin pinnalle, jos se voidaan piirtää sille ilman, että se ylittää reunoja. Pinottua graafia kutsutaan geometriseksi , sen kärjet ovat pinnan pisteitä ja reunat ovat sen viivoja. Alueita, joihin kuvaaja jakaa pinnan, kutsutaan kasvoiksi . Tasograafi on tasolle asetettu graafi.

Kuvaajan G leikkausnumero on graafin G tasaisen piirustuksen reunojen  pienin leikkauspisteiden lukumäärä . Graafi on siis tasomainen silloin ja vain, jos sen leikkausnumero on nolla.

Toroidaalinen graafi  on graafi, joka voidaan asettaa torukselle.

Katso myös

Muistiinpanot

  1. ↑ Harari F. Graafiteoria URSS s. 126
  2. ↑ Hopcroft, John & Tarjan, Robert E. (1974), Efficient planarity testing , Journal of the Association for Computing Machinery, osa 21 (4): 549–568 , DOI 10.1145/321850.321852  .

Linkit