Hypergrafin viivakaavio

Hypergrafin viivakaavio  on graafi , jonka kärkijoukko on hypergraafin hyperreunajoukko ja kaksi hyperreunaa ovat vierekkäin, jos niillä on ei-tyhjä leikkauspiste. Toisin sanoen hypergraafin viivakaavio on äärellisten joukkojen perheen leikkauskuvaaja . Käsite on yleistys tavallisen graafin viivakaaviosta .

Hypergraafien viivakaavioita koskevat kysymykset ovat usein yleistyksiä tavallisten kaavioiden viivakaavioista. Esimerkiksi hypergraafia, jonka kaikki reunat ovat kooltaan k , kutsutaan k-uniformiksi' (2-uniforminen hypergrafi on tavallinen kuvaaja). Hypergraafiteoriassa on usein luonnollista vaatia k -tasaisuutta. Mikä tahansa tavallinen graafi on jonkin hypergraafin viivagraafi, mutta jos kiinnitämme reunan koon k (reunaan kuuluvan joukon pisteiden lukumäärä), ei jokainen graafi ole jonkin k - yhtenäisen graafin viivagraafi. Päätehtävänä on kuvata kullekin viivakaaviot .

Hypergrafiaa kutsutaan lineaariseksi , jos jollakin hyperreunaparilla on korkeintaan yksi kärki risteyksessä. Mikä tahansa graafi ei ole vain jonkin hypergraafin, vaan myös lineaarisen hypergraafin viivakaavio [1] .

K -uniformisten hypergraafien viivakaaviot,

Beinecke [2] kuvasi säännöllisten kaavioiden viivakaavioita luettelemalla 9 kiellettyä indusoitua aligraafia (katso kohta viivakaaviot ). Mitään kuvausta kiellettyjen indusoitujen aligraafien avulla k-uniformisten hypergraafien viivakaavioista ei tunneta millekään arvolle , ja Lovas [3] osoitti, ettei sellaista kuvausta ole äärellisen listan muodossa k = 3:lle.

Kraus [4] kuvasi tavallisten kaavioiden viivakaavioita klikkin peiton suhteen ( katso Line graph ). Berge [1] antaa globaalin kuvauksen Kraus-tyypistä k -uniformisten hypergraafien viivakaavioille .

K -uniformin viivahypergraafien viivakaaviot

Naik, Rao, Srikhande ja Singhi [5] ovat antaneet yleiskuvauksen Kraus-tyypistä k -uniformisten viivahypergrafien viivakaavioille . Samaan aikaan he löysivät äärellisen määrän kiellettyjä indusoituja aligraafia lineaarisille 3-uniformisille hypergrafeille, joiden huippupisteen minimiaste oli vähintään 69. Metelsky ja Tyshkevich [6] ja Jakobson, Kezdi, Lekhel [7] paransivat tätä rajoitusta 19: ään. , kun taas Skums, Suzdal ja Tyszkiewicz [8] vähensivät tämän 16:een. Metelsky ja Tyszkiewicz [6] osoittivat myös, että k > 3:lle ei ole olemassa sellaista listaa lineaarisille k -uniformisille hypergrafeille, riippumatta siitä, mikä asterajoitus on asetettu.

Lineaaristen k -uniformisten hypergraafien kuvauksen löytämisen monimutkaisuus on se, että kiellettyjä generoituja aligraafia on äärettömän monta. Esimerkkinä m > 0 ottamalla m timanttigraafin ketju niin, että timanteilla on toisen asteen kärjet, ja lisäämällä joitain riippuvia pisteitä kuvan osoittamalla tavalla saadaksesi yksi vähimmäiskiellettyjen aligraafien perheistä [5 ] [9] .

Lineaaristen k -uniformisten hypergraafien viivakaavioille on olemassa useita mielenkiintoisia kuvauksia eri kirjoittajilta [10] , joissa on rajoituksia pisteiden minimiasteeseen tai reunojen minimiasteeseen. Vähimmäisreunaaste minkä tahansa k -uniformin viivahypergrafien viivagraafien kuvaamiseen , mikä ei ole pienempi Naikin, Raon, Srikhanden ja Sighin [5] töissä , on pelkistetty Jakobsonin, Kezdin, Lehelin teoksissa [7 ]. ] ja Zverovich [11] .

Lineaaristen k -uniformisten hypergraafien viivakaavioiden tunnistamisen monimutkaisuus ilman minimiasteen (tai reunojen minimiasteen) rajoituksia on tuntematon. Kun k = 3 ja minimiaste on vähintään 19, tunnistus on mahdollista polynomiajassa [7] [6] ). Skums, Suzdal ja Tyszkiewicz [8] alensivat vähimmäisasteen kymmeneen.

Niken et ai., Jacobson et al., Metelsky et al. ja Zverovich töissä on monia ratkaisemattomia ongelmia ja hypoteeseja.

Muistiinpanot

  1. ↑ 12 Berge , 1989 .
  2. ↑ Beineke, 1968 .
  3. ↑ Lovász, 1977 .
  4. ↑ Krausz, 1943 .
  5. ↑ 1 2 3 Naik, Rao, Shrikhande, Singhi, 1980 .
  6. ↑ 1 2 3 Metelsky ja Tyshkevich, 1997 .
  7. ↑ 1 2 3 Jacobson, Kézdy, Lehel, 1997 .
  8. ↑ 1 2 Skums, Suzdal', Tyshkevich, 2009 .
  9. ↑ Naik, Rao, Shrikhande, Singhi, 1982 .
  10. ↑ Naik, Rao, Shrikhande, Singhi, 1980 ; Naik, Rao, Shrikhande, Singhi 1982 ; Jacobson, Kézdy, Lehel, 1997 ; Metelsky ja Tyshkevich, 1997 ; Zverovich, 2004
  11. ↑ Zverovich, 2004 .

Kirjallisuus