Skärningsdiagram

I grafteorin är en skärningsgraf en graf som representerar skärningsschemat för en familj av mängder . Vilken graf som helst kan representeras som en skärningsgraf, men några viktiga specialklasser kan definieras i termer av de mängdtyper som används för representation som skärningsmängder.

Se McKee och McMorris [1] för en översikt av teorin om korsningsgrafer och viktiga specialklasser av korsningsgrafer .

Formell definition

En skärningsgraf är en oriktad graf bildad av en familj av uppsättningar

S_{i},i=0,1,2,...

genom att skapa en vertex för varje uppsättning och koppla samman två hörn och en kant om motsvarande två uppsättningar har en icke-tom skärningspunkt, d.v.s. $v_{i}$ $Si}$ $v_{i}$ $v_{j}$

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

Alla grafer är skärningsdiagram

Vilken oriktad graf G som helst kan representeras som en skärningsgraf - för vilken vertex som helst av grafen G bildar vi en uppsättning som består av kanter som faller in med . Två sådana uppsättningar har en icke-tom skärningspunkt om och endast om motsvarande hörn hör till samma kant. Erdős, Goodman och Poza [2] visade en mer effektiv konstruktion (som kräver färre element i alla uppsättningar ) där det totala antalet element i uppsättningarna inte överstiger , där n är antalet hörn i grafen. Deras påstående att alla grafer är skärningsdiagram noterades av Marchevsky [3] , men de rekommenderade också att titta på Chuliks arbete [4] . Skärningsantalet för en graf är det minsta antalet element i representationerna av en graf som en skärningsgraf. $v_{i}$ $Si}$ $v_{i}$ $Si}$ $n^{2}/4$

Klasser av skärningsdiagram

Många viktiga familjer av grafer kan beskrivas som skärningsgrafer av begränsade uppsättningstyper, såsom uppsättningar härledda från vissa geometriska konfigurationer:

En intervallgraf definieras som en graf över skärningspunkter av intervall på en linje, eller anslutna vägundergrafer .
En cirkelbågsgraf definieras som en cirkelbågsskärningsgraf .
Grafen för polygoner på en cirkel definieras som grafen för skärningspunkter mellan polygoner med hörn som ligger på cirkeln.
En av särdragen hos ackordsgrafer är att de är skärningsdiagram av sammankopplade subgrafer i ett träd .
En trapetsformad graf definieras som grafen över skärningspunkter mellan trapetser som bildas av två parallella linjer. De är en generalisering av begreppet en permutationsgraf , som i sin tur är ett specialfall av komplementfamiljen av jämförbarhetsgrafer , kända som samjämförbarhetsgrafer.
Enhetscirkelgrafen definieras som skärningsgrafen för enhetscirklar i planet.
Cirkelpackningssatsen säger att plana grafer är exakt skärningsgraferna för familjer av slutna disjunkta (tillåten beröring) skivor i planet.
Scheinermans gissning (nu ett teorem) säger att vilken plan graf som helst kan representeras som en graf av skärningspunkter mellan linjesegment i ett plan. Emellertid kan grafer över skärningspunkter för segment på en linje vara icke-plana, och igenkänning av grafer för skärningspunkter mellan segment på en linje är komplett för teorin om förekomsten av reella tal [5] .
Linjediagrammet för en graf G definieras som skärningsdiagrammet för kanterna på en graf G , där varje kant betraktas som en uppsättning av två av dess ändhörn.
En stränggraf är en graf över skärningspunkter mellan kurvor i ett plan .
En graf har ram k om den är en skärningsgraf av flerdimensionella rektanglar med dimensionen k , men inga mindre dimensioner.

Variationer och generaliseringar

De teoretiska analogerna av ordningsföljden av skärningsgrafer är kapslingsordningar . På samma sätt som representationen av skärningsdiagrammet betecknar varje hörn med den uppsättning kanter som faller in på den och som har en icke-tom skärning, betecknar kapslingsordningen f -representationen av en delvis ordnad uppsättning varje element med en uppsättning så att för alla x och y i det om och bara om . $x\leq y$ $f(x)\subseteq f(y)$
Nervbeläggning

Litteratur

K. Culik. Teori om grafer och dess tillämpningar (Proc. Sympos. Smolenice, 1963). — Prag: Publ. Hus Czechoslovak Acad. Sci., 1964, sid. 13-20.
Paul Erdős, A.W. Goodman, Louis Posa. Representationen av en graf genom fastställda skärningspunkter // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - doi : 10.4153/CJM-1966-014-3 .
Martin Charles Golumbic. Algoritmisk grafteori och perfekta grafer. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Ämnen i Intersection Graph Theory. - Philadelphia: Society for Industrial and Applied Mathematics, 1999. - Vol 2. - (SIAM Monographs on Discrete Mathematics and Applications). — ISBN 0-89871-430-3 .
E. Szpilrain-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Matematik. . - 1945. - T. 33 . - S. 303-307 .
Marcus Schäfer. Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, september 2009, Revised Papers . - Springer-Verlag, 2010. - Vol. 5849. - S. 334-344. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_32 .

Länkar

Jan Kratochvíl, en videoföreläsning om korsningsdiagram (juni 2007) Arkiverad 17 februari 2020 på Wayback Machine
E. Prisner, A Journey through Intersection Graph County Arkiverad 24 april 2021 på Wayback Machine