Risteyskaavio - Intersection graph

Esimerkki siitä, kuinka leikkaavat joukot määrittävät kuvaajan.

Vuonna graafiteoria An risteyksen kuvaaja on kaavio , joka edustaa rakenteessa risteyksiä ja perheen sarjoiksi . Mikä tahansa kaavio voidaan esittää leikkauskäyränä, mutta jotkin tärkeät kaavioiden erityisluokat voidaan määritellä niiden joukotyyppien avulla, joita käytetään muodostamaan niiden leikkauskuva.

Virallinen määritelmä

Muodollisesti leikkauskuvaaja G on suuntaamaton kaavio, joka on muodostettu joukkojoukosta

S _i , i = 0, 1, 2, ...

luomalla yksi kärki v _i kullekin joukolle S _i ja yhdistämällä kaksi kärkeä v _i ja v _j reunalla aina, kun vastaavilla kahdella joukolla on tyhjä leikkauspiste,

E ( G ) = {{ v _i , v _j } | i ≠ j , S _i ∩ S _j ≠ ∅}.

Kaikki kuvaajat ovat leikkauskuvaajia

Mikä tahansa suuntaamaton verkko G voidaan esittää leikkauksena kuviossa: kunkin kärkipisteen v _i on G , muodostavat joukon S _i , joka koostuu reunojen tapahtuman v _i ; silloin kahdella tällaisella joukolla on tyhjä leikkauspiste vain ja vain, jos vastaavat kärjet jakavat reunan. Erdős, Goodman & Pósa (1966) tarjoavat tehokkaamman rakenteen (toisin sanoen vaatii pienemmän elementtien kokonaismäärän kaikissa sarjoissa S _i yhdistettynä), jossa joukkoelementtien kokonaismäärä on enintään n ² / 4 missä n on kaavion pisteiden lukumäärä. He arvostavat Szpilrajn-Marczewskin (1945) havaintoa, että kaikki kuvaajat ovat leikkauskuvaajia , mutta sanovat näkevänsä myös Čulíkin (1964) . Leikkauspiste määrä graafin on pienin alkioiden kokonaislukumäärä missä tahansa risteyksessä esitys kaavion.

Risteyskaavioiden luokat

Monia tärkeitä kaavioperheitä voidaan kuvata leikkauskuvaajina rajoitetummille joukkojoukoille, esimerkiksi joukot, jotka on johdettu jonkinlaisesta geometrisesta kokoonpanosta:

• Aikaväli kaavio on määritelty risteyksessä kuvaaja välein reaaliakselilla, tai yhdistettyjen subgraphs on polku kuvaajan .
• Välinpitämättömyys kuvaaja voidaan määritellä risteyksessä kuvaaja yksikön välein reaaliakselilla
• Ympyränkaaren kaavio on määritelty risteyksessä kuvaaja kaarien ympyrän .
• Monikulmion ympyrän kuvaaja määritellään risteyksessä monikulmiot kulmat ympyrän.
• Yksi sointukaavion luonnehdinta on puun yhdistettyjen alikaavioiden leikkauskuvaaja .
• Puolisuunnikkaan muotoinen kuvaaja määritellään risteyksessä kuvaajan trapetsoidimenetelmällä muodostettu kaksi rinnakkaista. Ne ovat yleistys permutaatiokaavion käsitteestä , puolestaan ​​ne ovat erityistapaus vertailukuvaajien täydennysryhmästä, joka tunnetaan nimellä vertailukelpoisuusgraafit.
• Yksikkö levy kaavio on määritelty risteyksessä kuvaaja yksikön levyjen tasossa.
• Ympyrä kuvaaja on leikkauspiste kuvaajan joukko sointuja ympyrän.
• Ympyrä pakkaus lause todetaan, että tasomainen kuvaajat ovat täsmälleen risteyksessä kuvaajat perheiden suljetun levyjä tasossa, jota rajoittaa ei-rajan piireissä.
• Scheinermanin oletuksessa (nyt lause) todetaan, että jokainen tasomainen kaavio voidaan esittää myös tasossa olevien viivasegmenttien leikkauskuvaajana. Kuitenkin, leikkauspiste kaavioita johtosegmenteistä voi olla ei-tasomainen, kuten hyvin, ja tunnustaa leikkauspiste kaavioita janojen on valmis varten eksistentiaaliseen teoria reals ( Schaefer 2010 ).
• Viivadiagrammi graafin G määritellään leikkauspiste kuvaajan reunojen G , jossa ovat kukin reuna joukko sen kaksi päätepistettä.
• Merkkijono kaavio on risteyksessä kuvaaja käyrät tasossa .
• Graafilla on ruutu k, jos se on ulottuvuuden k moniulotteisten laatikkojen leikkauskuvaaja , mutta ei pienempi.
• Klikki kaavio on risteyksessä kuvaaja maksimaalinen klikkien toisen kuvaajan
• Lohko kaavio on klikki puu on risteyksessä kuvaaja biconnected komponenttien toisen kuvaajan

Scheinerman (1985) luonnehti graafien leikkausluokkia , äärellisten graafien perheitä, joita voidaan kuvata tietystä joukkojoukosta piirrettyjen joukkojen leikkauskuvaajina. On välttämätöntä ja riittävää, että perheellä on seuraavat ominaisuudet:

• Jokaisen perheen kaavion indusoidun alikaavion on oltava myös perheessä.
• Jokaisen kaavion, joka muodostetaan perheen kaaviosta korvaamalla kärkipiste klikkauksella, on kuuluttava myös perheeseen.
• Perheessä on ääretön kaavioiden sekvenssi, joista kukin on sekvenssin seuraavan kaavion indusoitu alikaavio, jolla on ominaisuus, että jokainen perheen kaavio on sekvenssin graafin indusoitu aligrafiikka.

Jos leikkauskäyräesityksillä on lisävaatimus, että eri pisteet on esitettävä eri joukkoilla, niin klikkauksen laajennusominaisuus voidaan jättää pois.

Liittyvät käsitteet

Jotta teoreettista analoginen risteys kuvaajat ovat sisällyttäminen tilauksia . Samalla tavoin, että leikkauspiste esitys kuvaajan tarrat joka kärkeen joukko siten, että pisteiden ovat vierekkäin, jos ja vain jos niiden sarjaa on ei-tyhjä risteys, niin sisällyttämisen esitys f on poset tarrat jokainen elementti joukon siten, että kaikki x ja y poseteissa, x  ≤  y ja vain, jos f ( x ) ⊆  f ( y ).

Katso myös

• Yhteystiedot-kaavio

Viitteet

• Čulík, K. (1964), "Graafiteorian sovellukset matemaattiseen logiikkaan ja kielitieteeseen", Graafien teoria ja sen sovellukset (Proc. Sympos. Smolenice, 1963) , Praha: Publ. Talo Tšekkoslovakian Acad. Sei., S. 13–20, MR  0176940.
• Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "Kaavion esitys asetettujen leikkauspisteiden avulla" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153 / CJM-1966-014-3 , MR  0186575.
• Golumbic, Martin Charles (1980), algoritminen graafiteoria ja täydelliset kuvaajat , Academic Press, ISBN 0-12-289260-7.
• McKee, Terry A .; McMorris, FR (1999), Aiheet leikkausgraafiteoriassa , SIAM-monografiat erillisestä matematiikasta ja sovelluksista, 2 , Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR  1672910.
• Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des class d'ensembles", rahasto. Matematiikka. , 33 : 303–307, MR  0015448.
• Schaefer, Marcus (2010), "Joidenkin geometristen ja topologisten ongelmien monimutkaisuus" (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, syyskuu 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Springer-Verlag, s. 334–344, doi : 10.1007 / 978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
• Scheinerman, Edward R. (1985), "Graafien leikkausluokat", Diskreetti matematiikka , 55 (2): 185–193, doi : 10.1016 / 0012-365X (85) 90047-0 , MR  0798535.

Lisälukemista

• Katso yleiskatsaus sekä leikkauskaavioiden teoriasta että tärkeistä leikkauskaavioiden erikoisluokista, katso McKee & McMorris (1999) .

Ulkoiset linkit

• Jan Kratochvíl, videoluento leikkauskaavioista (kesäkuu 2007)
• E. Prisner, Matka risteyskaavion piirikunnan kautta