Skæringsgraf

I grafteori er en skæringsgraf en graf, der repræsenterer skæringsskemaet for en familie af sæt . Enhver graf kan repræsenteres som en skæringsgraf, men nogle vigtige specialklasser kan defineres i forhold til de sættyper, der bruges til repræsentation som skæringssæt.

For en oversigt over skæringsgrafteori og vigtige specielle klasser af skæringsgrafer, se McKee og McMorris [1] .

Formel definition

En skæringsgraf er en urettet graf dannet af en familie af sæt

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

ved at skabe et toppunkt for hvert sæt og forbinde to toppunkter og en kant, hvis de tilsvarende to sæt har et ikke-tomt skæringspunkt, dvs. $v_{i}$ $S_{i}$ $v_{i}$ $v_{j}$

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

Alle grafer er skæringsgrafer

Enhver urettet graf G kan repræsenteres som en skæringsgraf - for et hvilket som helst toppunkt på grafen G danner vi et sæt bestående af kanter, der falder ind med . To sådanne sæt har et ikke-tomt skæringspunkt, hvis og kun hvis de tilsvarende spidser hører til den samme kant. Erdős, Goodman og Poza [2] viste en mere effektiv konstruktion (som kræver færre elementer i alle mængder ), hvor det samlede antal elementer i mængderne ikke overstiger , hvor n er antallet af hjørner i grafen. Deres påstand om, at alle grafer er skæringsgrafer, blev noteret af Marchevsky [3] , men de anbefalede også at se på Chuliks arbejde [4] . En grafs skæringsantal er det mindste antal elementer i repræsentationerne af en graf som en skæringsgraf. $v_{i}$ $S_{i}$ $v_{i}$ $S_{i}$ $n^{2}/4$

Klasser af skæringsgrafer

Mange vigtige familier af grafer kan beskrives som skæringsgrafer af begrænsede sættyper, såsom sæt afledt af visse geometriske konfigurationer:

En intervalgraf er defineret som en graf over skæringspunkter af intervaller på en linje eller forbundne stiundergrafer .
En cirkelbuegraf er defineret som en cirkelbueskæringsgraf .
Grafen for polygoner på en cirkel er defineret som grafen over skæringspunkter mellem polygoner med hjørner, der ligger på cirklen.
Et af kendetegnene ved akkordgrafer er, at de er skæringsgrafer af forbundne undergrafer i et træ .
En trapezformet graf er defineret som grafen over skæringspunkter mellem trapezoider dannet af to parallelle linjer. De er en generalisering af begrebet en permutationsgraf , som igen er et specialtilfælde af komplementfamilien af sammenlignelighedsgrafer , kendt som cocomparability-grafer.
Enhedscirkelgrafen er defineret som skæringsgrafen for enhedscirkler i planet.
Cirkelpakningssætningen siger, at plane grafer er nøjagtigt skæringsgraferne for familier af lukkede usammenhængende (berøring tilladt) diske i planet.
Scheinermans formodning (nu et teorem) siger, at enhver plan graf kan repræsenteres som en graf over skæringspunkter mellem linjestykker i en plan. Imidlertid kan grafer af skæringspunkter af segmenter på en linje være ikke-plane, og genkendelse af grafer for skæringspunkter af segmenter på en linje er komplet for teorien om eksistensen af reelle tal [5] .
Linjegrafen for en graf G er defineret som skæringsgrafen for kanterne af en graf G , hvor hver kant betragtes som et sæt af to af dens endespidser.
En strenggraf er en graf over skæringspunkter mellem kurver i et plan .
En graf har ramme k , hvis den er en skæringsgraf af flerdimensionale rektangler med dimension k , men ikke mindre dimensioner.

Variationer og generaliseringer

De teoretiske analoger til rækkefølgen af skæringsgrafer er indlejringsrækkefølger . På samme måde som gengivelsen af skæringsgrafen mærker hvert toppunkt ved det sæt af kanter, der falder ind dertil, og som har et ikke-tomt skæringspunkt, mærker indlejringsrækkefølgen f -repræsentationen af et delvist ordnet sæt hvert element med et sæt således, at for enhver x og y i det hvis og kun hvis . $x\leq y$ $f(x)\subseteq f(y)$
Nervebelægning

Litteratur

K. Culik. Teori om grafer og dens anvendelser (Proc. Sympos. Smolenice, 1963). — Prag: Udg. Hus Czechoslovak Acad. Sci., 1964, s. 13-20.
Paul Erdős, A.W. Goodman, Louis Posa. Repræsentationen af en graf ved faste skæringspunkter // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - doi : 10.4153/CJM-1966-014-3 .
Martin Charles Golumbic. Algoritmisk grafteori og perfekte grafer. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Emner 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. — (Forelæsningsnotater i datalogi). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_32 .