Skärningsgraf

Ett exempel på hur korsande mängder definierar en graf.

I grafteorin är en skärningsgraf en graf som representerar mönstret av skärningspunkter för en familj av mängder . Vilken graf som helst kan representeras som en skärningsgraf, men några viktiga specialklasser av grafer kan definieras av de typer av uppsättningar som används för att bilda en skärningsrepresentation av dem.

Formell definition

Formellt är en skärningsgraf G en oriktad graf bildad av en familj av mängder

$S_{i},\,\,\,i=0,1,2,\dots$

genom att skapa en vertex v _i för varje uppsättning Si _icke , och ansluta två hörn v _i och v _j med en kant när de motsvarande två uppsättningarna har en -tom skärningspunkt, dvs.

$E(G)=\{\{v_{i},v_{j}\}\mid i\neq 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 varje vertex vi _av G , bilda en mängd Si _som består av kanterna som faller in mot v _i ; då har två sådana uppsättningar en icke-tom skärningspunkt om och endast om motsvarande hörn delar en kant. Därför G skärningsgrafen för _mängderna Si .

Erdős, Goodman & Pósa (1966) ger en konstruktion som är mer effektiv, i den meningen att den kräver ett mindre totalt antal element i alla uppsättningarna Si _kombinerade . För den är det totala antalet uppsättningselement högst n ² / 4 , där n är antalet hörn i grafen. De tillskriver observationen att alla grafer är skärningsdiagram till Szpilrajn-Marczewski (1945), men säger att se även Čulík (1964) . Skärningsnumret för en graf är det minsta totala antalet element i varje skärningsrepresentation av grafen .

Klasser av skärningsdiagram

Många viktiga graffamiljer kan beskrivas som skärningsdiagram för mer begränsade typer av uppsättningsfamiljer, till exempel uppsättningar härledda från någon form av geometrisk konfiguration:

• En intervallgraf definieras som skärningsdiagrammet för intervaller på den verkliga linjen, eller för anslutna subgrafer i en väggraf .
• En indifferensgraf kan definieras som skärningsdiagrammet för enhetsintervall på den verkliga linjen
• En cirkelbågsgraf definieras som skärningsgrafen för bågar på en cirkel .
• En polygoncirkelgraf definieras som skärningspunkten mellan polygoner och hörn på en cirkel.
• En karakterisering av en ackordsgraf är som skärningsgrafen för anslutna subgrafer i ett träd .
• En trapetsdiagram definieras som skärningsdiagrammet för trapetser bildade av två parallella linjer. De är en generalisering av begreppet permutationsgraf , i sin tur är de ett specialfall av familjen av komplement av jämförbarhetsgrafer som kallas samjämförbarhetsgrafer.
• En enhetsskivagraf definieras som skärningsdiagrammet för enhetsskivor i planet.
• En cirkelgraf är skärningsgrafen för en uppsättning ackord i en cirkel.
• Cirkelpackningssatsen säger att plana grafer är exakt skärningsgraferna för familjer av slutna skivor i planet som begränsas av icke-korsande cirklar .
• Scheinermans gissning (nu ett teorem) säger att varje plan graf också kan representeras som en skärningsgraf av linjesegment i planet. Emellertid kan skärningsgrafer för linjesegment också vara icke-plana, och igenkännandet av skärningsdiagram för linjesegment är komplett för den existentiella teorin om verkligheten ( Schäfer 2010 ).
• Linjediagrammet för en graf G definieras som skärningsdiagrammet för kanterna på G , där vi representerar varje kant som en uppsättning av dess två ändpunkter.
• En stränggraf är skärningsdiagrammet för kurvor på ett plan .
• En graf har boxicitet k om den är skärningsgrafen för flerdimensionella rutor med dimensionen k , men inte av någon mindre dimension.
• En klickgraf är skärningsdiagrammet för maximala klick i en annan graf
• En blockgraf av klickträd är skärningsdiagrammet för bikopplade komponenter i en annan graf

Scheinerman (1985) karakteriserade skärningsklasserna av grafer , familjer av ändliga grafer som kan beskrivas som skärningsgrafer för mängder dragna från en given familj av mängder. Det är nödvändigt och tillräckligt att familjen har följande egenskaper:

• Varje inducerad subgraf i en graf i familjen måste också vara i familjen.
• Varje graf som bildas från en graf i familjen genom att ersätta en vertex med en klick måste också tillhöra familjen.
• Det finns en oändlig sekvens av grafer i familjen, som var och en är en inducerad subgraf av nästa graf i sekvensen, med egenskapen att varje graf i familjen är en inducerad subgraf av en graf i sekvensen.

Om skärningsdiagramrepresentationerna har det ytterligare kravet att olika hörn måste representeras av olika uppsättningar, kan klickexpansionsegenskapen utelämnas.

Relaterade begrepp

En ordningsteoretisk analog till skärningsgraferna är inklusionsordningarna . På samma sätt som en skärningsrepresentation av en graf betecknar varje hörn med en uppsättning så att hörn ligger intill om och endast om deras mängder har en icke-tom skärningspunkt, så markerar en inklusionsrepresentation f av en poset varje element med en mängd så att för alla x och y i satsen, x ≤ y om och endast om f ( x ) ⊆ f ( y ).

Se även

• Kontaktdiagram

•   Čulík, K. (1964), "Applications of graph theory to matematic logic and linguistics", Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) , Prag: Publ. Hus Czechoslovak Acad. Sci., s. 13–20, MR 0176940 .
•    Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153/CJM-1966-014-3 , MR 0186575 , S2CID 646660 .
•   Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs , Academic Press, ISBN 0-12-289260-7 .
•    McKee, Terry A.; McMorris, FR (1999), Topics in Intersection Graph Theory , SIAM Monographs on Discrete Mathematics and Applications, vol. 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 classes d'ensembles", Fund. Matematik. , 33 : 303-307, doi : 10.4064/fm-33-1-303-307 , MR 0015448 .
•   Schaefer, Marcus (2010), "Complexity of some geometric and topological problems" (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, september 2009, Revised Papers , Lecture Notes in Computer Science, vol. 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), "Characterizing intersection classes of graphs", Discrete Mathematics , 55 (2): 185–193, doi : 10.1016/0012-365X(85)90047-0 , MR 0798535 .

Vidare läsning

• För en översikt av både teorin om skärningsgrafer och viktiga specialklasser av skärningsgrafer, se McKee & McMorris (1999) .

externa länkar

• Jan Kratochvíl, en videoföreläsning om korsningsdiagram (juni 2007)
• E. Prisner, A Journey through Intersection Graph County